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
Newtonovské metody
Kvazi-Newtonovské metoda

Metody druhé derivace
–
•
Pro stanovení minima funkce f: RN -> R využívají:
•První derivaci funkce f (gradient).
•Druhou derivaci funkce f (hessián).
Poskytuje informace o zakřivení funkce v daném bodě.

 Newtonovské metody
- obecně
•Odvození:
•
•Zapišme si funkci f: R -> R pomocí Taylorova polynomu:
• f(x) = f(x(k)) + (x - x(k)).f´(x(k)) + (x - x(k))2.f´´(x(k))/2 + ...
•Pro první derivaci funkce f tedy platí:
• f´(x) = f´(x(k)) + (x - x(k)).f´´(x(k)) + ...
•Pokud předpokládáme, že funkci f lze v okolí bodu x považovat za kvadratickou funkci, můžeme výše
uvedenou rovnici zjednodušit na následující tvar:
• f´(x) = f´(x(k)) + (x - x(k)).f´´(x(k))

Newtonovské metody
- obecně II
•V bodě x(k+1) tedy pro f platí:
• f´(x(k+1)) = f´(x(k)) + (x(k+1) - x(k)).f´´(x(k))
•Pokud se x(k+1) nachází poblíž minima, pak platí:
• f´(x(k+1)) = 0.
•Takže výše uvedenou rovnici lze přepsat:
• f´´(x(k)).d(k) =  -f´(x(k))
• kde d(k) = x(k+1) - x(k)
•
•Analogicky pro f: RN -> R platí:
• G(k).d(k) = -g(k)

Newtonovské metody
- obecně III
•Jednotlivé typy newtonovských metod se liší v postupu, jakým vyjadřují G(k):
–klasická Newtonova metoda počítá G(k) přesně
–kvazi-newtonovské metody využívají jistou její aproximaci H(k) » G(k)

Newtonovské metody
- klasická Newtonova metoda
•Konstruuje x(k+1) přímo pomocí G(k).
•
•
•V k-ém kroku Newtonovy metody se pak provedou následující operace:
•
•a) Najdi řešení d(k) rovnice G(k).d(k) = -g(k)
•b) Polož x(k+1) = x(k) + d(k)
•

Newtonovské metody
- klasická Newtonova metoda II
•Nejčastějším postupem, jak získat d(k) je tento:
• d(k) = - (G(k))-1. g(k)
•
•Pro x(k+1) tedy platí:
• x(k+1) = x(k) - (G(k))-1. g(k)
•
•

Newtonovské metody
- klasická Newtonova metoda III
•Příklad:
• funkce: f(x, y) = x2 + 2y2
• bod: x(0) = (9, 9)T
•

Newtonovské metody
- klasická Newtonova metoda III
Příklad:
funkce: f(x, y) = x2 + 2y2
bod: x(0) = (9, 9)T
gradient v bodě x(0): g(0) = (18, 36)T
hessian v bodě x(0):
inverze hessianu:
bod x(1):

Newtonovské metody
- klasická Newtonova metoda IV
•Není-li k dispozici procedura pro výpočet hessiánu funkce f, lze jej aproximovat pomocí konečných
diferencí z gradientu. i-tý sloupec gi hessiánu G(k) je pak odhadnut jako:
•
•
•
• kde ei je i-tý jednotkový vektor a hi > 0 je vhodně zvolené malé číslo.
•

Newtonovské metody
- klasická Newtonova metoda V
•Problémy, spojené s použitím Newtonovy metody:
•Pokud matice G(k) není kladně definitní, pak metoda nemusí konvergovat k minimu funkce f
•Určení (G(k))-1 (tedy invertování matice G(k)), má velkou časovou složitost, konkrétně: O(N3).
•Uživatel musí mít nejen algoritmus pro výpočet f(x(k)) a g(k), ale i pro výpočet G(k).
•
•Všechny uvedené problémy jsou vyřešeny v kvazi-newtonovských metodách.

