Optimalizace bez omezení
(unconstraint)
Nederivační (ad hoc) metody
Jednoduché metody
Nelder-Meadova (simplexová) metoda
Derivační metody
První derivace
Metoda největšího spádu + další spádové metody
Metoda konjugovaných gradientů
Druhá derivace
Newton-Raphsonova metoda
Quasi-Newtonova metoda
Metody konjugovaných gradientů
- obecně
= metody sdružených gradientů
= conjugate gradient method
= speciální případ metod sdružených směrů
Základní myšlenka: Pro určení směru přesunu z bodu x(k) do bodu
x(k+1) se využívají nejen hodnotu g(k+1), ale rovněž hodnotu g(k).
(V obecném případě je možno využít hodnot g(1), g(2), ..., g(k),
g(k+1).)
Zdůvodnění: Spojení informací o současném a předchozím
sklonu studované funkce umožňuje rychlejší sestup do minima
(zlepšení konvergence na plochých oblastech).
Metody konjugovaných gradientů
- algoritmus
Výpočet x(k+1):
x(k+1) se určuje pomocí stejného vztahu jako u
spádových metod:
x(k+1) = x(k) + a(k).s(k) [2.1]
kde:
s(k) směr přesunu z bodu x(k)
a(k) koeficient, popisující délku daného přesunu
Metody konjugovaných gradientů
- algoritmus II
Výpočet a(k):
Analogické jako u spádových metod:
1) Je nutno zvolit koeficient a(k) tak, aby platilo:
0 < a(k) < a(k)´
kde: f(x(k) + a(k)´.s(k)) = f(x(k+1))
2) a(k) by se měla co nejvíce blížit a(k)*,
kde a(k)* je minimum funkce f(x(k) + a(k).s(k)).
Metody konjugovaných gradientů
- algoritmus III
Výpočet s(k+1):
s(k+1) se vypočte pomocí gradientu g(k+1) a směru s(k).
(Přičemž s(k) byl vypočítán pomocí předchozích
hodnot gradientů ...). Konkrétně:
s(k+1) = -g(k+1) + b(k).s(k) [2.2]
Kde b(k) je koeficient, který určuje míru vlivu směru
přesunu v kroku k (s(k)) na směr přesunu v
následujícím kroku (s(k+1) ).
Výpočet s(0):
s(0) = -g(0)
Metody konjugovaných gradientů
- algoritmus III
Výpočet b(k+1):
Existuje více možností, jak volit číslo b(k+1).
Nyní odvodíme hodnotu b(k+1) za předpokladu, že
minimalizovaná funkce je kvadratická a má pozitivně definitní
Hessovou matici G. V tomto případě platí:
y(k) = G.d(k) [2.3]
kde y(k) = g(k+1) – g(k) a d(k) = x(k+1) – x(k).
Protože vektory s(k+1) a s(k) mají být sdružené vzhledem ke G,
musí platit:
s(k+1)T.G.d(k) = 0 [2.4]
Z [2.3] a [2.4] vyplývá:
0 = s(k+1)T.G.d(k) = s(k+1)T.y(k)
Metody konjugovaných gradientů
- algoritmus IV
Po transponování rovnice [2.2] a násobení vektorem y(k)
zprava dostáváme:
0 = -g(k+1)T.y(k) + b(k).s(k)T.y(k) [2.5]
Odtud plyne hodnota, kterou navrhli Hestenes a Stiefel
v roce 1952:
[2.6])(
)(
)()1()(
)()1()1(
)(
kkTk
kkTk
k
HS
ggs
ggg
−
−
= +
++
b
s(k+1) = -g(k+1) + b(k).s(k) [2.2]
Metody konjugovaných gradientů
- algoritmus V
Pokud je x(k) v rovnici [2.1] přesně určeným minimem
ve směru s(k), musí platit s(k)T.g(k+1) = 0 (jinak by se
hodnota f ve směru s(k) dala ještě snížit), obdobně
s(k-1)T.g(k) = 0. Pak je jmenovatel ve vztahu [2.6]
roven:
[2.7]
( )  
2
2
)()()(
)()1()1()()()()()1()(
kkk
kTkkkkTkkkTk
g.gg
.g.sg.gsggs
==
=−=−=− −−+
b
Metody konjugovaných gradientů
- algoritmus VI
Po dosazení [2.7] do [2.6] získáme vyjádření b(k), které
poprvé publikovali Polak a Ribiere v roce 1969:
[2.8]
Obdobně lze ukázat, že g(k+1)T.g(k) = 0, odtud plyne
vztah pro b(k) podle Fletchera a Reevese (1963):
2
2
)(
)()1()1(
)( )(
k
kkTk
k
PR
g
ggg −
=
++
b
2
2
)(
2
2
)1(
)(
k
k
k
FR
g
g +
=b
Metody konjugovaných gradientů
- algoritmus VII
Pro kvadratické funkce je .
To ale neplatí pro obecnější funkce. Při testovacích
úlohách dává obvykle nejlepší výsledky varianta
Polaka a Ribiera.
)()()( k
FR
k
PR
k
HS bbb ==
Metody konjugovaných gradientů
- zhodnocení
Výhody:
Spolehlivější než spádové metody.
Vhodná i v oblastech poblíž minima
Nevýhody:
Výpočetně náročnější.
Větší prostorová složitost (nutnost ukládat několik nprvkových
vektorů).
Metody konjugovaných gradientů
- porovnání
Vhodná i v oblastech poblíž Porovnání metody největšího
spádu a metody konjugovaných gradientů (Rosenbrockova
funkce):
Dale ko od minima Poblíž minima
(gra die nt < 1kca l.A
-2
) (gra die nt < 0,1kca l.A
-2
)
CPU Poče t ite r. CPU Poče t ite r.
Ne jv. spád 67 98 1405 1893
Konj. grad. 149 213 257 367
Metody konjugovaných gradientů
- porovnání II
Ukázka konvergence spádové metody pro Rosenbrockovu
funkci:
Metody konjugovaných gradientů
- porovnání III
Ukázka konvergence metody konjugovaných gradientů pro
Rosenbrockovu funkci:
Cvičení
Proveďte první 2 kroky optimalizace funkce:
f(x1, x2) = x1
2 + 2x2
2
a) pomocí metody největšího spádu
b) pomocí metody konjugovaných gradientů
Poznámka: Využijte a = 0,25. Počáteční bod je (2,1)
Funkce: f(x1, x2) = x1
2 + 2x2
2
Výchozí bod: x0 = (2, 1)
Parametry: a = 0.25
Gradient funkce: f(x1, x2) = (2x1, 4x2)
Směr funkce: sk = -gk
Následující bod: xk+1 = xk + a.sk
Gradient v bodě x0: g0 = (4,4)
Směr v bodě x0: s0 = (-4,-4)
Bod x1: x1 = (2,1) + 0,25.(-4,-4) = (1,0)
Gradient v bodě x1: g1 = (2,0)
Směr v bodě x1: s1 = (-2,0)
Bod x2: x2 = (1,0) + 0,25.(-2,0) = (0.5,0)
Funkce: f(x1, x2) = x1
2 + 2x2
2
Výchozí bod: x0 = (2, 1)
Parametry: a = 0.25
Gradient funkce: f(x1, x2) = (2x1, 4x2)
Směr funkce: sk = -gk
Následující bod: xk+1 = xk + a.sk
Gradient v bodě x0: g0 = (4,4)
Směr v bodě x0: s0 = (-4,-4)
Bod x1: x1 = (2,1) + 0,25.(-4,-4) = (1,0)
Gradient v bodě x1: g1 = (2,0)
Směr v bodě x1: s1 = (-2,0)
Bod x1: x2 = (1,0) + 0,25.(-2,0) = (0.5,0)
Funkce: f(x1, x2) = x1
2 + 2x2
2
Výchozí bod: x0 = (2, 1)
Parametry: a = 0.25
Gradient funkce: f(x1, x2) = (2x1, 4x2)
Směr funkce: sk = -gk
Následující bod: xk+1 = xk + a.sk
Gradient v bodě x0: g0 = (4,4)
Směr v bodě x0: s0 = (-4,-4)
Bod x1: x1 = (2,1) + 0,25.(-4,-4) = (1,0)
Gradient v bodě x1: g1 = (2,0)
Směr v bodě x0: s1 = (-2,0)
Bod x2: x2 = (1,0) + 0,25.(-2,0) = (0.5,0)
Funkce: f(x1, x2) = x1
2 + 2x2
2
Výchozí bod: x0 = (2, 1)
Parametry: a = 0.25
Gradient funkce: f(x1, x2) = (2x1, 4x2)
Směr funkce: sk = -gk
Následující bod: xk+1 = xk + a.sk
Gradient v bodě x0: g0 = (4,4)
Směr v bodě x0: s0 = (-4,-4)
Bod x1: x1 = (2,1) + 0,25.(-4,-4) = (1,0)
Gradient v bodě x1: g1 = (2,0)
Směr v bodě x0: s1 = (-2,0)
Bod x1: x2 = (1,0) + 0,25.(-2,0) = (0.5,0)
Funkce: f(x1, x2) = x1
2 + 2x2
2
Výchozí bod: x0 = (2, 1)
Parametry: a = 0.25
Gradient funkce: f(x1, x2) = (2x1, 4x2)
Směr funkce: sk = -gk
Následující bod: xk+1 = xk + a.sk
Gradient v bodě x0: g0 = (4,4)
Směr v bodě x0: s0 = (-4,-4)
Bod x1: x1 = (2,1) + 0,25.(-4,-4) = (1,0)
Gradient v bodě x1: g1 = (2,0)
Směr v bodě x0: s0 = (-2,0)
Bod x1: x1 = (1,0) + 0,25.(-2,0) = (0.5,0)
Domácí úkol
Proveďte první 3 kroky optimalizace funkce:
f(x1, x2) = x1
2 + 2x2
2
a) pomocí metody konjugovaných gradientů
Poznámka: Využijte a = 0,25. Počáteční bod je (2,1)
Domácí úkol 2
Gradient Rosenbrockovy funkce:
Výchozí bod:
x0 = (-2, 2)
Parametry:
a = 0,001
f x x x x x( , ) ( ) ( )1 2 2 1
2 2
1
2
100 1= − + −
( ) = − − − − −f x x x x x x x
T
( ) ( ) ( ), ( )400 2 1 2001 2 1
2
1 2 1
2
Připravte implementaci metody konjugovaných gradientů
(např. v Excelu, Pythonu apod.) pro Rosenbrockovu funkci: