OPTPV_20141118 06

Zhrnutie prednášky

Prednáška nadväzuje na lineárne programovanie a predstavuje kvadratické programovanie (QP) ako triedu úloh s kvadratickou účelovou funkciou a lineárnymi obmedzeniami (rovnosťovými aj nerovnosťovými). Vysvetľuje sa podmienka konvexnosti pomocou pozitívne definitnej (resp. semidefinitnej) symetrickej matice P a dôsledky pre existenciu jednoznačného globálneho optima. Ukazuje sa odvodenie riešenia pre prípad bez obmedzení pomocou položenia gradientu na nulu a využitia invertovateľnosti matice P, ako aj rozšírenie na prípad s rovnosťovými obmedzeniami cez Lagrangeovu funkciu a riešenie sústavy KKT rovníc. Diskutuje sa výpočtová náročnosť (inverzia matice rádu n³) a dôležitosť voľby vhodného algoritmu podľa štruktúry problému (napr. ak P=0, ide o LP, nie QP). V druhej časti prednáška avizuje aplikácie QP na fitovanie metódou najmenších štvorcov s obmedzeniami, riedke riešenia a lineárnu/robustnú separáciu dát.

• - QP má kvadratickú účelovú funkciu, ale obmedzenia musia byť vždy lineárne (rovnosť aj nerovnosť).
• - Konvexnosť úlohy zabezpečuje pozitívne definitná (alebo semidefinitná) symetrická matica P vo funkcii nákladov.
• - Ak je P striktne pozitívne definitná, je invertovateľná, čo umožňuje priame riešenie cez gradient položený na nulu.
• - Ak P=0, úloha sa redukuje na lineárne programovanie a treba použiť efektívnejší simplexový algoritmus namiesto QP metód.
• - Pri obmedzeniach rovnosti sa problém rieši cez Lagrangeovu funkciu a sústavu KKT rovníc (inverzia väčšej matice).
• - Výpočtová zložitosť inverzie matice rastie s treťou mocninou počtu premenných, čo obmedzuje veľkosť riešiteľných QP úloh v porovnaní s LP.
• - Nasledujúce aplikácie QP: fitovanie metódou najmenších štvorcov s obmedzeniami/riedkosťou a lineárna, robustná a približná separácia dát.

Zhrnutie pripravené s pomocou AI z prepisu videa.