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ě
Jsou založeny na stejném principu jako metoda největšího spádu:
x(k+l) _ x(k) + a>s(k)? kde.
s(k) je směr přesunu z bodu x(k),
nejčastěji jako směr volíme -g(k) a koeficient, popisující délku daného přesunu
Využívají sofistikovanější metody k určení koeficientu a. Hodnota koeficientu a je různá pro každou iteraci.
Spádové metody
- obecně II
Podmínka pro ideální hodnotu (a*) koeficientu a: funkce (|)(a) = f(x(a)) má v a* minimum [1]
Poznámka: Jedná se o nejmenší hodnotu a, v níž má (|)(a) minimum. Navíc samozřejmě platí a > 0.
Tuto podmínku nelze využít k volbě koeficientu a.
Potřebujeme totiž určit hodnotu a pro danou iteraci v konečném a pokud možno velmi malém počtu kroků.
Spádové metody
- obecně III
Předpokládejme, že funkce f má průběh naznačený na obrázku.
Pak existuje a > 0 tak, že: f(x<k> + as*>) = f(x*+1>)
Nej menší takové a označujeme a'.
=> Nutné podmínky pro koeficient a:
0 < a < a [2]
Spádové metody
- obecně IV
=> Při volbě koeficientu a musíme dodržet podmínky [2] a co nejvíce se přiblížit podmínce [1].
Metody pro nalezení a:
• Goldsteinovy podmínky
• Wolfe-Powellovy podmínky Značení:
f(xft*") = f(xm+a.sm)
budeme značit (|)(a)
budeme značit (|)(0)
Spádové metody
- Goldsteinovy podmínky I
1. Goldsteinova podmínka zaručuje, že a nebude zvoleno příliš blízko a':
<j){a) < ^(0) + pxx4\0) Parametr p je zde pevně zvolené číslo z intervalu (0, Vi).
I když a neexistuje {tj. §{a) < (|)(0) pro všechna a > 0}, je 1GP schopna omezit volbu a(k). (Pokud je tedy funkce f zdola omezená.)
Spádové metody
- Goldsteinovy podmínky II
2. Goldsteinova podmínka zaručuje, že a nebude zvoleno příliš blízko 0:
Pravé strany Goldsteinových podmínek určují dvě přímky se zápornou směrnicí. Hodnoty ax a a2, které přísluší průsečíkům těchto přímek s (|)(a), určují interval vhodných hodnot a.
Spádové metody
- Goldsteinovy podmínky III
Spádové metody
- Goldsteinovy podmínky IV Zdůvodnění Goldsteinových podmínek:
GP2: <|>(a)=<|>(0)+(l-p)a.<|>'(0)
Spádové metody
- Goldsteinovy podmínky V
Věta: Nechť funkce f je spojitě diferenciovatelná a nechť její gradient g = Vf je lipschitzovsky spojitý na Rn.
Je-li {x(k)} posloupnost generována spádovou metodou a volba a vyhovuje Goldsteinovým podmínkám, pak platí:
f(x«) - fCx^D) > - p.gOO.Ô*)
kde 5« = a*)s*) = x*+1> - x*)
=> Metoda vždy konverguj e k minimu funkce f (pro vhodné p).
Poznámka: Volba koeficientu p < Vi zaručuje konvergenci metody pro kvadratické funkce.
Spádové metody
- Goldsteinovy podmínky VI
Nevýhoda Goldsteinových podmínek:
V intervalu mezi a: a a2 se nemusí nacházet minimum funkce (|)(a).
Spádové metody
- Wolfe-Powellovy podmínky
Místo GP2 se testuje sklon funkce (|)(a) v bodě a.
Využívá se tedy následující podmínka: f (a0| ^ o\ť(0)
kde ae(p, 1).
Spádové metody
- Wolfe-Powellovy podmínky II
a