PA081: Programování numerických výpočtů 4. Optimalizace Aleš Křenek jaro 2016 PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 1/61 Řešený problém ► hledání minima funkce f:RN^R ► maximum je minimum -f(x), speciálně neřešíme ► standardní metody hledají (nejbližší) lokální minimum ► potřebujeme znát vlastnosti funkce a mít dobrý počáteční odhad ► existují i rozšíření na globální minima ► celkově příjemnější problém než řešení rovnic ► především ve více dimenzích ► stačí „jít směrem dolů" a minimum najdeme (kořen ne) ► žádná univerzální metoda opět neexistuje PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 2/61 Klasifikace metod ► ► ► ► ► ► ► jednorozměrné metody zlatý řez - robustní, relativně pomalá Brentova - interpolace parabolou využití derivací je v ID diskutabilní většina vícerozměrných metod využívá jednorozměrné ► vícerozměrné metody simplex (améba) - jednoduchá a robustní, pomalá sdružené směry (Powell) - bez derivací, kvadratická konvergence ► sdružené gradienty (Polak-Ribiere, Fletcher-Reeves) -s derivacemi ► seminewtonovské (Davidon-Fletcher-Powell, Broyden-Fletcher-Goldfarb-Shanno) - s derivacemi, postupná aproximace druhých derivací ► newtonovské - s explicitními druhými derivacemi, vhodné pro S/í(x)2 ► globální metody ► simulované žíhání PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované á/bl Metoda zlatého řezu ► analogie metody půlení intervalu pro řešení rovnic ► podobný pojem separace minima ► spojitá funkce /, trojice bodů a < b < c, platí f (a) > f(b) a zároveň f(b) < f(c) potom / má v intervalu [a, c] lokální minimum ► vybereme nový bod x např. z (b, c) ► je-li/(x) > f(b), pokračujeme s a, b,x, jinak sb,x,c Metoda zlatého řezu Určení poměru ► jak vybrat optimálně bod x? ► uvažujme poměry b - a c - a = w a tedy c - b c - a = 1 - w nové x předpokládáme o z dál za b x - b c - a = z w 1 - w a b x ► nový úsek bude w + z nebo 1 - w ► chceme se vyhnout nejhoršímu případu, položíme tedy w + z = 1 - w PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 5/bl Metoda zlatého řezu Určení poměru PA081: Programování numerických výpočtů A. Křenek ► kde se vzalo w? z dělení ve stejném poměru, tedy 1 - w = w ► dostáváme rovnici w2 - 3w + 1 = 0, tj. w = 3-v5 0.38197 ► není-li původní a, b, c v tomto poměru, rychle se k němu priblíži ► rychlost konvergence jen o málo horší než půlení intervalů ► n + 1. interval je 0.61803 délky n-tého Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované b/bl Metoda zlatého řezu Počáteční separace PA081: Programování numerických výpočtů A. Křenek ► nevíme-li nic lepšího, začneme z libovolné dvojice a, b ► pokračujeme směrem „dolů" podle f(a),f(b) ► kroky prodlužujeme konstantním faktorem, ► lze využít kvadratickou inter/extrapolaci ► rychlejší postup a přesnější výsledek pro „hezké" funkce ► viz Brentova metoda ► má-li funkce globální minimum, musíme narazit na místo, kde se otočí Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 7/bl Metoda zlatého řezu Kritérium zastavení ► naivní |b - x\ < \b\e ► jsme poblíž minima, f je skoro plochá ► musíme aplikovat na funční hodnoty, tj. \f(b)-f(x)\ < \f(b)\e ► Taylorův rozvoj f(x)*f(b) + -f"(b)(x-b)2 a tedy po úpravách x - bI < Je\b 2\f(b)\ b2f"(b) ► velký zkomek je pro „normální" funkce ~ 1 ► v x má tedy smysl relativní přesnost jen ^[e PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 8/61 Brentova metoda ► analogie metody pro řešení rovnic ► v okolí minima lze funkci dobře aproximovat parabolou ► ► optimistická hypotéza platí pro mnoho reálně používaných funkcí \ \v ■ • • • / 1 v (p % •\\ • ■ • M ■ / / i f 1 1 / / / / / v •v W / Jaj .*— ► parabolickou interpolací lze dosáhnout kvadratické konvergence PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 9/61 Brentova metoda ► extrém paraboly procházející body a, b, c (b- a)2(f(b) - f (c)) -(b- c)2(f(b) - f (a)) X 2«b - a)(f(b) - f (c)) -(b- c)(f(b) - f (a))) ► možné problémy ► vzorec najde maximum ► jmenovatel je nulový nebo blízký nule ► x zabloudí příliš daleko ► metoda problémy detekuje a vrací se k bezpečnému zlatému řezu ► důsledně zachovává separaci minima ► detaily viz literatura Využití derivací ► naivní přístup - řešení f (x) = O ► nerozlíši minimum a maximum, potřebovali bychom ještě f"(x)>0 ► derivace nesouvisí přímo s bezpečnou separací ► v jednom nebo obou krajních bodech může být směr „dolů" zároveň „ven" ► derivace lze využít k přesnější aproximaci funkce ► v jednom iteračním kroku se lépe přiblížíme skutečnému minimu ► zlatý řez lineární, Brent kvadratický, ... PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 11/61 Využití derivací ► naivní přístup - řešení f'(x) = O ► nerozlíši minimum a maximum, potřebovali bychom ještě f"(x) >0 ► derivace nesouvisí přímo s bezpečnou separací ► v jednom nebo obou krajních bodech může být směr „dolů" zároveň „ven" ► derivace lze využít k přesnější aproximaci funkce ► v jednom iteračním kroku se lépe přiblížíme skutečnému minimu ► zlatý řez lineární, Brent kvadratický, ... ► nemusí přinést očekávaný výsledek ► polynom nepostihne exponenciální charakteristiky funkcí ► výpočet derivací je zpravidla zatížen větší chybou ► celkově diskutabilní přínos ► cena za vyhodnocení derivace je větší než potenciální zrychlení a zpřesnění výpočtu ► zejména v případě hledání po přímce, kde reálně potřebujeme N parciálních derivací PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 11/61 Simplexová metoda PA081: Programování numerických výpočtů A. Křenek ► také améba, resp. Nelder-Mead ► nevyžaduje derivace, robustní vůči singularitám apod. jednoduchá implementace nepříliš efektivní Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované IZ/bl Simplexová metoda ► také améba, resp. Nelder-Mead ► nevyžaduje derivace, robustní vůči singularitám apod. ► jednoduchá implementace ► nepříliš efektivní ► AT-rozměrný simplex je konvexní lineární „těleso" definované N + 1 body ► ► trojúhelník, čtyřstěn, ... ► metoda nechává simplex „plazit se" po funkční hyperploše dolů PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované IZ/bl Simplexová metoda ► počáteční odhad minima Po, definujeme další body simplexu Pí = Po + Xet kde A odpovídá měřítku problému ► reflexe ► nejvyšší bod simplexu (podle /) promítneme symetricky podle protilehlé stěny PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované lá/bl Simplexová metoda ► expanze ► je-li výsledek reflexe lepší než nejnižší předchozí bod ► zkusíme protáhnout simplex na dvojnásobnou délku slibným směrem ► kontrakce ► v případě, kdy reflexe nepomohla ► simplex se smrskne v jednom rozměru od nejvyššího bodu PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 14/61 Simplexová metoda ► kontrakce ve více dimenzích ► ani kontrakce v jednom rozměru nepomohla ► simplex se smrskne v N - 1 rozměrech směrem k nejlepšímu bodu A 'I \ PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 15/61 Simplexová metoda ► kontrakce ve více dimenzích ► ani kontrakce v jednom rozměru nepomohla ► simplex se smrskne v N - 1 rozměrech směrem k nejlepšímu bodu A 'I \ ► kritérium ukončení ► tolerance Vě v nezávislých proměnných, e ve funkčních hodnotách, viz úvahy o jednorozměrném případě ► v praxi 2(f(xH)-f(xL)) \f(xH)\ + \f(xL) < € kde Xh,Xl jsou nevyšší a nejnižší body simplexu PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 15/61 Aproximace parabolou kvadratická funkce v jedné proměnné f(x) = c + bx + —ax její derivace f'(x) = b + ax, f"(x) = a ► známe-li v libovolném xq hodnoty f',f", umíme spočítat a, b ► řešení f'(x) = 0, tj. x = -b/a je minimum / ► za předpokladu a > 0 PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 16/61 Aproximace paraboloidem kvadratická funkce více proměnných ► derivace f(x) = c + bx + -xAx V/ = b + Ax, V2/ = A ► známe-li v libovélném xo hodnoty V/, V2/, umíme spočítat A, b ► řešením Ax = -b získáme minimum ► je-li A pozitivně deftnitní PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 17/61 Vlastnosti dané Hessiánem ► matice druhých parciálních derivací ► v případě kvadratické formy konstantní ► znaménka vlastních hodnot všechny kladné - minimum všechny záporné - maximum ► ► ► mix - sedlo PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 18/61 Vlastnosti dané Hessiánem ► matice druhých parciálních derivací ► v případě kvadratické formy konstantní ► znaménka vlastních hodnot ► všechny kladné - minimum ► všechny záporné - maximum ► mix - sedlo ► velikost vlastních hodnot ► deformace základního tvaru PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 18/61 Vlastnosti dané Hessiánem ► matice druhých parciálních derivací ► v případě kvadratické formy konstantní ► znaménka vlastních hodnot ► všechny kladné - minimum ► všechny záporné - maximum ► mix - sedlo ► velikost vlastních hodnot ► deformace základního tvaru ► vlastní vektory ► rotace základního tvaru ► (u symetrické matice jsou kolmé) PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 18/61 Newtonovské a odvozené metody ► známe-li V/, V2/ a funkce je kvadratická, nalezneme minimum přímo ► funkci postupně aproximujeme paraboloidy ► snažíme se informaci odpovídající V/, V2/ získat ► metody se liší explicitním výpočtem derivací a způsobem udržování této informace PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 19/61 Metoda sdružených směru ► umíme minimalizovat funkci jedné proměnné ► minimalizace funkce f(x) více proměnných z bodu P ve směru n je minimalizace /(P + An) v jedné proměnné A ► postupně volíme směry n ► bod P nahradíme minimem v tomto směru, tj. P + Aminii ► pokračujeme v jiném směru ► jádrem metody je stanovení těchto směrů PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 2.0/bl Metoda sdružených směru naivní přístup - souřadné osy nevyvážené vlastní hodnoty matice druhých derivací PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované Metoda sdružených směru ► následující krok „nepokazí", co jsme získali předchozím ► předpokládejme, že směrem u jsme minimalizovali ► v tomto bodě je V f kolmý k u (tj. V/u = 0) ► chceme se vydat dál jen takovým směrem v, že V f zůstane k u kolmý PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované r-j r-j /ri Metoda sdružených směru v souřadném systému s počátkem P lze psát 1 « /(P) - bx + -xAx kde b = -Vf [A] y - d2f dXidXj potom derivováním V f = Ax - b PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované Metoda sdružených směrů ► změna V f ve směru v tedy musí být také kolmá na u ► pro N = 2 znamená zachování směru V/ ► pro N > 3 je bohatší V/lx+v - V/lx = A(x + v)-b-Ax + b = Av ► stačí tedy vyžadovat uAv = 0 ► postupná minimalizace v N lineárně nezávislých sdružených směrech přesně minimalizuje kvadratickou formu Metoda sdružených směru Původní Powellův algoritmus ► začneme s ut = ^ a počátečním bodem Po ► postupně pro i = 1,..., N minimalizujeme z Pj_i směrem Ut a získáme tak Pí ► přejmenujeme směry <- Ui+i (zapomeneme tedy ui) ► nastavíme Ujv <- Pjv - Po ► minimalizujeme směrem Ujv a výsledek označíme jako nový Po PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 2.5/bl Metoda sdružených směru Původní Powellův algoritmus ► začneme s ut = ^ a počátečním bodem Po ► postupně pro i = 1,..., N minimalizujeme z Pj_i směrem Ut a získáme tak Pí ► přejmenujeme směry <- Ui+i (zapomeneme tedy ui) ► nastavíme Ujv <- Pjv - Po ► minimalizujeme směrem Ujv a výsledek označíme jako nový Po ► lze ukázat (Powell, 1964), že k opakování vygeneruje k sdružených směrů PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 2.5/bl Metoda sdružených směru Problémy původního algoritmu ► opakované zapomínání ui postupně vede ke zvyšující se lineární závislosti ► v numerickém smyslu, algebraicky v pořádku ► metoda se tedy pohybuje jen v podprostoru RN ► při více iteracích spočítá falešné řešení PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované Metoda sdružených směru Problémy původního algoritmu ► opakované zapomínání ui postupně vede ke zvyšující se lineární závislosti ► v numerickém smyslu, algebraicky v pořádku ► metoda se tedy pohybuje jen v podprostoru RN ► při více iteracích spočítá falešné řešení ► degenerující systém lze nahradit po > N iteracích ► znovu ei ► vlastními vektory A, je-li k dispozici ► nezapomínat vždy ui, ale ten směr, kterým jsme nevíce získali ► odpovídá dosažení dna údolí ► naruší striktní udržování sdruženosti směrů ► je třeba kompenzovat - v jistých případech se ponechá původní sada u; PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované Ukázka chování algoritmu ► molekula cyklohexanu, v počáteční konformaci „židlička" ► násilím ji zdeformujeme vychýlením jednoho atomu ► minimalizujeme funkci „ošklivosti" ► vyjádřena jako odchylky délek vazeb a úhlů mezi sousedními vazbami ► přibližně odpovídá potenciální energii ► zpětná volání z minimalizační funkce ► vizualizace chování metody minimalizace ► dvě varianty ► zafixovaný vychýlený atom, polohu hledají jen dva další ► uvolněný i vychýlený atom, vrátí se zpět nebo do „lodičky" PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 27/61 Prof. Powell po 40 letech metody UOBYQA a NEWUOA ► metoda sdružených směrů pracuje s parabolickou aproximací implicitně ► n minimalizací po přímce dosáhne minima paraboloidu ► alternativou je explicitní aproximace paraboloidem ► analogie Brentovy metody v ID ► vyjádření kvadratickou formou q(x) = c + g^(x-x0) + -(x-x0)tGq(x-x0) ► gQ a Gq jsou 1. a 2. parciální derivace ► celkem m = 1 + n+ \n2 koeficientů ► k jednoznačné aproximaci potřebujeme m nezávislých vyhodnocení / Prof. Powell po 40 letech metody UOBYQA a NEWUOA ► stanovíme m bodů počáteční aproximace xi ► xo, xo + pet a jejich kombinace podle vlastností / ► algoritmus pracuje s Lagrangeovými polynomy lj(x) = Cj + gj(x-x0) + -(x-x0)rGj(x-x0) kde Q(x) = X/(x)ij(x) j ► v každém kroku minimalizace Q a náhrada jednoho z xt ► není třeba přepočítávat všechny Lagrangeovy polynomy ► komplikovaný algoritmus rozhodování o detailech dalšího kroku ► viz Powell M. J. D. (2002). UOBYQA: unconstrained optimization by quadratic approximation. PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce 29/61 Prof. Powell po 40 letech metody UOBYQA a NEWUOA PA081: Programování numerických výpočtů A. Křenek ► ► ► funguje dobře pro problémy do cca. n = 20 ► m = 1 + n+\n2 bodů aproximace přestává být praktické ► metoda NEWUOA používá omezený počet bodů odhadu, typicky 2n + 1 chybějící stupně volnosti „dohání" minimalizací V2Qfc-V2Qfc_i ► v praxi funguje velmi dobře ► formulace algoritmu dovoluje i snadné zahrnutí lineárních omezení ► viz Powell, M. J. D. (2004). Least Frobenius norm updating of quadratic models that satisfy interpolation conditions Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované áO/bl Využití derivací Naivní přístup PA081: Programování numerických výpočtů A. Křenek ► vedle funkčních hodnot umíme spočítat i gradient V f ► metoda největšího spádu ► vektor - V/ určuje směr „dolů" ► tímto směrem minimalizujeme ► v dalším kroku se vydáme opět po gradientu Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované ál/bl Využití derivací Naivní přístup PA081: Programování numerických výpočtů A. Křenek ► vedle funkčních hodnot umíme spočítat i gradient V f ► metoda největšího spádu ► vektor - V/ určuje směr „dolů" ► tímto směrem minimalizujeme ► v dalším kroku se vydáme opět po gradientu ► stejné riziko postupu velmi krátkými kroky ► ideálně funguje pouze pro nekonečně krátké kroky ► v jednom kroku netrefíme dno údolí přesně ► další musí být kolmo Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované ál/bl Využití derivací Sdružené gradienty ► posloupnost bodů Pj, gradientů gt a směrů h; gi ■ gj = 0 hjAhj = 0 gi ■ hj = 0 pro j < í PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 32/61 Využití derivací Sdružené gradienty ► posloupnost bodů Pí, gradientů gt a směrů h; gt ■ gj = 0 hiAh, = 0 gt ■ hj■ = 0 pro j < i ► algoritmus Fetcher-Reeves ► minimalizace z Pí směrem hi, získáme Pí+i ► gí+i :=-V/(Pí+i) ► hi+i := gi+1 + y^hi kde _ gj+i-gj+i gi-gi důkaz pro kvadratickou formu mechanický PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované Využití derivací Sdružené gradienty ► posloupnost bodů Pí, gradientů gt a směrů h; gt ■ gj = 0 hiAh, = 0 gt ■ hj■ = 0 pro j < ► algoritmus Fetcher-Reeves ► minimalizace z Pí směrem hi, získáme Pi+i ► gí+i :=-V/(Pí+i) ► hi+i := gi+1 + y^hi kde y; = gi^;^+1 ► důkaz pro kvadratickou formu mechanický ► varianta Polak-Ribiere (gi+i -gi) ■ gi+i ► pro kvadratickou formu ekvivalentní ► empiricky lepší výsledky pro složitější funkce ► když dojde dech, vrací se ke gradientům Využití derivací Má to smysl? PA081: Programování numerických výpočtů A. Křenek ► menší sklon k degeneraci ► použití gradientu vnáší čerstwou informaci do sady směrů ► neubývá dimenzí prohledávaného prostoru Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované áá/bl Využití derivací Má to smysl? ► menší sklon k degeneraci ► použití gradientu vnáší čerstwou informaci do sady směrů ► neubývá dimenzí prohledávaného prostoru ► Powellova metoda potřebuje N2 minimalizací v ID ► minimalizace v ID cca. 5-10 vyhodnocení funkce (kvadratická konvergence, přesnost Je) ► Fletcher-Reeves - stačí N kroků ► lx minimalizace v ID ► výpočet N parciálních derivací ► derivace mohou recyklovat společné podvýrazy ► stejná asymptotická složitost, menší celkový počet operací PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované áá/bl Newtonovské a seminewtonovské metody ► přímo dostupný Hessián velmi speciální případy ► ► ► ► explicitní výpočet Hessiánu je náročný (O(AT2)) přínost přesného výpočtu diskutabilní nejčastěji pro S/i(x)2 ► explicitně udržovaná aproximace Hessiánu ■ ■ r ► resp. pnmo její inverze ► Davidon-Fletcher-Powell, Broyden-Fletcher-Goldfarb-Shanno ► robustnější - Hessián skutečných funkcí není vždy pozitivně deftnitní ► výsledky srovnatelné s metodou sdružených gradientů ► detaily viz literatura PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 34/61 Domácí úkol Vybranou minimalizační metodou implementujte jednoduchý model interakce dvou molekul. ► je dána cílová poloha - energetické minimum (pdb) ► volné proměnné pro minimalizaci: ► vektor polohy x - molekula se může volně pohybovat ► vyjádření rotace - tři úhly nebo kvaternion ► minimalizovat začínáme z vychýlené polohy ► při vyjádření rotace kvaternionem je třeba silně penalizovat jeho odchylku od jednotkového (molekula by se deformovala) ► odchýlení od cílové polohy penalizujte modelem vhodně tuhé pružiny F = kAx tj. £ = -fe|Ax|2 j 2 PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované á5/bl Domácí úkol ► libovolná dvojice atomů na sebe působí van der Waalsovou silou, odpovídá energii E = a 12 CT 6 r 12 r 6 kde r je vzálenost atomů. Působí mírně přitažlivě na dálku, silně odpudivě na blízko. Použijte realistické cr = 2.7 ► pro vizualizaci použijte VMD http://www.ks.ui uc.edu/Research/vmd/ ► připojení k serveru příkazem „imd connect hostname port" ► implementaci serveru použijte z ukázkového příkladu PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované áb/bl Domácí úkol ► přijďte se zeptat, nebudete-li si vědět rady ► můžete si vymyslet i jiný obdobně složitý příklad ► kvalitní implementace - zápočet nebo 2 body ke zkoušce PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované á//ol Globální optimalizace ► popsané metody směřují k nějakému lokálnímu minimu ► to ale nemusí být řešení, které chceme ► mnoho reálných problémů ► ne vždy víme, kde začít hledat ► globální metody - jak se dostat k nejlepšímu minimu ► místo sestupu potřebujeme dynamiku PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované áo/bl Přesná řešení ► systematické prohledání stavového prostoru ► případně heuristické metody ► vhodné pro diskrétní problémy, ve spojitém případě problematické ► ► diskrétní vzorkování každé proměnné i při malém počtu příliš náročné (MN) PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované á9/bl Heuristiky ► technika řešení problému postavená na více či méně naivním očekávání ► sledování gradientu ► náhodné vzorkování ► ► negarantuje nalezení optimálního řešení s vysokou pravděpodobností přijatelné řešení v přijatelném čase PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 40/61 Heuristiky ► Monte Carlo ► Las Vegas ► Macao PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 41/61 Heuristiky ► Monte Carlo ► vede k výsledku jen s jistou pravděpodobností ► deterministická délka výpočtu ► Las Vegas ► vždy vede k výsledku ► délka výpočtu záleží na průběhu náhodných čísel ► Macao ► vždy vede k výsledku ► deterministická délka výpočtu PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 41/61 Základní algoritmus ► pracujeme s jedním konkrétním stavem x ► vygenerujeme jednoho nebo více kandidátů x' = x + Ax ► v těchto bodech vypočteme hodnotu cílové funkce f (x) ► podle nějakého kritéria rozhodneme o přijetí nebo odmítnutí kandidáta PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 42/61 Základní algoritmus ► pracujeme s jedním konkrétním stavem x ► vygenerujeme jednoho nebo více kandidátů x' = x + Ax ► v těchto bodech vypočteme hodnotu cílové funkce f (x) ► podle nějakého kritéria rozhodneme o přijetí nebo odmítnutí kandidáta ► konkrétní metody se liší strategií (heuristikami) ► volba směru a velikosti kroku ► kritérium rozhodnutí o přijetí ► průběžné modifikace parametrů těchto strategií PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 42/61 Základní algoritmus ► pracujeme s jedním konkrétním stavem x ► vygenerujeme jednoho nebo více kandidátů x' = x + Ax ► v těchto bodech vypočteme hodnotu cílové funkce f (x) ► podle nějakého kritéria rozhodneme o přijetí nebo odmítnutí kandidáta ► konkrétní metody se liší strategií (heuristikami) ► volba směru a velikosti kroku ► kritérium rozhodnutí o přijetí ► průběžné modifikace parametrů těchto strategií ► dělení podle použití paměti čistě Markovovské - nepamatují si nic ► ► ► využívající historie různé délky seznamy tabu PA081: Programování numerických výpočtů A. Křenek Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 42/61 Triviální strategie přijetí PA081: Programování numerických výpočtů A. Křenek náhodná procházka: p(x — x') = 1 ► má smysl v kombinaci s propracovanější strategií volby kroku ► funguje dobře pro problémy typu golfového hřiště Přehled Metoda zlatého řezu Brentova metoda Simplexová metoda Newtonovské metody Metody sdružených směrů Domácí úkol Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované 43/61 Triviální strategie přijetí ► náhodná procházka: p(x — x') = 1 ► má smysl v kombinaci s propracovanější strategií volby kroku ► funguje dobře pro problémy typu golfového hřiště primy sestup p(x — x') = 1 když/(x')