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«) + (x - x«).f (x«) + (x - x«)2.f'(x«)/2 + ... Pro první derivaci funkce f tedy platí: f'(x) = f (x«) + (x - x«).f'(x«) + ... 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: r(x) = f (x«) + (x - x<®).f"(x<&) Newtonovské metody - obecně II V bodě x(k+1) tedy pro f platí: f'(x(k+D) = f(x(k)) + (X(k+l) _ x(k))-f-(x(k)) Pokud se x(k+1) nachází poblíž minima, pak platí: f'(X(k+D) = o. Takže výše uvedenou rovnici lze přepsat: f"(x(k)).ô(k) = -f'(x*>) kde 5« = x^+D - x« Analogicky pro f: RN -> R platí: Q(k)§(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í j istou 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í 5(k) rovnice G(k).5(k) = -g(k) b) Polož x*+1) = + 5« Newtonovské metody - klasická Newtonova metoda II Nejčastějším postupem, jak získat 5(k) je tento: §(k) = _ (G^)-K g*) Pro x(k+1) tedy platí: x(k+l) _ x(k) _ (GW)-1. g(k) Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x(°> = (9, 9)T Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x(°> = (9, 9)T gradient v bodě x(0): Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x(°> = (9, 9)T gradient v bodě x(°>: g(0) = (18, 36)T g = (2x, Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x<°> = (9, 9)T gradient v bodě #: g(°> = (18, 36)T g = (2x, hessian v bodě x(0): Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x*°) = (9, 9)T gradient v bodě x(°>: g(0) = (18, 36)T (2 Ó\ vO Aj g = (2x, hessian v bodě x(0): h(0) = Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x*°) = (9, 9)T gradient v bodě x(°>: g(0) = (18, 36)T (2 Ó\ vO Aj g = (2x, hessian v bodě x(0): h(0) = Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x<°> = (9, 9)T gradient v bodě x^: g<0> = (18, 36)T g = (2x, 4y) (2 0^ hessian v bodě x(0): h(0) = V0 A) inverze hessianu: hm = h " D Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x<°> = (9, 9)T gradient v bodě x^: g<0> = (18, 36)T (2 0^ v0 4j hessian v bodě x(0): h(0) = inverze hessianu: h(0) = 1/2 0 ^ 0 1/4) g = (2x, 4y) h (0)-i V D n Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x(°> = (9, 9)T gradient v bodě x<°>: g(0) = (18, 36)T hessian v bodě x(0): h( = inverze hessianu: h(0) 1 = g = (2x, 4y) '1/2 0 > v 0 1/4; V D bodxd): xm = x(l) = x(0) _ h(0H g (0) Newtonovské metody - klasická Newtonova metoda III Příklad: funkce: f(x, y) = x2 + 2y2 bod: x(°> = (9, 9)T gradient v bodě x<°>: g(0) = (18, 36)T (2 ti\ v0 Aj hessian v bodě x(0): h(0) = inverze hessianu: h (O)"1 _ (1/2 0 ^ V 0 1/4, g = (2x, bodx^: xm = (9) v9y ľ 1/2 0 "\ l 0 1/4/ í18l v36y x(l) = x(0) _ h(0H g (0) 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 y1 hessiánu G(k) je pak odhadnut jako: y „8(x(k))-g h kde ei je i-tý jednotkový vektor a hj > 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ě: 0(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 kx*. 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 - x® 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«) = VF(x«)T . Ô«T Newtonova metoda je zde opět dána postupem: a) Najdi řešení 8(k) rovnice G(k\8(k) = -g(k) b) Polož x = x« + ô*> Kde G(k) = V 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)) = VF(x(k))T . 5(k)T známou Newton-Raphsonovu metodu (někdy je také označována metoda tečen): r(k+l) (k) F(X ) F'(x) Kvazi-newtonovské metody V rámci Newtonovy metody je místem s nej větší složitostí výpočet inverzního hessiánu, nutného pro řešení rovnice: Q(k)g(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íží: lim_ H<*> = (G(k)y1 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+i) = x(k) + a(k)s(k) c) Vypočti H(k+1) na základě H(k) tak, aby platilo: H(k+l)s(k) = y(k)5 y(k) = g(X(k+l)) _ 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<°> = I. Kvazi-newtonovské metody Kvazi-Newtonovské metody j sou obecně konstruovány tak, aby H(k+1) byla vždy symetrická a kladně definitní. Díky tomuto faktu a díky své efektivitě j sou 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 jj(k+i) 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 0(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+1Vk) = y(k) plyne: y(k) _ H(k)s(k) = a uuT s*) Kvazi-newtonovské metody Odtud je vidět, že vektor u je skalárním násobkem vektoru y(k) - H(k)s(k), neboť ccuuT s(k) = u(auT s(k)) a (auT s(k)) eR.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(kVk) = a uuT s(k) upravit následovně: y(k) _ H(k)s(k) = (y(k) _ H(k>s«)auT s*) Kvazi-newtonovské metody Předchozí rovnici násobíme zleva vektorem: / \ -i y(k)-H[K,.S (k) s y y By 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) = 3xj2 + 4x22 - 5xjX2 - 2x1 bod: x<°> = (5, 5)T Cvičení - klasická Newtonova metoda funkce: f(x) = 3xj2 + 4x22 - 5xxx2 - 2xx bod: x<°> = (5, 5)T gradient v bodě x(0): Cvičení - klasická Newtonova metoda funkce: f(x) = 3xx2 + 4x22 - 5xxx2 - 2xx bod: xí°> = (5, 5)T gradient v bodě x(0): g(0) = [6xl — 5x2 — 2, 8x2 -5jCj ) = Cvičení - klasická Newtonova metoda funkce: f(x) = 3xj2 + 4x22 - 5xjX2 - 2xl bod: x<°> = (5, 5)T gradient v bodě x(0): g(0) = (6xl -5x2 - 2, 8x2 -5jcx )r = (3, 15\T Cvičení - klasická Newtonova metoda funkce: f(x) = 3xT2 + 4x22 - 5xxx2 - 2x1 bod: x(°> = (5, 5)T gradient v bodě x(0): g(0) = (ójq - 5x2 - 2, 8x2 - 5x1 )T = (3, 15)r hessian v bodě x(0): Cvičení - klasická Newtonova metoda funkce: f(x) = 3xj2 + 4x22 - 5xjX2 - 2xl bod: x<°> = (5, 5)T gradient v bodě x(0): g(0) — (óxl — 5x2 - 2, 8x2 — 5xl) = (3, 15) hessian v bodě x(0): (6 -Š\ v-5 8, h(0) = Cvičení - klasická Newtonova metoda funkce: f(x) = 3xj2 + 4x22 - 5xjX2 - 2xl bod: x<°> = (5, 5)T gradient v bodě x(0): g(0) = (6xl — 5x2 — 2, 8x2 — 5xl ) — ^3, 15^ hessian v bodě x(0): (6 -5] h«» = 1-5 SJ inverze hessianu: ( h h(oyl = 22 V D D n ) Cvičení - klasická Newtonova metoda funkce: f(x) = 3xj2 + 4x22 - 5xjX2 - 2xl bod: x<°> = (5, 5)T gradient v bodě x(0): g(0) = (6xl —5x2 — 2, 8x2 — 5xl) — ^3, 15^ hessian v bodě x(0): (6 -5] h«» = 1-5 SJ inverze hessianu: ( h h(oyl = 22 V D D n ) Cvičení - klasická Newtonova metoda funkce: f(x) = 3xT2 + 4x22 - 5x^2 - 2x1 bod: x(°) = (5, 5)T gradient v bodě x(0): g(0) = (óx1 — 5x2 — 2, 8x2 — 5xx ) = (3, 15^ hessian v bodě x(0): (6 -5^ h(0) = 1-5 8) inverze hessiánu: í /z(0)_1 = h 22 bod xd): v D D xm = Í51 v5y (v* 23 5 23 72 D 723 y%3 723 723^ 15) ^99/ \ 23 723 Cvičení - klasická Newtonova metoda Rosenbrockova funkce: f(xlfx2 ) = 100(x2 - x] )2+(l- x, f Výchozí bod: x0 = (-2, 2) Naprogramujte klasickou Newtonovu metodu. Vyzkoušejte pro Rosenbrockovu funkci.