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 Metoda největšího spádu -obecně II – • Algoritmus: •zvolíme výchozí bod x(0) •k-tá iterace: bod x(k+1) vypočítáme z bodu x(k) pomocí vztahu: x(k+1) = x(k) - a.g(k), kde: -g(k) zjednodušený zápis -Ñf(x(k)), určuje směr přesunu z bodu x(k) a koeficient, popisující délku daného přesunu Metoda největšího spádu - volba a v metodě největšího spádu – • Z bodu x(k) se přesunujeme po polopřímce: x(a) = x(k) + a.x(k), kde a > 0 Hodnotu funkce f na této polopřímce popisuje funkce f(a): f(a) = f(x(a)) Je zřejmé, že musíme zvolit takové aOK, aby platilo: f(x(k)) > f(x(k+1)), kde x(k+1) = x(aOK) pro dostatečný počet iterací. Poznámka: „Dostatečný počet“ = dostačuje k tomu, aby metoda konvergovala k minimu ( ). Metoda největšího spádu - volba a v metodě největšího spádu – • Funkce f(a) má následující tvar: Metoda největšího spádu - volba a v metodě největšího spádu – • Metoda největšího spádu volí pro každý krok stejnou hodnotu a. Konkrétně velmi malou hodnotu a. Poznámka: Hodnoty a musí být dostatečně, aby metoda konvergovala. Metoda největšího spádu zhodnocení – • Výhody: •Implementačně jednoduché •Nízká prostorová složitost Nevýhody: •Velmi pomalá konvergence (speciálně v oblastech malého spádu => nízkých hodnot gradientu). •Chyby, způsobené zaokrouhlením. Mohou vést i k tomu, že se výpočet vůbec nedostane rozumně blízko k minimu. Ale při (ideální) přesné aritmetice metoda konverguje vždy k nějakému lokálnímu minimu. Metoda největšího spádu - příklad – • Rosenbrockova funkce: Gradient Rosenbrockovy funkce: Výchozí bod: x0 = (-2, 2) Parametry: a = 0,001 Výpočet první iterace - dobrovolník u tabule :-). Další iterace - příklad v Excelu. Metoda největšího spádu - příklad II – • Ukázka konvergence metody největšího spádu pro Rosenbrockovu funkci: Spádové metody - obecně – • Jsou založeny na stejném principu jako metoda největšího spádu: x(k+1) = x(k) + a.s(k), kde: s(k) je směr přesunu z bodu x(k), nejčastěji jako směr volíme -g(k) a koeficient, popisující délku daného přesunu Využívají sofistikovanější metody k určení koeficientu a. Hodnota koeficientu a je různá pro každou iteraci. Spádové metody - obecně II – • Podmínka pro ideální hodnotu (a*) koeficientu a: funkce f(a) = f(x(a)) má v a* minimum [1] Poznámka: Jedná se o nejmenší hodnotu a, v níž má f(a) minimum. Navíc samozřejmě platí a > 0. Tuto podmínku nelze využít k volbě koeficientu a. Potřebujeme totiž určit hodnotu a pro danou iteraci v konečném a pokud možno velmi malém počtu kroků. Spádové metody - obecně III – • => Nutné podmínky pro koeficient a: 0 < a < a´ [2] Předpokládejme, že funkce f má průběh naznačený na obrázku. Pak existuje a > 0 tak, že: f(x(k) + as(k)) = f(x(k+1)) Nejmenší takové a označujeme a´. Spádové metody - obecně IV – • => Při volbě koeficientu a musíme dodržet podmínky [2] a co nejvíce se přiblížit podmínce [1]. Metody pro nalezení a: •Goldsteinovy podmínky •Wolfe-Powellovy podmínky Značení: budeme značit f(a) budeme značit f(0) Spádové metody - Goldsteinovy podmínky I – • 1. Goldsteinova podmínka zaručuje, že a nebude zvoleno příliš blízko a´: Parametr r je zde pevně zvolené číslo z intervalu (0, ½). I když a´ neexistuje {tj. f(a) < f(0) pro všechna a > 0}, je 1GP schopna omezit volbu a(k). (Pokud je tedy funkce f zdola omezená.) Spádové metody - Goldsteinovy podmínky II – • 2. Goldsteinova podmínka zaručuje, že a nebude zvoleno příliš blízko 0: Pravé strany Goldsteinových podmínek určují dvě přímky se zápornou směrnicí. Hodnoty a1 a a2, které přísluší průsečíkům těchto přímek s f(a), určují interval vhodných hodnot a. Spádové metody - Goldsteinovy podmínky III – • Spádové metody - Goldsteinovy podmínky IV – • Zdůvodnění Goldsteinových podmínek: Spádové metody - Goldsteinovy podmínky V – • Věta: Nechť funkce f je spojitě diferenciovatelná a nechť její gradient g = Ñf je lipschitzovsky spojitý na Rn. Je-li {x(k)} posloupnost generována spádovou metodou a volba a vyhovuje Goldsteinovým podmínkám, pak platí: f(x(k)) – f(x(k-1)) ³ - r.g(k).d(k) kde d(k) = a(k)s(k) = x(k+1) – x(k) => Metoda vždy konverguje k minimu funkce f (pro vhodné r). Poznámka: Volba koeficientu r < ½ zaručuje konvergenci metody pro kvadratické funkce. Spádové metody - Goldsteinovy podmínky VI – • Nevýhoda Goldsteinových podmínek: V intervalu mezi a1 a a2 se nemusí nacházet minimum funkce f(a). Spádové metody - Wolfe-Powellovy podmínky – • Místo GP2 se testuje sklon funkce f(a) v bodě a. Využívá se tedy následující podmínka: kde sÎ(r, 1). Spádové metody - Wolfe-Powellovy podmínky II – • Metody konjugovaných gradientů - obecně •= metody sdružených gradientů •= conjugate gradient method •= speciální případ metod sdružených směrů • •Základní myšlenka: Pro určení směru přesunu z bodu x(k) do bodu x(k+1) se využívají nejen hodnotu g(k+1), ale rovněž hodnotu g(k). (V obecném případě je možno využít hodnot g(1), g(2), ..., g(k), g(k+1).) • •Zdůvodnění: Spojení informací o současném a předchozím sklonu studované funkce umožňuje rychlejší sestup do minima (zlepšení konvergence na plochých oblastech). Metody konjugovaných gradientů - algoritmus •Výpočet x(k+1): • • x(k+1) se určuje pomocí stejného vztahu jako u spádových metod: • x(k+1) = x(k) + a(k).s(k) [2.1] • kde: • s(k) směr přesunu z bodu x(k) • a(k) koeficient, popisující délku daného přesunu • • • Metody konjugovaných gradientů - algoritmus II •Výpočet a(k): • • Analogické jako u spádových metod: • 1) Je nutno zvolit koeficient a(k) tak, aby platilo: •0 < a(k) < a(k)´ • kde: f(x(k) + a(k)´.s(k)) = f(x(k+1)) • 2) a(k) by se měla co nejvíce blížit a(k)*, • kde a(k)* je minimum funkce f(x(k) + a(k).s(k)). • Metody konjugovaných gradientů - algoritmus III •Výpočet s(k+1): • s(k+1) se vypočte pomocí gradientu g(k+1) a směru s(k). (Přičemž s(k) byl vypočítán pomocí předchozích hodnot gradientů ...). Konkrétně: • s(k+1) = -g(k+1) + b(k).s(k) [2.2] • Kde b(k) je koeficient, který určuje míru vlivu směru přesunu v kroku k (s(k)) na směr přesunu v následujícím kroku (s(k+1) ). •Výpočet s(0): • s(0) = -g(0) Metody konjugovaných gradientů - algoritmus III •Výpočet b(k+1): • Existuje více možností, jak volit číslo b(k+1). • Nyní odvodíme hodnotu b(k+1) za předpokladu, že minimalizovaná funkce je kvadratická a má pozitivně definitní Hessovou matici G. V tomto případě platí: • y(k) = G.d(k) [2.3] • kde y(k) = g(k+1) – g(k) a d(k) = x(k+1) – x(k). • Protože vektory s(k+1) a s(k) mají být sdružené vzhledem ke G, musí platit: • s(k+1)T.G.d(k) = 0 [2.4] • Z [2.3] a [2.4] vyplývá: • 0 = s(k+1)T.G.d(k) = s(k+1)T.y(k) Metody konjugovaných gradientů - algoritmus IV •Po transponování rovnice [2.2] a násobení vektorem y(k) zprava dostáváme: • 0 = -g(k+1)T.y(k) + b(k).s(k)T.y(k) [2.5] • •Odtud plyne hodnota, kterou navrhli Hestenes a Stiefel v roce 1952: • • [2.6] • • s(k+1) = -g(k+1) + b(k).s(k) [2.2] Metody konjugovaných gradientů - algoritmus V •Pokud je x(k) v rovnici [2.1] přesně určeným minimem ve směru s(k), musí platit s(k)T.g(k+1) = 0 (jinak by se hodnota f ve směru s(k) dala ještě snížit), obdobně s(k-1)T.g(k) = 0. Pak je jmenovatel ve vztahu [2.6] roven: • • • [2.7] • Metody konjugovaných gradientů - algoritmus VI •Po dosazení [2.7] do [2.6] získáme vyjádření b(k), které poprvé publikovali Polak a Ribiere v roce 1969: • • [2.8] • •Obdobně lze ukázat, že g(k+1)T.g(k) = 0, odtud plyne vztah pro b(k) podle Fletchera a Reevese (1963): Metody konjugovaných gradientů - algoritmus VII • •Pro kvadratické funkce je . • •To ale neplatí pro obecnější funkce. Při testovacích úlohách dává obvykle nejlepší výsledky varianta Polaka a Ribiera. Metody konjugovaných gradientů - zhodnocení •Výhody: • Spolehlivější než spádové metody. • Vhodná i v oblastech poblíž minima • •Nevýhody: • Výpočetně náročnější. • Větší prostorová složitost (nutnost ukládat několik n-prvkových vektorů). Metody konjugovaných gradientů - porovnání •Vhodná i v oblastech poblíž Porovnání metody největšího spádu a metody konjugovaných gradientů (Rosenbrockova funkce): • Metody konjugovaných gradientů - porovnání II – • Ukázka konvergence spádové metody pro Rosenbrockovu funkci: Metody konjugovaných gradientů - porovnání III – • Ukázka konvergence metody konjugovaných gradientů pro Rosenbrockovu funkci: Cvičení •Proveďte první 2 kroky optimalizace funkce: • f(x1, x2) = x12 + 2x22 • • a) pomocí metody největšího spádu • b) pomocí metody konjugovaných gradientů • •Poznámka: Využijte a = 0,25. Počáteční bod je (2,1) • Příloha •Příklad je řešen v přiloženém excelovém souboru „3uncon_metody_prvni_derivace.xlsx“ •