Newtonovské metody
- klasická Newtonova metoda VI
•Newtonova metoda konverguje kvadraticky v okolí minima, jak ukazuje věta:
• Předpokládejme, že funkce f má spojité druhé derivace a její hessián je lipschitzovsky spojitý v
nějakém okolí lokálního minima x*. Pokud x(k) je dostatečně blízko x* pro některé k a pokud G* je
kladně definitní, pak Newtonova metoda pro funkci f konverguje kvadraticky k x*.
•V praxi to znamená, že v každé iteraci se počet platných cifer odhadu řešení zhruba zdvojnásobuje.

Newtonovské metody
- klasická Newtonova metoda VII
•Newtonovské metody lze využít i pro řešení soustav nelineárních rovnic.
•Pokud řešíme rovnici F(x) = 0, kde F: RN -> RN, pak můžeme F rozvinout do Taylorovy řady jako:
• F(x(k+1)) » F(x(k)) + ÑF(x(k))T .d(k)
• kde d(k) = x(k+1) - x(k)
• pokud zanedbáme členy druhého a vyššího stupně.

Newtonovské metody
- klasická Newtonova metoda VIII
•Pokud požadujeme, aby F(x(k+1)) = 0, dostáváme z předchozí rovnice vztah, popisující Newtonovu
metodu pro soustavu nelineárních rovnic:
• - F(x(k)) = ÑF(x(k))T . d(k)T
•Newtonova metoda je zde opět dána postupem:
•a) Najdi řešení d(k) rovnice G(k).d(k) = -g(k)
•b) Polož x(k+1) = x(k) + d(k)
•Kde G(k) = Ñ F(x(k))T a vektor g(k) je nahrazen funkční hodnotou F(x(k)).

Newtonovské metody
- klasická Newtonova metoda IX
•V jednodimenzionárním případě dostáváme z rovnice: - F(x(k)) = ÑF(x(k))T . d(k)T  známou
Newton-Raphsonovu metodu (někdy je také označována metoda tečen):
•

Kvazi-newtonovské metody
•V rámci Newtonovy metody je místem s největší složitostí výpočet inverzního hessiánu, nutného pro
řešení rovnice:
• G(k).d(k) = -g(k)
•Tento krok lze obejít a místo inverzního hessiánu použít sérii matic, které se mu limitně blíží:
•
•

Kvazi-newtonovské metody
•Algoritmus kvazi-newtonovských metod je modifikací algoritmu Newtonovy metody, doplněnou o
lineární vyhledávání a rekurentní výpočet matice H(k) (která je nyní pouze aproximací hessiánu):
•a) Najdi řešení s(k) rovnice H(k).s(k) = -g(k)
•b) Najdi vhodné a(k) a polož:
• x(k+1) = x(k) + a(k)s(k)
•c) Vypočti H(k+1) na základě H(k) tak, aby platilo:
• H(k+1)s(k) = y(k), kde y(k) = g(x(k+1)) – g(x(k))

Kvazi-newtonovské metody
•Inicializace:
•Matice H(0) může být libovolná pozitivně definitní matice.
•Není-li známo, že minimalizační úloha má nějakou speciální strukturu, volí se obvykle
• H(0) = I.
•

Kvazi-newtonovské metody
•Kvazi-Newtonovské metody jsou obecně konstruovány tak, aby H(k+1) byla vždy symetrická a kladně
definitní.
•Díky tomuto faktu a díky své efektivitě jsou kvazi-newtonovské metody nejpoužívanějšími
minimalizačními metodami založenými na Taylorově větě.
•

Kvazi-newtonovské metody
•Pokud chceme zkonstruovat efektivní metodu pro generování matic H(k), měli bychom hledat
rekurentní vyjádření H(k+1) z H(k). Výpočet H(k+1) podle této rekurentní formule by se měl dát
provést pomocí relativně malého počtu operací, což v praxi znamená časovou složitost O(N2). Navíc
by matice H(k+1) měla být symetrická, pokud tuto vlastnost má H(k).

Kvazi-newtonovské metody
•Nejjednodušší formulí, splňující požadavky uvedené na předchozím slidu, je:
• H(k+1) = H(k) + a uuT
• kde u je jistý vektor (obecně závislý na H(k), s(k) a y(k)). Matice uuT má řád 1 a její výpočet
vyžaduje jen n2 + n násobení.
•Z rovnice H(k+1)s(k) = y(k) plyne:
• y(k) - H(k)s(k) = a uuT s(k)

