OPTPV_20141118 08

Zhrnutie prednášky

Prednáška ilustruje fungovanie aktívnej množinovej metódy (active set method) na riešenie kvadratického programovania pomocou konkrétneho príkladu s piatimi optimalizačnými premennými a približne dvadsiatimi obmedzeniami. Namiesto brute-force prehľadávania miliardy kombinácií algoritmus postupne pridáva a odoberá obmedzenia do kandidátnej aktívnej množiny na základe riešenia KKT sústavy, kým nedosiahne riešenie, ktoré je zároveň prípustné aj optimálne (nezáporné Lagrangeove multiplikátory). Demonštruje sa jednoduchá implementácia algoritmu v MATLABe (rádovo 20 riadkov kódu) a porovnanie výsledku s riešením pomocou funkcie quadprog. Ďalej sa preberá vstupný formát a výstupné stavové príznaky funkcie quadprog v MATLABe, vrátane troch dostupných metód riešenia a významu chybových kódov (nesplniteľnosť, neohraničenosť, dosiahnutie maximálneho počtu iterácií). Zdôrazňuje sa praktická efektívnosť metódy pre riadenie procesov napriek exponenciálnej zložitosti v najhoršom prípade.

• - Aktívna množinová metóda rieši QP postupným pridávaním/odoberaním obmedzení namiesto brute-force prehľadávania všetkých kombinácií
• - Algoritmus rieši KKT sústavu rovníc, hľadá zlepšujúci smer a dĺžku kroku obmedzenú najbližším porušeným obmedzením
• - Ak je zlepšujúci smer nulový a niektorý Lagrangeov multiplikátor je záporný, odstráni sa obmedzenie s najzápornejším multiplikátorom
• - Optimum je dosiahnuté, keď je riešenie prípustné a všetky Lagrangeove multiplikátory nezáporné
• - Implementácia metódy je jednoduchá (~20 riadkov MATLAB kódu), jadrom výpočtu je inverzia matice pri riešení KKT systému
• - MATLAB funkcia quadprog implementuje tri metódy vrátane active set, vstupný formát je podobný linprog, Hessián sa zadáva bez delenia dvomi
• - Metóda má exponenciálnu zložitosť v najhoršom prípade, ale v praxi je efektívna pre stovky až tisíce premenných a vhodná pre riadiaci hardvér

Zhrnutie pripravené s pomocou AI z prepisu videa.