OPTPV_20141125 03

Zhrnutie prednášky

Prednáška sa venuje riešeniu nelineárnych, potenciálne nekonvexných optimalizačných úloh s obmedzeniami, ktoré nemožno vyriešiť predtým prebranými metódami pre optimalizáciu bez obmedzení. Vysvetľuje sa, prečo je priame použitie Karush-Kuhn-Tuckerových podmienok pre nekonvexné úlohy problematické, keďže vedie iba k nutným podmienkam optimality a vyžaduje exponenciálne veľa kombinácií aktívnych obmedzení. Ako riešenie sa predstavuje metóda sekvenčného kvadratického programovania (SQP), ktorá iteratívne aproximuje pôvodný problém pomocou Taylorovho rozvoja druhého rádu účelovej funkcie a prvého rádu obmedzení okolo aktuálneho bodu. Takto vzniknutá lokálna kvadratická aproximácia s lineárnymi obmedzeniami sa dá riešiť ako konvexný QP problém, pričom riešenie sa iteratívne spresňuje ako nový linearizačný bod. Zdôrazňuje sa, že SQP nájde len lokálne optimum a na konci sa naznačuje problém s pozitívnou definitnosťou Hessovej matice.

• - Nelineárne úlohy s obmedzeniami sú výrazne zložitejšie ako úlohy bez obmedzení.
• - Priame riešenie cez KKT podmienky je pre nekonvexné problémy nespoľahlivé a výpočtovo náročné (exponenciálna zložitosť).
• - Sekvenčné kvadratické programovanie (SQP) rieši problém iteratívnym riešením kvadratických aproximácií.
• - Účelová funkcia sa aproximuje Taylorovým rozvojom 2. rádu (s gradientom a Hessovou maticou), obmedzenia lineárne (1. rádu).
• - Vzniknutý QP podproblém s lineárnymi obmedzeniami je konvexný a ľahšie riešiteľný.
• - Riešenie sa iteratívne aktualizuje ako nový linearizačný bod, kým sa nedosiahne dostatočne dobré riešenie.
• - SQP nachádza iba lokálne optimum, nie je zaručené globálne optimum; naznačený problém s pozitívnou definitnosťou Hessiánu.

Zhrnutie pripravené s pomocou AI z prepisu videa.