Minimalizácia v smeroch
Ďalšia skupina metód na hľadanie extrémov sú také, ktoré premieňajú problém hľadania extrému vo viac dimenziách na postupné hľadanie extrému v jednom rozmere. Zvolí sa smer, v ktorom sa nájde minimum a v nájdenom minime sa volí nový smer, ktorý sa opäť minimalizuje. Takto to pokračuje, až kým sa nedostaneme k požadovanej presnosti. Minimalizácia v smeroch bázových vektorov nie je zrovna najefektívnejšia, viď príklady z prednášky. Volia sa preto sofistikovanejŠie metódy. Jednou z možností je vybrať sa smerom najprudŠieho spádu v danom mieste. To znamená, že minimalizujeme v smere záporného gradientu. Nevýhodou však je, že ak nájdeme minimum, gradient je v tom minime kolmý k predchádzajúcemu. Vzniká tým pádom ten istý problém ako v predchádzajúcom prípade. Optimálnou voľbou mnohokrát býva metóda konjugovaných gradientov. Stiahnite si skript k takémuto typu optimalizácie. Vysvetlenie nájdete vo videu od začiatku do času 21:00. Detailnejšie vysvetlenie v pdf.
Simulované žíhaní
Kombinatorická minimalizácia je vhodná na diskrétne úlohy ktoré majú veľa stupňov voľnosti a je dôležitejšie nájsť približnú hodnotu globálneho minima než jeho presnú hodnotu, čo by bolo časovo zbytočne náročné. Často sa využíva pre úlohy, kde exaktné gradientné metódy zlyhávajú. Najtypickejší prípad využitia simulovaného žíhania je problém obchodného cestujúceho, popísaného v prednáške a vo videu.
K videu si stiahnite skript a prejdite si úvod k úlohe a implementačnú časť od začiatku videa do 36:05.
Pre záujemcov
- Gradientné metódy za využívajú aj pri trénovaní neurónových sietí. Trénovanie neurónovej siete sa dá vlastne preformulovať ako problém hľadania minima. Algoritmus je zrozumiteľne popísaný vo videu od 3Blue1Brown a nazýva sa backpropagation.
### Domáca úloha
Deadline na odovzdanie domácej úlohy je streda 21. Apríl 2021 23:59:59. Konzultácie a odovzdanie úlohy cez chat v MS Teams. Zadanie dostanete takisto v MS Teams.
Comments