OPTPV_20141007 01

Zhrnutie prednášky

Prednáška nadväzuje na predchádzajúce numerické metódy riešenia neobmedzených optimalizačných úloh a uvádza tzv. bezgradientové metódy, ktoré sa použijú vtedy, keď gradient účelovej funkcie nie je analyticky dostupný. Úvod formou opakovacieho testu zhŕňa rozdiely medzi gradientovou metódou a Newtonovou metódou – ich lokálny charakter, závislosť od počiatočného bodu pri nekonvexných funkciách a rozdielnu časovú náročnosť jednotlivých iterácií. Zdôrazňuje sa, že Newtonova metóda vyžaduje inverziu Hessiánu, čo je pri vysokom počte premenných výpočtovo nákladné, zatiaľ čo gradientová metóda je v takom prípade efektívnejšia napriek vyššiemu počtu iterácií. Zároveň sa pripomína podmienka dvojnásobnej spojitej diferencovateľnosti funkcie potrebná na existenciu Hessiánu a teda použiteľnosť Newtonovej metódy.

• - Dnešnou témou sú gradientovo-voľné metódy pre prípad, keď gradient funkcie nie je analyticky známy.
• - Gradientové metódy (gradient descent, Newtonova metóda) sú lokálne metódy, negarantujú nájdenie globálneho optima.
• - Pri konvexných funkciách nezáleží na počiatočnom bode z hľadiska konvergencie ku globálnemu optimu, pri nekonvexných áno.
• - Vzdialenosť štartovacieho bodu od optima negarantuje rýchlejšiu konvergenciu pri nekonvexných funkciách.
• - Newtonova metóda potrebuje inverziu Hessiánu (rádovo n³ operácií), čo je pri veľkom počte premenných nevýhodné oproti gradientovej metóde.
• - Pre konvexnú kvadratickú funkciu Newtonova metóda konverguje presne v jednej iterácii pri kroku t=1.
• - Newtonova metóda vyžaduje, aby bola funkcia dvakrát spojito diferencovateľná (existencia Hessiánu).

Zhrnutie pripravené s pomocou AI z prepisu videa.