Accessible Complexity Bounds for Restarted PDHG on Linear Programs with a Unique Optimizer

References

• [1] Alizadeh F, Haeberly JPA, Overton ML (1998) Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM J. Optim. 8(3):746–768.Crossref, Google Scholar
• [2] Anstreicher KM, Ji J, Potra FA, Ye Y (1993) Average performance of a self–dual interior point algorithm for linear programming. Pardalos PM, ed. Complexity in Numerical Optimization (World Scientific, Singapore), 1–15.Crossref, Google Scholar
• [3] Anstreicher KM, Ji J, Potra FA, Ye Y (1999) Probabilistic analysis of an infeasible-interior-point algorithm for linear programming. Math. Oper. Res. 24(1):176–192.Link, Google Scholar
• [4] Applegate D, Díaz M, Lu H, Lubin M (2024) Infeasibility detection with primal-dual hybrid gradient for large-scale linear programming. SIAM J. Optim. 34(1):459–484.Crossref, Google Scholar
• [5] Applegate D, Hinder O, Lu H, Lubin M (2023) Faster first-order primal-dual methods for linear programming using restarts and sharpness. Math. Programming 201(1–2):133–184.Crossref, Google Scholar
• [6] Applegate D, Díaz M, Hinder O, Lu H, Lubin M, O’Donoghue B, Schudy W (2021) Practical large-scale linear programming using primal-dual hybrid gradient. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, eds. NIPS’21: Proc. 35th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 20243–20257.Google Scholar
• [7] Basu K, Ghoting A, Mazumder R, Pan Y (2020) Eclipse: An extreme-scale linear program solver for web-applications. Daumé H III, Singh A, eds. Proc. 37th Internat. Conf. Machine Learn., vol. 119 (PMLR), 704–714.Google Scholar
• [8] Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, vol. 6 (Athena Scientific, Belmont, MA).Google Scholar
• [9] Borgwardt KH (1987) The Simplex Method: A Probabilistic Analysis, Algorithms and Combinatorics, vol. 1 (Springer, Berlin, Heidelberg).Crossref, Google Scholar
• [10] Bowman EH (1956) Production scheduling by the transportation method of linear programming. Oper. Res. 4(1):100–103.Link, Google Scholar
• [11] Cardinal Operations LLC (2025) Logging: Cardinal Optimizer (COPT) user guide, version 8.0. Accessed December 16, 2025, https://guide.coap.online/copt/en-doc/logging.html#first-order-method-pdlp-logging-for-gpu-solver.Google Scholar
• [12] Chambolle A, Pock T (2011) A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vision 40(1):120–145.Crossref, Google Scholar
• [13] Charnes A, Cooper WW (1954) The stepping stone method of explaining linear programming calculations in transportation problems. Management Sci. 1(1):49–69.Link, Google Scholar
• [14] Chen K, Sun D, Yuan Y, Zhang G, Zhao X (2026) HPR-LP: An implementation of an HPR method for solving linear programming. Math. Programming Comput. 18(1):183–210.Crossref, Google Scholar
• [15] Cormen TH, Leiserson CE, Rivest RL, Stein C (2022) Introduction to Algorithms, 4th ed. (MIT Press, Cambridge, MA).Google Scholar
• [16] Dantzig GB (2002) Linear programming. Oper. Res. 50(1):42–47.Link, Google Scholar
• [17] De Rosa A, Khajavirad A, Wang Y (2026) On the power of linear programming for K-means clustering. INFORMS J. Optim., ePub ahead of print May 19, https://doi.org/10.1287/ijoo.2025.0065.Link, Google Scholar
• [18] Deng Q, Feng Q, Gao W, Ge D, Jiang B, Jiang Y, Liu J, et al. (2025) An enhanced alternating direction method of multipliers-based interior point method for linear and conic optimization. INFORMS J. Comput. 37(2):338–359.Link, Google Scholar
• [19] Drusvyatskiy D, Lewis AS (2011) Generic nondegeneracy in convex optimization. Proc. Amer. Math. Soc. 139(7):2519–2527.Crossref, Google Scholar
• [20] Esser E, Zhang X, Chan TF (2010) A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4):1015–1046.Crossref, Google Scholar
• [21] FICO (2025) FICO Xpress Optimizer documentation: Solution methods (hybrid gradient method). Accessed December 16, 2025, https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/HTML/chapter4.html.Google Scholar
• [22] Freund RM (2003) On the primal-dual geometry of level sets in linear and conic optimization. SIAM J. Optim. 13(4):1004–1013.Crossref, Google Scholar
• [23] Freund RM, Vera JR (1999) Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm. SIAM J. Optim. 10(1):155–176.Crossref, Google Scholar
• [24] Ge D, Hu H, Huangfu Q, Liu J, Liu T, Lu H, Yang J, Ye Y, Zhang C (2024) cuPDLP-C. Accessed September 11, 2024, https://github.com/COPT-Public/cuPDLP-C.Google Scholar
• [25] Gleixner A, Gottwald L, Hoen A (2023) PaPILO: A parallel presolving library for integer and linear optimization with multiprecision support. INFORMS J. Comput. 35(6):1329–1341.Link, Google Scholar
• [26] Gleixner A, Hendel G, Gamrath G, Achterberg T, Bastubbe M, Berthold T, Christophel P, et al. (2021) MIPLIB 2017: Data-driven compilation of the 6th mixed-integer programming library. Math. Programming Comput. 13(3):443–490.Crossref, Google Scholar
• [27] Greene WH (2017) Econometric Analysis, 8th ed. (Pearson, New York).Google Scholar
• [28] Güler O, Ye Y (1993) Convergence behavior of interior-point algorithms. Math. Programming 60(1–3):215–228.Crossref, Google Scholar
• [29] Gurobi Optimization, LLC (2025) Gurobi 13.0 FAQ: Primal-dual hybrid gradient (PDHG) for very large linear programs. Accessed December 16, 2025, https://www.gurobi.com/resources/faq/gurobi-13-0.Google Scholar
• [30] Hanssmann F, Hess SW (1960) A linear programming approach to production and employment scheduling. Management Sci. MT-1(1):46–51.Link, Google Scholar
• [31] Hinder O (2024) Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs. Oper. Res. Lett. 57:107199.Crossref, Google Scholar
• [32] Hough M, Vavasis SA (2024) A primal-dual Frank-Wolfe algorithm for linear programming. Preprint, submitted February 28, https://arxiv.org/abs/2402.18514.Google Scholar
• [33] Huang Y, Zhang W, Li H, Ge D, Liu H, Ye Y (2025) A restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming. INFORMS J. Comput., ePub ahead of print November 20, https://doi.org/10.1287/ijoc.2024.0983.Crossref, Google Scholar
• [34] Koch T, Berthold T, Pedersen J, Vanaret C (2022) Progress in mathematical programming solvers from 2001 to 2020. EURO J. Comput. Optim. 10:100031.Crossref, Google Scholar
• [35] Li B, Yang L, Chen Y, Wang S, Mao H, Chen Q, Ma Y, et al. (2024) PDHG-unrolled learning-to-optimize method for large-scale linear programming. Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, Berkenkamp F, eds. ICML’24: Proc. 41st Internat. Conf. Machine Learn. (PMLR), 29164–29180.Google Scholar
• [36] Lin T, Ma S, Ye Y, Zhang S (2021) An ADMM-based interior-point method for large-scale linear programming. Optim. Methods Software 36(2–3):389–424.Crossref, Google Scholar
• [37] Lin Z, Xiong Z, Ge D, Ye Y (2025) A practical GPU-enhanced matrix-free primal-dual method for large-scale conic programs. Preprint, submitted May 1, https://arxiv.org/abs/2505.00311.Google Scholar
• [38] Liu XW, Dai YH, Huang YK (2024) Convergence and iteration-complexity of a primal-dual majorization-minimization method for large-scale linear programming. Pacific J. Optim. 20(3):513–535.Google Scholar
• [39] Lu H, Applegate D (2024) Scaling up linear programming with PDLP. Accessed September 26, 2024, https://research.google/blog/scaling-up-linear-programming-with-pdlp/.Google Scholar
• [40] Lu H, Yang J (2022) On the infimal sub-differential size of primal-dual hybrid gradient method and beyond. Preprint, submitted June 24, https://arxiv.org/abs/2206.12061.Google Scholar
• [41] Lu H, Yang J (2024a) PDOT: A practical primal-dual algorithm and a GPU-based solver for optimal transport. Preprint, submitted July 29, https://arxiv.org/abs/2407.19689.Google Scholar
• [42] Lu H, Yang J (2024b) Restarted Halpern PDHG for linear programming. Preprint, submitted July 23, https://arxiv.org/abs/2407.16144.Google Scholar
• [43] Lu H, Yang J (2025a) cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia. Oper. Res. 73(6):3440–3452.Link, Google Scholar
• [44] Lu H, Yang J (2025b) On the geometry and refined rate of primal–dual hybrid gradient for linear programming. Math. Programming 212(1):349–387.Crossref, Google Scholar
• [45] Lu H, Yang J (2026) A practical and optimal first-order method for large-scale convex quadratic programming. Math. Programming 215(1–2):771–808.Crossref, Google Scholar
• [46] Lu H, Simester D, Zhu Y (2025) Optimizing scalable targeted marketing policies with constraints. Marketing Sci. 44(5):1082–1103.Link, Google Scholar
• [47] Lu H, Yang J, Hu H, Huangfu Q, Liu J, Liu T, Ye Y, Zhang C, Ge D (2023) cuPDLP-C: A strengthened implementation of cuPDLP for linear programming by C language. Preprint, submitted December 22, https://arxiv.org/abs/2312.14832.Google Scholar
• [48] Mehrotra S, Ye Y (1993) Finding an interior point in the optimal face of linear programs. Math. Programming 62(1–3):497–515.Crossref, Google Scholar
• [49] Mirrokni V (2023) 2022 & beyond: Algorithmic advances. Accessed September 11, 2024, https://ai.googleblog.com/2023/02/google-research-2022-beyond-algorithmic.html.Google Scholar
• [50] NVIDIA Corporation (2025) LP features—NVIDIA cuOpt user guide (25.12). Accessed December 16, 2025, https://docs.nvidia.com/cuopt/user-guide/latest/lp-features.html.Google Scholar
• [51] O’Donoghue B (2021) Operator splitting for a homogeneous embedding of the linear complementarity problem. SIAM J. Optim. 31(3):1999–2023.Crossref, Google Scholar
• [52] O’Donoghue B, Chu E, Parikh N, Boyd S (2016) Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169(3):1042–1068.Crossref, Google Scholar
• [53] Peña JF (2024) An easily computable upper bound on the Hoffman constant for homogeneous inequality systems. Comput. Optim. Appl. 87(1):323–335.Crossref, Google Scholar
• [54] Peña J, Vera JC, Zuluaga LF (2021) New characterizations of Hoffman constants for systems of linear constraints. Math. Programming 187:79–109.Crossref, Google Scholar
• [55] Pock T, Cremers D, Bischof H, Chambolle A (2009) An algorithm for minimizing the Mumford–Shah functional. Proc. 2009 Internat. Conf. Computer Vision (IEEE, Piscataway, NJ), 1133–1140.Google Scholar
• [56] Potra FA (1994) A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points. Math. Programming 67:383–406.Crossref, Google Scholar
• [57] Todd MJ (1991) Probabilistic models for linear programming. Math. Oper. Res. 16(4):671–693.Link, Google Scholar
• [58] Todd MJ, Ye Y (1990) A centered projective algorithm for linear programming. Math. Oper. Res. 15(3):508–529.Link, Google Scholar
• [59] Vavasis SA, Ye Y (1996) A primal-dual interior point method whose running time depends only on the constraint matrix. Math. Programming 74(1):79–120.Crossref, Google Scholar
• [60] Wagner M, Meller J, Elber R (2004) Large-scale linear programming techniques for the design of protein folding potentials. Math. Programming 101(2):301–318.Crossref, Google Scholar
• [61] Wang H, Ghosal P, Mazumder R (2023) Linear programming using diagonal linear networks. Preprint, submitted October 4, https://arxiv.org/abs/2310.02535.Google Scholar
• [62] Xiong Z (2025a) High-probability polynomial-time complexity of restarted PDHG for linear programming. Preprint, submitted January 1, https://arxiv.org/abs/2501.00728.Google Scholar
• [63] Xiong Z (2025b) New theory and new practical methods for solving large-scale linear and conic optimization. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
• [64] Xiong Z, Freund RM (2023) On the relation between LP sharpness and limiting error ratio and complexity implications for restarted PDHG. Preprint, submitted December 21, https://arxiv.org/abs/2312.13773.Google Scholar
• [65] Xiong Z, Freund RM (2024) The role of level-set geometry on the performance of PDHG for conic linear optimization. Preprint, submitted June 4, https://arxiv.org/abs/2406.01942.Google Scholar
• [66] Xiong Z, Freund RM (2026) Computational guarantees for restarted PDHG for LP based on “limiting error ratios” and LP sharpness. Math. Programming, ePub ahead of print May 26, https://doi.org/10.1007/s10107-026-02358-w.Crossref, Google Scholar
• [67] Yang T, Lin Q (2018) RSG: Beating subgradient method without smoothness and strong convexity. J. Machine Learn. Res. 19(6):1–33.Google Scholar
• [68] Ye Y (1992) On the finite convergence of interior-point algorithms for linear programming. Math. Programming 57(1):325–335.Crossref, Google Scholar
• [69] Ye Y (1994) Toward probabilistic analysis of interior-point algorithms for linear programming. Math. Oper. Res. 19(1):38–52.Link, Google Scholar
• [70] Ye Y (2011) The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Math. Oper. Res. 36(4):593–603.Link, Google Scholar