Toto cvičenie sa zaoberá hľadaním extrému funkcie jednej a viac premenných. Táto procedúra sa nazýva často aj optimalizácia. Cieľom je popísať si rôzne metódy, keďže sa nedá obecne tvrdiť, že daná metóda je lepšia než ostatné. Je teda veľmi užitočné mať prehľad vo viacerých metódach, keďže v opatimalizácii platí “no free lunch” pravidlo. To tvrdí, že ak vezmeme dva ľubovoľné optimalizačné algoritmy, tak ich výpočetná náročnosť spriemerovaná cez množinu všetkych množných optimalizačných problémov je ekvivalentná. Preto je potrebné pochopenie konkrétneho algoritmu a znalosť, na aký typ úloh sa hodí. Dodatočné info k optimalizácii viď prednáška. Začneme metódami hľadania extrému funkcií jednej premennej.
Funkcia jednej premennej
Metóda zlatého rezu
Metóda funguje na princípe zužovania intervalu. K ohraničeniu budeme potrebovať 3 body, \(x_1<x_2<x_3\), viď obrázok. Funkciu \(f(x)\) máme vyhodnotenú v troch bodoch. Keďže \(f_2\) je menšia ako \(f_1\) a \(f_3\), je zrejmé, že minimum leží v intervale \([x_1,x_3]\). V ďalšom kroku vyhodnotíme funkciu v bode \(x_4\), ktorý volíme vo väčšom intervale. Pri vyhodnocovaní funkcie môžu nastať dva prípady
- \(f_4>f_2\) (v obrázku prípad \(f_{4a}\)) - minimum leží v intervale \([x_1,x_4]\) a nová trojica bodov bude \(x_1,x_2,x_4\)
- \(f_4<f_2\) (v obrázku prípad \(f_{4b}\)) - minimum leží v intervale \([x_2,x_3]\) a nová trojica bodov bude \(x_2,x_4,x_3\)
Veľkosti úsekov na obrázku sú v pomere \(2-\varphi:2\varphi-3:2-\varphi\).
Aby boli veľkosti intervalov rovnako veľké nezávisle od toho, ktorým smerom zužujeme interval (teda, či bude nový interval \([x_1,x_4]\) alebo \([x_2,x_3]\)), musí platiť, že \(a+c=b\). Bod \(x_4\) teda volíme ako \(x_4=x_1+(x_3-x_2)\). Takisto platí, že \(b/a=\varphi=\frac{1+\sqrt{5}}{2}\). Vyskúšajte si skript ktorý je vo videu upravovaný, implementácia sa nachádza vo videu v čase od 21:08 do 28:10.
Vlastnosti metódy
- ak je v intervale viacero miním, nájde jedno z nich
- pomalá, ale robustná metóda
Parablická interpolácia
Popis metódy v slajdoch z prednášky, tu si stiahnete skript. Opäť máme 3 body, cez ktoré interpolujeme Lagrangov kvadratický polynom. V mieste minima paraboly volíme bod \(x_4\), ktorý použijeme na nasledujúce interpolácie.
Vlastnosti metódy
- kvadratická metóda, môže byť neefektívna ďaleko minima
- nemusí konvergovať, je potrebné kombinovať s ohraničením minima
Funkcia viac premenných
Simplexová metóda (amoeba)
Využíva (N+1) simplex v N-dimenzionálnom priestore. Simplex ohraničuje minimum a následne sa zmenšuje, až kým ho nenájde s dostatočnou presnosťou. Implementácia algoritmu vo videu sa nachádza v čase od 6:40-49:10, stiahnite si k tomu aj odpovedajúci skript. Samozrejme odporúčam prezrieť si aj grafické ukážky na konci videa.
Domáca úloha
Deadline na odovzdanie domácej úlohy je streda 14. Apríl 2021 23:59:59. Konzultácie a odovzdanie úlohy cez chat v MS Teams. Zadanie dostanete takisto v MS Teams.
Comments