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 nej většího spádu:
x(k+l) _ x(k) + as(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ělll
Předpokládejme, že funkce f má průběh naznačený na obrázku.
Pak existuje a > 0 tak, že: f(x^ + as*)) = f(x<k+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(x(M>) = f(xm+cum) f(xik>)
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':
Parametr p je zde pevně zvolené číslo z intervalu (0, V2).
I když a' neexistuje {tj. (j)(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:
^(a)>^(0) + (l-p).a/(0)
Pravé strany Goldsteinových podmínek určují dvě přímky se zápornou směrnicí. Hodnoty 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*"1)) > - p.g*).ô«
kde 8« = a*Vk) = 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 ax 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 (a)| < <r|f (0)
kde ae(p, 1).
Spádové metody
- Wolfe-Powellovy podmínky II
a