Kvazi-newtonovské metody
•Odtud je vidět, že vektor u je skalárním násobkem vektoru y(k) - H(k)s(k), neboť auuT s(k) =
u(auT s(k)) a (auT s(k)) ÎR.Bez újmy na obecnosti (z hlediska vektoru u) můžeme proto volit u =
y(k) - H(k)s(k).
•Nyní můžeme rovnici y(k) - H(k)s(k) = a uuT s(k)  upravit následovně:
• y(k) - H(k)s(k) = (y(k) - H(k)s(k))auT s(k)

Kvazi-newtonovské metody
•Předchozí rovnici násobíme zleva vektorem:
•
•
•Získáme rovnici 1 = auT s(k), ze které po úpravě dostaneme vztah pro výpočet a:
•

Kvazi-newtonovské metody
•Dosadíme-li vztahy pro u a a do rovnice:
•H(k+1) = H(k) + a uuT
•Získáme vztah, který lze využít pro výpočet H(k+1):
•
•
•Lze ukázat, že tato formule obecně nezachovává pozitivní definitnost matice H.

Kvazi-newtonovské metody
•Je proto vhodné analyzovat formule druhého řádu:
• H(k+1) = H(k) + a uuT + b vvT
•Zde již nejsou vektory u a v určeny jednoznačně.
•Po dosazení do vztahu:
• H(k+1)s(k) = y(k)
•Dostaneme:
• y(k) = H(k) s(k) + a uuT s(k) + b vvT s(k)
•

Kvazi-newtonovské metody
•Odtud analogicky jako v předchozím případě odvodíme vztah pro výpočet H(k+1):
•
•
• horní indexy (k) na pravé straně vynecháváme.
•Tuto metodu navrhli v roce 1970 nezávisle čtyři autoři: Broyden, Fletcher, Goldfard a Shanno.
Proto je označována jako metoda BFGS.

Kvazi-newtonovské metody
•Jinou kvazi-newtonovskou metodu dostaneme, když budeme hledat řešení vyhovující rekurentní formuli
druhého řádu, ale pro inverzi matice H(k). Položíme-li B(k) = (H(k))-1, jde o formuli:
• B(k+1) = B(k) + a uuT + b vvT
•Pokud nyní volíme u = s(k) a v =B(k)y(k), dostáváme obdobným postupem jako u metody BFGS vztah:

Kvazi-newtonovské metody
•Tato metoda byla v jisté podobě obsažena v práci Davidona z roku 1959 a později explicitně popsána
Fletcherem a Powellem v roce 1963. Proto bývá označována zkratkou DFP.

Cvičení
- klasická Newtonova metoda
• funkce: f(x) = 3x12 + 4x22 – 5x1x2 – 2x1
• bod: x(0) = (5, 5)T
•

Cvičení
- klasická Newtonova metoda
• funkce: f(x) = 3x12 + 4x22 – 5x1x2 – 2x1
• bod: x(0) = (5, 5)T
• gradient v bodě x(0):
•
•
• hessian v bodě x(0):
•
•
•
inverze hessianu:
bod x(1):

Cvičení
- klasická Newtonova metoda II
• Příklad 2: Rosenbrockova funkce: f(x) = 100(x2 – x12)2 + (1 – x1)2
• bod: x(0) = (-2, 1)T
•
•

Cvičení
- klasická Newtonova metoda II
• Příklad 2: Rosenbrockova funkce: f(x) = 100(x2 – x12)2 + (1 – x1)2
• bod: x(0) = (-2, 1)T
• gradient v bodě x(0):
•
•
• hessian v bodě x(0):
•
•
•
inverze hessianu:
bod x(1):

Cvičení
- klasická Newtonova metoda III
• Příklad 3: Rosenbrockova funkce: f(x) = 100(x2 + x12)2 + (1 – x1)2
• bod: x(0) = (-2, 1)T
•
•

Cvičení
- klasická Newtonova metoda III
• Příklad 3: Rosenbrockova funkce: f(x) = 100(x2 + x12)2 + (1 – x1)2
• bod: x(0) = (-2, 1)T
• gradient v bodě x(0):
•
•
• hessian v bodě x(0):
•
•
•
inverzní hessian:
bod x(1):