OPTPV_20141104 01

Zhrnutie prednášky

Prednáška nadväzuje na Karush-Kuhn-Tuckerove podmienky a rozoberá ich praktické úskalia pri riešení optimalizačných úloh s obmedzeniami. Vysvetľuje sa, že KKT podmienky (stacionarita, primárna uskutočniteľnosť, nezápornosť multiplikátorov a komplementárna nedbalosť) sú vo všeobecnom prípade len nutné, avšak pri konvexných problémoch sú aj postačujúce pre optimalitu. Hlavná časť sa venuje problému tzv. degenerácie, keď je v optime aktívnych viac obmedzení, než je dimenzia priestoru premenných, čo vedie k preurčenému systému rovníc. Na grafickom príklade sa ukazuje, ako redundantné obmedzenie spôsobí, že rovnaké optimálne riešenie sa nájde viacnásobne pri skúmaní rôznych kombinácií aktívnych obmedzení, čo zbytočne zväčšuje výpočtový priestor najmä pri nekonvexných úlohách.

• - Zhrnutie KKT sústavy: stacionarita, primárna uskutočniteľnosť, nezápornosť multiplikátorov, komplementárna nedbalosť
• - Komplementárna nedbalosť je nelineárna podmienka spôsobená súčinom Lagrangeových multiplikátorov a obmedzení
• - KKT podmienky sú vo všeobecnosti len nutné, pri konvexných problémoch (konvexná účelová funkcia a konvexné obmedzenia) sú aj postačujúce
• - Nedegenerovaný prípad: počet aktívnych obmedzení v optime zodpovedá dimenzii priestoru premenných
• - Degenerovaný prípad nastáva, keď je aktívnych viac obmedzení než premenných, čo vedie k preurčenému systému rovníc
• - Redundantné obmedzenia môžu spôsobiť, že rovnaké optimálne riešenie sa objaví pri viacerých kombináciách aktívnych obmedzení
• - Pri nekonvexných problémoch nemožno hľadanie zastaviť po nájdení prvého riešenia spĺňajúceho KKT podmienky

Zhrnutie pripravené s pomocou AI z prepisu videa.