PA081: Programování numerických výpočtů 6. Optimalizace Aleš Křenek jaro 2012 □ 4 ► < ► 4 * Ř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 Metoda sdružených směrů 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 Metoda sdružených směrů □ (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 Brentova metoda Simplexová metoda Metoda sdružených směrů 5/23 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 Metoda sdružených směrů 6/23 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 Metoda sdružených směrů 9/23 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 □ 4 S ► 4 = > Brentova metoda Simplexová metoda Metoda sdružených směrů 10/23 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 Metoda sdružených směrů 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 Metoda sdružených směrů 13/23 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 Metoda sdružených směrů □ I S ► 4 ■O0.O 14/23 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 PA081: Programování numerických výpočtů A. Křenek Metoda zlatého řezu Brentova metoda Simplexová metoda Metoda sdružených směrů 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 Metoda sdružených směrů kritérium ukončení ► tolerance y/ě 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 □ ► * S ► 4 1 » 4 ž 15/23 Metoda sdružených směrů umíme minimalizovat funkci jedné proměnné minimalizace funkce /(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 + Aminn pokračujeme v jiném směru jádrem metody je stanovení těchto směrů Brentova metoda Simplexová metoda Metoda sdružených směrů 16/23 Metoda sdružených směrů sdružené (konjugované) směry ► následující krok „nepokazí", co jsme získali předchozím ► formulujeme precizněji v souřadném systému s počátkem P lze psát /(x)=/(P) + X|txi + il^^ + ... « /(P) -bx+ ixAx kde b = - V/|p potom derivováním [A] ŕ 52f dxidxj V/ = Ax-b A. Křenek Přehled 4 □ ► 4 ^ * Metoda sdružených směrů Problémy původního algoritmu ► opakované zapomínání ui postupně vede k lineární závislosti Ui ► metoda se tedy pohybuje jen v podprostoru RN při více iteracích spočítá falešné řešení degenerující systém Ui lze nahradit po > 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; Brentova metoda Simplexová metoda Metoda sdružených směrů 21/23 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 ► při vyjádření rotace kvaternionem je třeba silně penalizovat jeho odchylku od jednotkového (molekula by se deformovala) ► odchýlení od této polohy penalizujte modelem vhodně tuhé pružiny F = kAx tj. £=-fe|Ax|2 Domácí úlol libovolná dvojice atomů na sebe působí van der Waalsovou silou, odpovídá energii