Kónické programování je obecný rámec, který zahrnuje lineární programování (LP), kvadratické programování (QP), semidefinitní programování (SDP) a další typy konvexních úloh jako speciální případy. Umožňuje modelovat a řešit složitější optimalizační problémy, které nelze vyjádřit pouze pomocí lineárních nerovností a rovností.
Zvláštní význam má semidefinitní programování (SDP) – optimalizace nad množinou pozitivně semidefinitních matic. Ačkoliv na první pohled vypadá matematicky náročněji než LP nebo QP, má řadu klíčových aplikací v teorii i praxi:
Reálné aplikace SDP
- Strojové učení a statistika – relaxace složitých úloh jako SVM, robustní PCA, nebo optimalizace kernelů.
- Kombinatorická optimalizace – aproximace NP-úplných úloh (např. Max-Cut, k-clustering) pomocí semidefinitních relaxací (např. slavná Goemans–Williamsonova relaxace).
- Řízení a systémová teorie – návrh řídicích zákonů pomocí lineárních maticových nerovností (LMI).
- Kvantová informatika a fyzika – optimalizace kvantových stavů a operací.
- Ekonometrie a finanční inženýrství – modelování rizika, korelační matice.
Díky své vysoké vyjadřovací síle jsou SDP modely velmi flexibilní a umožňují formulovat i úlohy, které nelze popsat lineárním modelem. Na druhou stranu, jejich řešení je výpočetně mnohem náročnější než v případě LP.
Klasické metody jako metoda vnitřního bodu (interior-point methods) mají kvadratickou až kubickou složitost a špatně škálují – už středně velké SDP úlohy (např. s několika tisíci proměnnými) mohou být prakticky neřešitelné. Zde přichází ke slovu metody prvního řádu jako je PDHG (Primal–Dual Hybrid Gradient), které sice konvergují pomaleji, ale umožňují řešit mnohem větší úlohy a často využít akceleraci pomocí GPU.
Cíle práce (konkrétní zadání se domluví individuálně se studentem):
- Porozumět teorii PDHG metody a jejím variantám (adaptivní kroky, over-relaxace, restartovací techniky).
- Implementovat PDHG algoritmus pro úlohy v LP a/nebo SDP.
- Ověřit možnosti paralelizace a akcelerace na GPU.
- Otestovat výkon na reálných úlohách z oblasti strojového učení, statistiky nebo řízení.
Přínosy pro studenta:
- Získá znalosti o důležité, prakticky používané oblasti optimalizace.
- Získá zkušenosti s návrhem paralelních algoritmů a programováním GPU.
- Bude pracovat na tématu, které má reálné využití ve vědě i průmyslu.
Doporučené zdroje:
- Applegate, David, et al. "Practical large-scale linear programming using primal-dual hybrid gradient." Advances in Neural Information Processing Systems 34 (2021): 20243-20257.
- Chambolle, Antonin, and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision 40 (2011): 120-145.
