Optimalizace bez omezení (unconstraint) Nederivační (ad hoc) metody Jednoduché metody Nelder-Meadova (simplexová) metoda Derivační metody První derivace Metoda největšího spádu + další spádové metody Metoda konjugovaných gradientů Druhá derivace Newton-Raphsonova metoda Quasi-Newtonova metoda Jednoduché metody Nejstarší z optimalizačních metod. Některé nejsou podloženy matematickou teorií, ostatní mají velmi jednoduchý princip. Konkrétně: • Postupná optimalizace proměnných • Systematické prohledávání • Náhodnostní metoda • Metoda alternujících proměnných Jednoduché metody - postupná optimalizace proměnných Jedna z nejstarších optimalizačních metod (označována také „naivní metoda“ :-). Princip: Nejdříve nalezne minimum první proměnné (hodnoty ostatních proměnných se nemění). Původní hodnotu této proměnné nahradí nově nalezenou hodnotou. Analogicky jsou optimalizovány další proměnné. Zhodnocení: Metoda je použitelná pouze v některých případech: funkce 2 nebo 3 proměnných + vhodný tvar funkce. V součastnosti se tato metoda již nevyužívá. Jednoduché metody - systematické prohledávání Anglicky označována grid search. Princip: Rozdělí vícerozměrný prostor, nad kterým je funkce definována na části pomocí vícerozměrné mřížky. Vypočítá pro každou část funkční hodnoty. Projde všechny funkční hodnoty a nalezne nejmenší z nich. V některých implementacích této metody analogickým způsobem prohledá okolí minima, nalezeného v předchozím kroku atd. Jednoduché metody - systematické prohledávání Zhodnocení: Výhody: Spolehlivá metoda. Dnes se využívá pro hledání globálních extrémů případně pro nalezení všech extrémů v určité oblasti. Nevýhody: Složitost q(P1.P2. ... .PN), kde Pi je počet dílů mřížky pro i-tou proměnnou a N je rozměr prostoru, nad kterým je studovaná funkce definována. Jednoduché metody - náhodnostní metoda Princip: V rámci každého kroku výpočtu je vypočítáno mnoho hodnot studované funkce pro náhodně vybrané hodnoty proměnných (tyto hodnoty jsou ovšem náhodně vybrány z určitého regionu). Poté je nalezena nejmenší hodnota funkce a ta se stane středem nového regionu (který má menší rozměry než původní region). Zhodnocení: Použitelné, ale pouze při dostatečně velkém počtu vypočítaných funkčnch hodnot v každém kroku. Nevýhodou je velká složitost metody. Jednoduché metody - metoda alternujících proměnných Anglicky označována alternating variables method. Princip: V iteraci k (k = 1, 2, ..., N*) se mění (je optimalizována) pouze proměnná xk, ostatní proměnné jsou ponechány. Poznámka: Proměnná xk je optimalizována např. tak, že jsou vypočítány hodnoty xk´ = xk+dx a xk = xk-dx, poté hodnoty f(x1, ..., xk´, ..., xN) a f(x1, ..., xk, ..., xN), a pak je pro další iteraci za xk použito nejvhodnější z xk´ a xk Po proběhnutí iterací 1 ... N, když jsou všechny hodnoty optimalizovány, se celý cyklus opakuje znovu (až do splnění podmínek minima). * N je dimenze prostoru, nad kterým je funkce definována. Jednoduché metody - metoda alternujících proměnných II Zhodnocení: Výhody: Jednoduchá implementace. Rozumná složitost. Nevýhody: V některých případech je tato metoda velmi neefektivní. Postup optimalizace je v těchto případech charakterizován oscilačním průběhem (viz následující obrázek). Navíc je znám problém (viz Practical methods of optimization), pro který metoda chybně konverguje k sedlovému bodu. Jednoduché metody - metoda alternujících proměnných III Příklad pomalé konvergence metody: Nelder-Meadova metoda - obecně Nazývá se také simplexová metoda. Základní myšlenka: N-rozměrným prostorem se pohybuje jistý objekt („améba“), který se může natahovat nebo zkracovat v různých směrech. Několik typů takových transformací má zajistit, aby se objekt posouval směrem do „údolí“ a po dosažení dna údolí se „plazil“ co nejkratší cestou k lokálnímu minimu. Nelder-Meadova metoda - obecně II Simplex: V N-rozměrném prostoru je „améba“ definována jako simplex s N+1 vrcholy s neprázdným obsahem, tj. jde o konvexní obal tvořený N+1 body. Zápis simplexu: S = {p1, p2, ..., pN+1}, kde pi  RN Příklady simplexů: R: R2: R3: Nelder-Meadova metoda - transformace Reflexe: Bod pi, který má největší funkční hodnotu se přemístí (odzrcadlí) na druhou stranu simplexu, tj. k bodu pi se přičte dvojnásobek rozdílu mezi pi a průměrem ostatních bodů .( ) p n j i j   Nelder-Meadova metoda - transformace II Reflexe a prodloužení: Totéž jako v předchozím případě, až na to, že simplex je prodloužen v novém směru (tj. přičítá se více než dvojnásobek rozdílu mezi nejhorším bodem a průměrem ostatních). Nelder-Meadova metoda - transformace III Kontrakce: Nejhorší bod se přiblíží k průměru ostatních. To je vhodné v případě, kdy má „améba“ projít úzkým údolím. Nelder-Meadova metoda - začátek výpočtu Na začátku výpočtu se simplex nejčastěji definuje takto: kde: i = 1, ..., N p0 pevně zvolený (počáteční) bod ei jednotkové vektory l konstanta, odrážející odhad měřítka optimalizačního problému (např. šířku „údolí“) p p ei 0 i= + l Nelder-Meadova metoda - ukončení výpočtu Metoda končí, pokud: – Není dosaženo výrazného snížení hodnoty studované funkce – simplex se v některém cyklu prakticky nezmění Nelder-Meadova metoda - zhodnocení Výhody: – Jednoduchá implementace – Rychlý výpočet 1 iterace – Rychlá konvergence v oblastech daleko od minima Nevýhody: – Pomalá konvergence v oblastech poblíž minima – Může nastat situace, že výpočet neskončí v lokálním minimu Nelder-Meadova metoda - příklad aplikace