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
Spádové metody
-obecně
Algoritmus:
• zvolíme výchozí bod x(0)
• k-tá iterace:
bod x(k+1) vypočítáme z bodu x(k) pomocí vztahu:
x(k+1) = x(k) + a.s(k), kde:
s(k) směr přesunu z bodu x(k)
a koeficient, popisující délku daného přesunu
Metoda největšího spádu
-obecně
Algoritmus:
• zvolíme výchozí bod x(0)
• k-tá iterace:
bod x(k+1) vypočítáme z bodu x(k) pomocí vztahu:
x(k+1) = x(k) - a.g(k), kde:
-g(k) zjednodušený zápis -f(x(k)),
určuje směr přesunu z bodu x(k)
a koeficient, popisující délku daného přesunu
s (k) = - g(k)
Metoda největšího spádu
- volba a v metodě největšího spádu
Z bodu x(k) se přesunujeme po polopřímce:
x(a) = x(k) + a.x(k),kde a > 0
Hodnotu funkce f na této polopřímce popisuje funkce
f(a): f(a) = f(x(a))
Je zřejmé, že musíme zvolit takové aOK, aby platilo:
f(x(k)) > f(x(k+1)), kde x(k+1) = x(aOK) pro dostatečný
počet iterací.
Poznámka: „Dostatečný počet“ = dostačuje k tomu,
aby metoda konvergovala k minimu ( ).lim ( )( )
k
k
f x
→
= 0
Metoda největšího spádu
- volba a v metodě největšího spádu
Funkce f(a) má následující tvar:
0
0 ,5
1
1 ,5
2
0 0 ,5 1 1 ,5 2
a
f(a)=f(x(a))
Metoda největšího spádu
- volba a v metodě největšího spádu
Metoda největšího spádu volí pro každý krok stejnou
hodnotu a.
Konkrétně velmi malou hodnotu a.
Poznámka: Hodnoty a musí být dostatečně malá, aby
metoda konvergovala.
Metoda největšího spádu
zhodnocení
Výhody:
• Implementačně jednoduché
• Nízká prostorová složitost
Nevýhody:
• Velmi pomalá konvergence (speciálně v oblastech malého
spádu => nízkých hodnot gradientu).
• Chyby, způsobené zaokrouhlením. Mohou vést i k tomu, že
se výpočet vůbec nedostane rozumně blízko k minimu. Ale
při (ideální) přesné aritmetice metoda konverguje vždy k
nějakému lokálnímu minimu.
1 1
1 1
2 2
1 1
2 2
Metoda největšího spádu
- příklad
Rosenbrockova funkce:
Gradient Rosenbrockovy funkce:
Výchozí bod:
x0 = (-2, 2)
Parametry:
a = 0,001
Vyzkoušejte doma :-)
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