OPTPV_20141007 02

Zhrnutie prednášky

Prednáška sa venuje metódam optimalizácie bez gradientu, ktoré sa používajú, keď nie je k dispozícii gradient účelovej funkcie alebo dokonca jej analytický tvar. Ťažiskom je algoritmus náhodného vyhľadávania nazývaný Luusova-Jaakolova metóda (v prepise skomolená ako "Lucia Cola"), ktorá pracuje s náhodne generovanými bodmi vo vnútri postupne sa zmenšujúceho alebo posúvajúceho sa boxu okolo aktuálneho najlepšieho riešenia. Metóda je vysvetlená graficky aj formálne, vrátane inicializačnej a iteračnej fázy, a je ukázaná jej implementácia v Matlabe. Na príklade nekonvexnej testovacej funkcie sa demonštruje, že metóda dokáže na rozdiel od gradientových metód unikať lokálnym optimám a nájsť globálne optimum, hoci si to vyžaduje viac iterácií a nezaručuje konvergenciu v polynomiálnom čase. Zmieňuje sa aj teoretický výsledok o konvergencii pre dvakrát spojito diferencovateľné funkcie s exponenciálnou zložitosťou v počte premenných.

• - Metódy bez gradientu sa delia na náhodné vyhľadávanie (Luusova-Jaakolova metóda, simulované žíhanie) a metódy aproximujúce gradient z lokálnych meraní.
• - Luusova-Jaakolova metóda generuje náhodné body v boxe okolo aktuálneho bodu; pri zlepšení sa box presunie, pri zhoršení sa zmenší.
• - Metóda vyžaduje iba hodnoty účelovej funkcie, nepotrebuje jej analytický tvar ani gradient.
• - Funguje aj pre nekonvexné funkcie a je schopná uniknúť lokálnym optimám na rozdiel od gradientových metód.
• - Ukončenie iterácií sa zvyčajne rieši dostatočne malým rozmerom boxu (napr. 10^-6).
• - Implementácia bola demonštrovaná v Matlabe vrátane inicializačnej a iteračnej fázy algoritmu.
• - Konvergencia je zaručená pre dvakrát spojito diferencovateľné konvexné funkcie, ale v najhoršom prípade exponenciálne závisí od počtu premenných.

Zhrnutie pripravené s pomocou AI z prepisu videa.