PDHG metoda pro lineární a kónické programování
| školitel: | doc. Ing. Tomáš Oberhuber, Ph.D. |
| e-mail: | zobrazit e-mail |
| typ práce: | bakalářská práce, diplomová práce |
| zaměření: | MI_MM, MI_AMSM, MINF |
| klíčová slova: | optimalizace, iterativní metody |
| popis: | 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: 1. Strojové učení a statistika – relaxace složitých úloh jako SVM, robustní PCA, nebo optimalizace kernelů. 2. Kombinatorická optimalizace – aproximace NP-úplných úloh (např. Max-Cut, k-clustering) pomocí semidefinitních relaxací (např. slavná Goemans–Williamsonova relaxace). 3. Řízení a systémová teorie – návrh řídicích zákonů pomocí lineárních maticových nerovností (LMI). 4. Kvantová informatika a fyzika – optimalizace kvantových stavů a operací. 5. 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: 1. Porozumět teorii PDHG metody a jejím variantám (adaptivní kroky, over-relaxace, restartovací techniky). 2. Implementovat PDHG algoritmus pro úlohy v LP a/nebo SDP. 3. Ověřit možnosti paralelizace a akcelerace na GPU. 4. Otestovat výkon na reálných úlohách z oblasti strojového učení, statistiky nebo řízení. Přínosy pro studenta: 1. Získá znalosti o důležité, prakticky používané oblasti optimalizace. 2. Získá zkušenosti s návrhem paralelních algoritmů a programováním GPU. 3. Bude pracovat na tématu, které má reálné využití ve vědě i průmyslu. |
| literatura: | 1. Applegate, David, et al. \"Practical large-scale linear programming using primal-dual hybrid gradient.\" Advances in Neural Information Processing Systems 34 (2021): 20243-20257. 2. 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. |
| naposledy změněno: | 19.05.2025 10:59:01 |
za obsah této stránky zodpovídá:
Pavel Strachota | naposledy změněno: 9.9.2021