OPTPV_20141028 02

Zhrnutie prednášky

Prednáška sa venuje Newtonovej metóde pre riešenie kvadratických optimalizačných úloh s rovnostnými obmedzeniami. Odvodzuje sa sústava lineárnych rovníc z podmienok optimality (gradient Lagrangiánu podľa delta a mí), ktorej riešením sa získa optimálny krok. Ukazuje sa, že pri kvadratickom probléme metóda so štartom z prípustného bodu konverguje presne v jednej iterácii, keďže riešená sústava zodpovedá priamo Karushovým-Kuhnovým-Tuckerovým podmienkam pôvodnej úlohy. Následne sa predstavuje metóda s neprípustným štartom, ktorá nevyžaduje počiatočný bod ležiaci na obmedzeniach, čím sa vyhýba numerickým problémom spôsobeným vzdialenými prípustnými bodmi. Na záver sa zdôrazňuje všeobecná použiteľnosť oboch prístupov aj pre nelineárne účelové funkcie.

• - Odvodenie sústavy lineárnych rovníc z podmienok optimality (gradient podľa delta a mí rovný nule)
• - Riešenie tejto sústavy zodpovedá KKT podmienkam pôvodného problému
• - Feasible-start Newtonova metóda pre kvadratické úlohy konverguje v jednej iterácii
• - Nevýhoda feasible-start metódy: vzdialený počiatočný bod ničí numerickú stabilitu
• - Infeasible-start metóda umožňuje ľubovoľný počiatočný bod, nie nutne na obmedzeniach
• - Zmena pravej strany sústavy z nuly na (b - Ax) je jediný rozdiel oproti feasible-start metóde
• - Pre kvadratické programy sa odporúča priamo riešiť KKT systém namiesto iteratívneho Newtonovho kroku
• - Obe metódy sú aplikovateľné aj na plne nelineárne účelové funkcie

Zhrnutie pripravené s pomocou AI z prepisu videa.