OPTPV_20141118 07

Zhrnutie prednášky

Prednáška predstavuje metódu aktívnej množiny (active set method) ako efektívnejšiu alternatívu k prehľadávaniu všetkých extrémnych bodov pri kvadratickom programovaní, podobne ako simplexová metóda pre lineárne programovanie. Algoritmus začína z prípustného bodu a počiatočnej (zvyčajne prázdnej) množiny aktívnych ohraničení, pričom v každej iterácii sa riešením KKT sústavy rovníc pre premennú delta a Lagrangeove multiplikátory hľadá smer a veľkosť kroku k zlepšeniu riešenia. Odvodzuje sa Lagrangeova funkcia a jej gradienty vedúce na lineárny systém rovníc, z ktorého vyplývajú dve kľúčové situácie: ak je delta nulová a všetky Lagrangeove multiplikátory nezáporné, riešenie je optimálne; ak je niektorý multiplikátor záporný, príslušné ohraničenie sa musí odstrániť z aktívnej množiny. Vysvetľuje sa heuristika výberu ohraničenia na odstránenie (najviac záporný multiplikátor) a paralela medzi iteráciami tejto metódy a pivotovaním v simplexovom algoritme.

• - Active set method je efektívnejšia alternatíva k úplnému prehľadávaniu extrémnych bodov pri riešení kvadratického programovania.
• - Algoritmus začína z prípustného bodu x0 a počiatočnej (často prázdnej) množiny aktívnych ohraničení W.
• - V každej iterácii sa zostavuje Lagrangeova funkcia a riešením KKT podmienok sa získava systém lineárnych rovníc pre delta a Lagrangeove multiplikátory lambda.
• - Ak je optimálne delta rovné nule a všetky lambda nezáporné, aktuálny bod x je certifikovane optimálnym riešením (splnené KKT podmienky).
• - Ak je delta nulové, ale niektorý lambda záporný, dané ohraničenie nie je v skutočnosti aktívne a musí sa odstrániť z množiny W.
• - Pri viacerých záporných multiplikátoroch sa používa heuristika odstránenia ohraničenia s najviac záporným lambda, hoci optimálnosť tohto výberu nie je garantovaná.
• - Metóda je štruktúrou a iteračným charakterom analogická simplexovému algoritmu pre lineárne programovanie.

Zhrnutie pripravené s pomocou AI z prepisu videa.