PA081: Programování numerických výpočtů 6. Optimalizace Aleš Křenek jaro 2013 Řešený problém hledání minima funkce /: RN — R ► maximum je minimum -/(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 Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí 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 X/i(x)2 globální metody ► simulované žíhání Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí □ (5 4 : 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 s b, x Metoda zlatého řezu Určení poměru ►•jak vybrat optimálně bod x? ► uvažujme poměry b - a a tedy b 1 - w c — a c — a nové x předpokládáme o z dál za b x - b a w 1 - w + H-h + a b x c nový úsek bude w + z nebo 1 - w chceme se vyhnout nejhoršímu případu, položíme tedy 1 □ s 4 : Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí 5/29 Metoda zlatého řezu Určení poměru kde se vzalo w? z dělení ve stejném poměru, tedy z 1 - w dostáváme rovnici w2 - 3w + 1 = 0, tj. w = « 0.38197 není-li původní a,b,c v tomto poměru, rychle se k němu přiblíží rychlost konvergence jen o málo horší než půlení intervalů ► n + 1. interval je 0.61803 délky n-tého Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí 6/29 Metoda zlatého řezu Počáteční separace ► 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čí Metoda zlatého řezu Kritérium zastavení ► naivní \b - x\ < \b\e ► jsme poblíž minima, / 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) + |/" a tedy po úpravách ► velký zkomek je pro „normální" funkce ~ 1 ► v x má tedy smysl relativní přesnost jen -Jě 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í parabolickou interpolací lze dosáhnout kvadratické konvergence Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí 9/29 Brentova metoda extrém paraboly procházející body a, b, c x b (b - a)Hf(b) - f (c)) -(b- c)2(f(b) - f (a) 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 Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí 10/29 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ý, ... Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí 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í Simplexová metoda ► také améba, resp. Nelder-Mead ► nevyžaduje derivace, robustní vůči singularitám apod. ► jednoduchá implementace ► nepříliš efektivní Simplexová metoda ► také améba, resp. Nelder-Mead ► nevyžaduje derivace, robustní vůči singularitám apod. ► jednoduchá implementace ► nepříliš efektivní ► JV-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ů Simplexová metoda počáteční odhad minima Po, definujeme další body simplexu Pr = P0 + Aer kde A odpovídá měřítku problému reflexe ► nejvyšší bod simplexu (podle /) promítneme symetricky podle protilehlé stěny Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí 13/29 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 Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí □ i ► 4 : 14/29 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 Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí 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 kritérium ukončení ► tolerance yfě 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)\ < e kde xh, xl jsou nevyšší a nejnižší body simplexu □ ► N iteracích ► znovu e; ► 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; 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" Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí Využití derivací Naivní přístup ► vedle funkčních hodnot umíme spočítat i gradient V/ ► 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 Využití derivací Naivní přístup ► vedle funkčních hodnot umíme spočítat i gradient V/ ► 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 ► v jednom kroku netrefíme dno údolí přesně ► další musí být kolmo Využití derivací Sdružené gradienty ► posloupnost bodů Pí, gradientů gt a směrů hj gi ■ gj: = 0 hiAhj = 0 g; ■ hj = 0 pro j < i Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí Využití derivací Sdružené gradienty ► posloupnost bodů Pí, gradientů gŕ a směrů hi gr ■ gj: = 0 hiAhj = 0 gr ■ hj: = 0 pro j < ► algoritmus Fetcher-Reeves ► minimalizace z P; směrem h;, získáme Pj+i ► Si+i ■= -V/(Pi+1) ► hi+1 := gi+1 + yŕhŕ kde yr = ^íl|±í ► důkaz pro kvadratickou formu mechanický Využití derivací Sdružené gradienty ► posloupnost bodů Pí, gradientů gŕ a směrů hí gr ■ gj: = 0 hiAhj = 0 gr ■ hj: = 0 pro j < ► algoritmus Fetcher-Reeves ► minimalizace z P; směrem h;, získáme Pj+i ► Si+i ■= -V/(Pi+1) ► hi+1 := gi+1 + yŕhŕ kde yr = ► důkaz pro kvadratickou formu mechanický ► varianta Polak-Ribiere „ _ (Si+i-Si) ■ Ei+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? menší sklon k degeneraci ► použití gradientu vnáší čerstou informaci do sady směrů ► neubývá dimenzí prohledávaného prostoru Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí Využití derivací Má to smysl? ► menší sklon k degeneraci ► použití gradientu vnáší čerstou 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 Domácí úkol PA081: Programování numerických výpočtů Vybranou minimalizační metodou implementujte jednoduchý model interakce dvou molekul. ► je dána cílová poloha - energetické minimum (pdb) ► při vyjádření rotace kvaternionem je třeba silně Domácí penalizovat jeho odchylku od jednotkového (molekula by se deformovala) ► odchýlení od cílové polohy penalizujte modelem vhodně tuhé pružiny 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 Brentova metoda Simplexová metoda Metody sdružených směrů ■O0.O Domácí úkol libovolná dvojice atomů na sebe působí van der Waalsovou silou, odpovídá energii 12 -12 kde r je vzálenost atomů. Působí mírně přitažlivě na dálku, silně odpudivě na blízko. Použijte realistické a = 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 Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí □ 4 ► 4 š ► < -E ► 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 Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí Shrnutí hledání minima funkcí jedné nebo více proměnných jednorozměrné metody ► zlatý řez - odpovídá půlení intervalu pro řešení rovnic ► Brentova metoda (přímá analogie řešení rovnic) ► v ID nemá příliš smysl používat derivace ► základ vícerozměrných optimalizací vícerozměrné metody ► jednoduchá simplexová ► sdružené směry bez i s derivacemi (Powell, Fletcher-Reeves) ► (semi)newtonovské metody (Hessián) více viz PV027 Optimalizace Brentova metoda Simplexová metoda Metody sdružených směrů Domácí úkol Shrnutí □ & 4 : ■OQ.O 29/29