PA081: Programování numerických výpočtů
6. Optimalizace
Aleš Křenek
jaro 2011
Řešený problém
hledání minima funkce f: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ů
2/23
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í
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
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,x, b, jinak s b,x
Metoda zlatého řezu
Určení poměru
► jak vybrat optimálně bod x?
► uvažujme poměry
b - a
w
a tedy
b
w
c — a c — a
► nové x předpokládáme o z dál za b
x - b
a
w
1 - w
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
a b    x c
► nový úsek bude w + z nebo 1 - w
► chceme se vyhnout nejhoršímu případu, položíme tedy
w + z
w
4 □ ► 4 ŕS ► 4 :
Metoda zlatého řezu
Určení poměru
► kde se vzalo w? z dělení ve stejném poměru, tedy
z
■w
1 - w
► dostáváme rovnici w2 - 3w + 1 = 0, tj.
3-V5
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čí
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
7/23
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
► Tayloruv rozvoj
f(x)«f(b) + ±f"(b)(x-b)
a tedy po úpravách
'2\f(b)\
\x - b\ < -Je\b\
b*f"{b)
► velký zkomek je pro „normální" funkce ~ 1
► v x má tedy smysl relativní přesnost jen sjě
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í
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
parabolickou interpolací lze dosáhnout kvadratické konvergence
9/23
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)) 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í prí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
Metoda zlatého řezu
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
11/23
Využití derivací
naivní přístup - řešení f (x) = O
► nerozlíši minimum a maximum, potřebovali bychom ještě
r (x) > o
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
Metoda
sdružených
směrů
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í
► iV-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
Vt = P0 + \et
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
Metoda zlatého řezu
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
14/23
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 vJV-1 rozměrech směrem k nejlepšímu bodu
Simplexová metoda
► kontrakce ve více dimenzích
► ani kontrakce v jednom rozměru nepomohla
simplex se smrskne v N k nejlepšímu bodu
1 rozměrech směrem
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
► kritérium ukončení
► tolerance ~Je 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
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í
► obecně to není tak zlé
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 /(*> = /(P> + X|£*<^XaS
2 rr dxidxi
/(P)-bx + -xAx
kde
b = -V/|p ► potom derivováním
[A](
d2f dxtdxi
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
V/ = Ax-b
18/23
Metoda sdružených směrů
► 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ý
Metoda sdružených směrů
► 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ý
► změna V f ve směru v tedy musí být také kolmá na u
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
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 í = 1,... ,N minimalizujeme z P/_i směrem U/ a získáme tak P/
► přejmenujeme směry U/ <- U/+i (zapomeneme tedy Ui)
► nastavíme Ujv <- Pn - 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
Metoda
sdružených
směrů
20/23
Metoda sdružených směrů
Původní Powellův algoritmus
► začneme s Uí = ei a počátečním bodem Po
postupně pro i = 1,...,N minimalizujeme z Pí i směrem Uí a získáme tak Pí
► přejmenujeme směry Uí <- Uí+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ěrů
Problémy původního algoritmu
► opakované zapomínání Ui postupně vede k lineární závislosti Uí
► metoda se tedy pohybuje jen v podprostoru RN
► při více iteracích spočítá falešné řešení
Metoda sdružených směrů
Problémy původního algoritmu
► opakované zapomínání Ui postupně vede k lineární závislosti Uí
► 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í
Domácí úkol
implementujte vizualizaci postupu optimalizačních metod statické zobrazení grafu funkce animovaný postup kroků metod
► transformace simplexu
► jednotlivé kroky separace minima a vlastní minimalizace po přímce
► vhodná podoba stopy předchozích kroků současné zobrazení více metod pro srovnání
► příště probereme další
implementace numerických metod najdete na ISu
► bude třeba doplnit je o zpětná volání animace odevzdejte funkční kód (Linux/Windows)
► pustíme si na přednášce
► předběžný termín 21.4.2011
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
22/23
Domácí úkol
► možnosti zobrazení
► jen 2D, funkce 2 proměnných, funkční hodnota na škále černá - bílá
► částečně 3D, funkce 2 proměnných, graf jako zakřivená plocha
► plně 3D, funkce 3 proměnných, „graf" jen naznačením významných bodů, postup minimalizace jako pentlička/trubka, barevně kódovaná funkční hodnota
► minimalizované funkce
► analyticky generované, např. deformované elektrostatické pole několika bodových nábojů
/(x)=?|At(x1-b1)l+XAX
Brentova metoda
Simplexová metoda
Metoda
sdružených
směrů
► výškové mapy (např. http: //hrne. sourceforge. net/)
23/23