The Primal-Dual Hybrid Gradient (PDHG) algoritmus patří mezi metody prvního řádu k řešení úloh lineárního programování (LP). V roce 2025 vydala společnost Gurobi vlastní implementaci algoritmu vhodnou pro paralelizaci výpočtů na grafické kartě NVIDIA, což umožňuje řešení velkých/výpočetně náročných úloh. Cílem této práce je nastudovat PDHG algoritmus a provést numerickou studiu, ve které bude tato metoda srovnaná s tradičním simplexovým algoritmem, případně bariérovou metodu, kterou řešič od Gurobi nyní používá k řešení úloh LP.
References
Applegate, D., Díaz, M., Hinder, O., Lu, H., Lubin, M., O’Donoghue, B., and Schudy, W., 2021. Practical large-scale linear programming using primal-dual hybrid gradient. Advances in Neural Information Processing Systems, 34, pp.20243–20257.
Chambolle, A. and Pock, T., 2011. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40, pp.120–145.
