Přehled PA081: Programování numerických výpočtů 4. Optimalizace Aleš Křenek jaro 2015 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 Ř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 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 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 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 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 f(x) > f(b), pokračujeme s a, b, x, jinak s b, x, c 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 Metoda zlatého řezu Určení poměru ►•jak vybrat optimálně bod x? ► uvažujme poměry b - a w 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-1-1-h a b x c nový úsek bude w + z nebo 1 - w chceme se vyhnout nejhoršímu případu, položíme tedy w + z = 1 - w 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 Metoda zlatého řezu Určení poměru kde se vzalo w? z dělení ve stejném pomeru, tedy z 1 - w w dostáváme rovnici w2 - 3w + 1 = 0, tj. w = 3^/1 « 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 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 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čí 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 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) + |/" (fc)(x-fc)2 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 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 Brentova metoda ► extrém paraboly procházející body a, b, c (b - a)2(f(b) - f (O) -(b- c)2 (f (b) - f (a) x = b 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 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 Využití derivací naivní přístup - řešení fr (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 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 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í 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 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 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 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 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 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 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 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)\ kde xh, xl jsou nevyšší a nejnižší body simplexu 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 Aproximace parabolou kvadratická funkce v jedné proměnné 1 její derivace f(x) = c + bx + —ax 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 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 Aproximace paraboloidem ► kvadratická funkce více proměnných /(x) = c + bx + t^xAx ► derivace 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ě definitní 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 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 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é) 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 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 Metoda sdružených směrů 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 + Aminn pokračujeme v jiném směru jádrem metody je stanovení těchto směrů 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 nevyvážené vlastní hodnoty matice druhých derivací Metoda sdružených směrů 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ý 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 Metoda sdružených směrů ► v souřadném systému s počátkem P lze psát 1 i,j J /(P)-bx+-xAx kde b = -V/|p [A]y potom derivováním V/ = Ax-b d2f dxidxj 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 Metoda sdružených směrů změna V/ 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/|x = 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 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 Metoda sdružených směrů Původní Powellův algoritmus ► začneme s u; = et a počátečním bodem Po ► postupně pro i = 1,... ,N minimalizujeme z P;_i směrem Uj a získáme tak P; ► přejmenujeme směry u; — Uj+i (zapomeneme tedy ui) ► nastavíme ujv — Pjv - Po ► minimalizujeme směrem ujv a výsledek označíme jako nový Pq 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 Metoda sdružených směrů Původní Powellův algoritmus ► začneme s u; = et a počátečním bodem Po ► postupně pro i = 1,... ,N minimalizujeme z P;_i směrem Uj a získáme tak P; ► přejmenujeme směry u; — Uj+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ů 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 Metoda sdružených směrů Problémy původního algoritmu opakované zapomínání ui postupně vede ke zvyšující se lineární závislosti u; ► 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í 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 Metoda sdružených směrů Problémy původního algoritmu opakované zapomínání ui postupně vede ke zvyšující se lineární závislosti u; ► 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 u; lze nahradit po > N iteracích ► znovu et *■ 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 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 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 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 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 ► ideálně funguje pouze pro nekonečně krátké 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ů h, gi ■ gj: = 0 híAhj = 0 g; ■ h, = 0 pro j < 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ů 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ý ► 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áší čerstwou informaci do sady směrů ► neubývá dimenzí prohledávaného prostoru 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 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 yfe) 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í 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 Newtonovské a seminewtonovské metody ► přímo dostupný Hessián ► velmi speciální případy ► explicitní výpočet Hessiánu je náročný (0(N2)) ► přínost přesného výpočtu diskutabilní ► nejčastěji pro X/i(x)2 ► explicitně udržovaná aproximace Hessiánu ► resp. přímo její inverze ► Davidon-Fletcher-Powell, Broyden-Fletcher-Goldfarb-Shanno ► robustnější - Hessián skutečných funkcí není vždy pozitivně definitní ► výsledky srovnatelné s metodou sdružených gradientů ► detaily viz literatura 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- 1 felAxI 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 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 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 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 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 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 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 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) 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 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é 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 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 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 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í 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 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 /(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 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 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ě 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 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ě přímý sestup p(x - x') 1 když/(x') = { 0 jinak ► vytváří izolované ostrovy ► ve více dimenzích zůstávají únikové cesty ► urychlení konvergence Změny optimalizované funkce Vyhlazování ► cílem je vyhlazení rušivých lokálních minim ► dobře do jde při plné znalosti funkce ► pak ale nepotřebujeme optimalizovat Změny optimalizované funkce Vyhlazování ► cílem je vyhlazení rušivých lokálních minim ► dobře do jde při plné znalosti funkce ► pak ale nepotřebujeme optimalizovat ► řízení přesnosti výpočtu / parametrem a ► s rostoucím a méně detailů začneme s velkým a, výpočet lokálního minima ► postupně a snižujeme, start lokální optimalizace v předchozím výsledku Stochastické tunelování ► modifikace simulovaného žíhání ► náhrada / transformací f'(