MPC_20130306

Zhrnutie prednášky

Prednáška nadväzuje na predchádzajúci výklad o konvexnej optimalizácii a venuje sa reformulácii optimalizačných úloh s normami vo funkcii cieľa na jednoduchšie riešiteľné tvary. Ukazuje sa, že minimalizácia jednotkovej (1) normy nie je lineárny problém, ale pomocou epigrafickej formulácie a zavedenia pomocných premenných epsilon ju možno prepísať na úlohu lineárneho programovania, čo znásobí počet premenných (2n). Podobne sa rieši minimalizácia nekonečnej normy, kde stačí jediná pomocná premenná epsilon, takže výsledný problém má len n+1 premenných, čo je výpočtovo výhodnejšie, keďže čas riešenia rastie približne s treťou mocninou počtu premenných. Naopak, minimalizácia euklidovskej (druhej) normy nie je po častiach lineárna, preto ju nemožno previesť na LP problém, a otvára sa otázka, či ju možno vyjadriť aspoň ako kvadratický optimalizačný problém. Tieto reformulácie sú kľúčové pre prediktívne riadenie, kde sa normy bežne vyskytujú v účelovej funkcii a snahou je vždy nájsť čo najjednoduchšiu (LP alebo QP) formuláciu úlohy.

• - Minimalizácia 1-normy vektora x nie je lineárny problém, keďže funkcia |x| nie je lineárna, hoci je konvexná a po častiach lineárna.
• - Epigrafická formulácia rieši tento problém zavedením pomocnej premennej epsilon ohraničenej zhora aj zdola grafom funkcie.
• - Pri minimalizácii 1-normy sa zavádza samostatná premenná epsilon pre každú zložku vektora x, čím sa počet premenných zdvojnásobí (n + n).
• - Pri minimalizácii nekonečnej (max) normy stačí jedna spoločná premenná epsilon pre všetky nerovnosti, výsledný LP problém má n+1 premenných.
• - Počet optimalizačných premenných výrazne ovplyvňuje výpočtový čas (rastie približne s treťou mocninou počtu premenných), preto sa preferujú formulácie s menším počtom premenných.
• - Minimalizácia euklidovskej (2) normy nie je po častiach lineárna, takže ju nemožno previesť na LP problém.
• - Otvorenou otázkou zostáva, či je minimalizácia 2-normy aspoň kvadratickým optimalizačným problémom, keďže konštrukty sú lineárne.

Zhrnutie pripravené s pomocou AI z prepisu videa.