PA081: Programování numerických výpočtů 4. Optimalizace Aleš Křenek jaro 2019 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce 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 Klasifikace metod ► globální metody ► fyzikální analogie - simulované žíhání ► změny funkce - stochastické tunelování ► střelba do vrabců ► metody s omezeními ► COBYLA ► L-BFGS-B ► Sequential Quadratic Programing ► ... a spousty dalších 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 6/61 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 = ^1 « 0.38197 ► není-li původní a,b,cw 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 7/61 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, 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 s/ě 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 9/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 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í 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ý, ... 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ý, ... ► 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í 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 13/61 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ů 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 14/61 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 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 \ 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 16/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 ► 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)\ e kde Xh,Xl jsou nevyšší a nejnižší body simplexu Aproximace parabolou ► kvadratická funkce v jedné proměnné 1 f(x) = c + bx + -ax ► její derivace f'(x) = b + ax, f" (x) = a ► známe-li v libovolném xo hodnoty /',/", umíme spočítat a, i> ► řešení /'(x) = 0, tj. x = -bla 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované Aproximace paraboloidem ► kvadratická funkce více proměnných 1 f(x) = c + bx + -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ě deftnitní 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 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 19/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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 19/61 Newtonovské a odvozené metody ► známe-li V/, V2 f a funkce je kvadratická, nalezneme minimum přímo ► funkci postupně aproximujeme paraboloidy ► snažíme se informaci odpovídající V/, V2 f získat ► metody se liší explicitním výpočtem derivací a způsobem udržování této informace 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ů Metoda sdružených směrů ► naivní přístup - souřadné osy ► nevyvážené vlastní hodnoty matice druhých derivací 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ý i P 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 23/61 Metoda sdružených směru ► v souřadném systému s počátkem P lze psát /(x) = /(P) + X Mr*i+ \ X ŤČrír.XiXJ + i i,j 1 J /(P) -bx+ |xAx kde b = -V/ [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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 24/61 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ěrů 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 Metoda sdružených směrů 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ů 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 27/61 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 ► 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; 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" 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 ► xo, xo + pet a jejich kombinace podle vlastností / ► algoritmus pracuje s Lagrangeovými polynomy lj(x) = Cj + gj(x-x0) + -(x-xo)rGj(x-x0) kde Q(x) = X/(x)ij(x) ► v každém kroku minimalizace Q a náhrada jednoho z x* ► 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 30/61 Prof. Powell po 40 letech metody UOBYQA a NEWUOA ► 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 Využití derivací Naivní přístup ► 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 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 32/61 Využití derivací Sdružené gradienty ► posloupnost bodů Pí, gradientů gt a směrů hi gi ■ gj = 0 híAhj = 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 33/61 Využití derivací Sdružené gradienty ► posloupnost bodů Pí, gradientů gt a směrů ht gt ■ gj = 0 hiAh, = 0 gt ■ hj■ = 0 pro j < i ► algoritmus Fetcher-Reeves ► minimalizace z Pí směrem hi, získáme Pi+i ► gí+i :=-V/(Pí+i) ► hi+1 := gi+1 + y^h; kde yí = ► 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce áá/bl Využití derivací Sdružené gradienty ► posloupnost bodů Pj, gradientů gŕ a směrů hj gr ■ gj = 0 híAhj = 0 gi ■ hj = 0 pro j < ► algoritmus Fetcher-Reeves ► minimalizace z Pj směrem hj, získáme Pj+i ► gi+i :=-V/(Pi+i) ► hŕ+1 := gi+1 + yŕhŕ kde yr = ^ff1 ► důkaz pro kvadratickou formu mechanický ► varianta Polak-Ribiere (gi+i " Si) ■ 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce á4/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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce 34/61 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 (N2)) ► přínost přesného výpočtu diskutabilní ► nejčastěji pro X fí (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 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 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce 59/bl 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 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í 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 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ě 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ů Globální optimalizace Základní metoda Simulované žíhání Chlazení a délka kroku Změny optimalizované funkce Shrnutí 41/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ě ► přímý sestup když/(x') t) = 1 f(r)-f(a)