Kvadratické programování (QP) představuje jednu z nejdůležitějších tříd konvexních optimalizačních úloh. Jedná se o problémy, kde je cílová funkce kvadratická a omezení jsou lineární. Přestože se na první pohled jedná o jednoduché rozšíření lineárního programování (LP), QP má výrazně širší modelovací schopnosti a v praxi se využívá v celé řadě klíčových oblastí:
- Ve strojovém učení se QP objevuje například ve formě Support Vector Machines (SVM), kde umožňuje efektivní trénování robustních klasifikátorů.
- V telekomunikaci a síťové optimalizaci - optimalizace přenosových výkonů, rozvrhování v síti, alokace kanálů, interference management.
- V optimalizace výroby a logistice - optimalizace tras s penalizací změn (např. robustní optimalizace rozvozu), skladování a distribuce – penalizace přetížení nebo odchylek od cílových zásob.
- V ekonomii a financích modeluje rozložení investic s ohledem na minimalizaci rizika.
- Ve vědeckých výpočtech se používá pro stabilizaci inverzních problémů nebo při aproximaci řešení parciálních diferenciálních rovnic pomocí Galerkinovy metody.
- V robotice - slouží pro optimalizaci pohybu (trajectory planning) – hladké trajektorie s minimalizací zrychlení a s omezeními.
Síla QP spočívá v tom, že dokáže zachytit kompromis mezi dvěma cíli – například minimalizací chyby a velikostí řešení (tzv. Tichonova regularizace) – pomocí kvadratické penalizace. Tato vlastnost jej činí ideálním nástrojem pro široké spektrum inženýrských a vědeckých problémů.
Moderní kvadratické úlohy však často obsahují tisíce až miliony proměnných, zejména v kontextu datových úloh nebo online řízení. Proto je klíčové vyvíjet škálovatelné a efektivní algoritmy, které umožní jejich řešení i na moderních výpočetních platformách, jako jsou grafické procesory (GPU). Zvlášť vhodné jsou metody prvního řádu, jako je Primal–Dual Hybrid Gradient (PDHG), které umožňují iterativní řešení i velmi rozsáhlých úloh s minimálními nároky na paměť.
Cíle práce (konkrétní zadání se domluví individuálně se studentem):
- Seznámit se s PDHG variantou pro úlohu kvadratického programování a prostudovat teorii týkající se PDHG metody.
- Seznámit se současnou implementací PDHG pro lineární programování v knihovně TNL.
- Rozšířit tento řešič o možnost řešení úloh QP.
- Otestovat řešič na vhodné úloze, např. SVM pro klasifikaci dat.
- Porovnat výsledný řešič s alternativními knihovnami.
Přínosy pro studenta:
- Získá znalosti o důležité, prakticky používané oblasti optimalizace.
- Získá zkušenosti s implementací numerických algoritmů v jazyce C++ a moderními vlastnostmi tohoto jazyka.
- Bude pracovat na tématu, které má reálné využití ve vědě i průmyslu.
Zdroje:
- Lu, Haihao, and Jinwen Yang. "A practical and optimal first-order method for large-scale convex quadratic programming." arXiv preprint arXiv:2311.07710 (2023).
- Applegate, David, et al. "Practical large-scale linear programming using primal-dual hybrid gradient." Advances in Neural Information Processing Systems 34 (2021): 20243-20257.
