High-Probability Polynomial-Time Complexity of Restarted Primal-Dual Hybrid Gradient Method for Linear Programming

References

• [1] Adler I, Megiddo N (1985) A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension. J. ACM 32(4):871–895.Crossref, Google Scholar
• [2] Adler I, Karp R, Shamir R (1986) A family of simplex variants solving an m×d linear program in expected number of pivot steps depending on d only. Math. Oper. Res. 11(4):570–590.Link, Google Scholar
• [3] Adler I, Karp RM, Shamir R (1987) A simplex variant solving an m×d linear program in O(min(m2,d2)) expected number of pivot steps. J. Complexity 3(4):372–387.Crossref, Google Scholar
• [4] Anagnostides I, Sandholm T (2024) Convergence of log(1/ϵ) for gradient-based algorithms in zero-sum games without the condition number: A smoothed analysis. Proc. Adv. Neural Inform. Processing Systems 37, vol. 37 (Curran Associates, Inc., Red Hook, NY), 125839–125878.Google Scholar
• [5] 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
• [6] 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
• [7] 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
• [8] 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. Proc. Adv. Neural Inform. Processing Systems 34, vol. 34 (Curran Associates, Inc., Red Hook, NY), 20243–20257.Google Scholar
• [9] Biele A, Gade D (2024) FICO® Xpress solver 9.4. Accessed August 1, 2026, https://community.fico.com/s/blog-post/a5QQi0000019II5MAM/fico4824.Google Scholar
• [10] Blin N (2024) Accelerate large linear programming problems with NVIDIA cuOpt. Accessed August 1, 2026, https://developer.nvidia.com/blog/accelerate-large-linear-programming-problems-with-nvidia-cuopt/.Google Scholar
• [11] Blum A, Dunagan J (2002) Smoothed analysis of the perceptron algorithm for linear programming. Proc. 13th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 905–914.Google Scholar
• [12] Borgwardt KH (1977) Untersuchungen zur Asymptotik der mittleren Schrittzahl von Simplexverfahren in der Linearen Optimierung. PhD thesis, Universität Kaiserslautern, Kaiserslautern, Germany.Google Scholar
• [13] Borgwardt KH (1978) Zum Rechenaufwand von Simplexverfahren. Oper. Res. Verfahren 31:83–97.Google Scholar
• [14] Borgwardt KH (1982a) Some distribution-independent results about the asymptotic order of the average number of pivot steps of the simplex method. Math. Oper. Res. 7(3):441–462.Link, Google Scholar
• [15] Borgwardt KH (1982b) The average number of pivot steps required by the simplex-method is polynomial. Zeitschrift Oper. Res. 26:157–177.Crossref, Google Scholar
• [16] Cook N (2018) Lower bounds for the smallest singular value of structured random matrices. Ann. Probab. 46(6):3442–3500.Crossref, Google Scholar
• [17] Dadush D, Huiberts S (2018) A friendly smoothed analysis of the simplex method. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 390–403.Google Scholar
• [18] Dumitriu I, Zhu Y (2024) Extreme singular values of inhomogeneous sparse random rectangular matrices. Bernoulli 30(4):2904–2931.Crossref, Google Scholar
• [19] Dunagan J, Spielman DA, Teng SH (2011) Smoothed analysis of condition numbers and complexity implications for linear programming. Math. Programming 126(2):315–350.Crossref, Google Scholar
• [20] Gale D (1969) How to solve linear inequalities. Amer. Math. Monthly 76(6):589–599.Google Scholar
• [21] Ge D, Hu H, Huangfu Q, Liu J, Liu T, Lu H, Yang J, Ye Y, Zhang C (2024) cuPDLP-C. Accessed August 1, 2026, https://github.com/COPT-Public/cuPDLP-C.Google Scholar
• [22] Güler O, Ye Y (1993) Convergence behavior of interior-point algorithms. Math. Programming 60(1–3):215–228.Crossref, Google Scholar
• [23] Gurobi Optimization, LLC (2025) Gurobi releases version 13.0 with improved performance and new solving capabilities. Accessed August 1, 2026, https://www.gurobi.com/company/newsroom/gurobi-releases-version-13-0-with-improved-performance-and-new-solving-capabilities.Google Scholar
• [24] Haimovich M (1983) The simplex algorithm is very good! On the expected number of pivot steps and related properties of random linear programs. Working paper, Columbia University, New York.Google Scholar
• [25] HiGHS Development Team (2024) HiGHS v1.7.0 release notes. Accessed August 1, 2026, https://github.com/ERGO-Code/HiGHS/releases/tag/v1.7.0.Google Scholar
• [26] 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
• [27] Huang S (2000) Average number of iterations of some polynomial interior-point: Algorithms for linear programming. Sci. China A Math. 43(8):829–835.Crossref, Google Scholar
• [28] Huang SM (2005) Expected number of iterations of interior-point algorithms for linear programming. J. Comput. Math. 23(1):93–100.Crossref, Google Scholar
• [29] 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
• [30] Ji J, Potra FA (2008) On the probabilistic complexity of finding an approximate solution for linear programming. J. Complexity 24(2):214–227.Crossref, Google Scholar
• [31] Klee V, Minty GJ (1972) How good is the simplex algorithm? Shisha O, ed. Inequalities III (Academic Press, New York), 159–175.Google Scholar
• [32] Lu H, Yang J (2024) Restarted Halpern PDHG for linear programming. Preprint, submitted September 9, https://arxiv.org/abs/2407.16144.Google Scholar
• [33] 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
• [34] Lu H, Yang J (2025b) On the geometry and refined rate of primal–dual hybrid gradient for linear programming. Math. Programming 212:349–387.Crossref, Google Scholar
• [35] 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
• [36] 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.14832v1.Google Scholar
• [37] Megiddo N (1986) Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm. Math. Programming 35:140–172.Crossref, Google Scholar
• [38] Mizuno S, Todd MJ, Ye Y (1993) On adaptive-step primal-dual interior-point algorithms for linear programming. Math. Oper. Res. 18(4):964–981.Link, Google Scholar
• [39] Paquette C, Lee K, Pedregosa F, Paquette E (2021) SGD in the large: Average-case analysis, asymptotics, and stepsize criticality. Proc. Thirty Fourth Conf. Learn. Theory, vol. 134 (PMLR, New York), 3548–3626.Google Scholar
• [40] Paquette C, van Merriënboer B, Paquette E, Pedregosa F (2023) Halting time is predictable for large models: A universality property and average-case analysis. Foundations Comput. Math. 23(2):597–673.Crossref, Google Scholar
• [41] Pedregosa F, Scieur D (2020) Acceleration through spectral density estimation. Proc. 37th Internat. Conf. Machine Learn., vol. 119 (PMLR, New York), 7553–7562.Google Scholar
• [42] Rudelson M, Vershynin R (2009) Smallest singular value of a random rectangular matrix. Commun. Pure Appl. Math. 62(12):1707–1739.Crossref, Google Scholar
• [43] Rudelson M, Vershynin R (2010) Non-asymptotic theory of random matrices: Extreme singular values. Proc. Internat. Congress Mathematicians 2010, vol. III (World Scientific, Singapore), 1576–1602.Google Scholar
• [44] Scieur D, Pedregosa F (2020) Universal average-case optimality of Polyak momentum. Proc. 37th Internat. Conf. Machine Learn. (PMLR, New York), 8565–8572.Google Scholar
• [45] Shamir R (1987) The efficiency of the simplex method: A survey. Management Sci. 33(3):301–334.Link, Google Scholar
• [46] Smale S (1983a) On the average number of steps of the simplex method of linear programming. Math. Programming 27(3):241–262.Crossref, Google Scholar
• [47] Smale S (1983b) The problem of the average speed of the simplex method. Bachem A, Korte B, Grötschel M, eds. Mathematical Programming: The State of the Art (Springer, Berlin, Heidelberg), 530–539.Crossref, Google Scholar
• [48] Spielman DA, Teng SH (2003) Smoothed analysis of termination of linear programming algorithms. Math. Programming 97:375–404.Crossref, Google Scholar
• [49] Spielman DA, Teng SH (2004) Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3):385–463.Crossref, Google Scholar
• [50] Terlaky T (2009) Twenty-five years of interior point methods. INFORMS TutORials Oper. Res. 1–33.Link, Google Scholar
• [51] Todd MJ (1986) Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems. Math. Programming 35(2):173–192.Crossref, Google Scholar
• [52] Todd MJ (1991) Probabilistic models for linear programming. Math. Oper. Res. 16(4):671–693.Link, Google Scholar
• [53] Todd MJ, Ye Y (1990) A centered projective algorithm for linear programming. Math. Oper. Res. 15(3):508–529.Link, Google Scholar
• [54] Vershynin R (2018) High-Dimensional Probability: An Introduction with Applications in Data Science, 1st ed. (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [55] Wainwright MJ (2019) High-Dimensional Statistics: A Non-Asymptotic Viewpoint (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [56] Wright SJ (1994) An infeasible-interior-point algorithm for linear complementarity problems. Math. Programming 67(1–3):29–51.Crossref, Google Scholar
• [57] Xiong Z (2026) Accessible complexity bounds for restarted PDHG on linear programs with a unique optimizer. Math. Oper. Res.Link, Google Scholar
• [58] 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.13773v1.Google Scholar
• [59] Xiong Z, Freund RM (2024) The role of level-set geometry on the performance of PDHG for conic linear optimization. Preprint, submitted July 15, https://arxiv.org/abs/2406.01942.Google Scholar
• [60] 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
• [61] Ye Y (1992) On the finite convergence of interior-point algorithms for linear programming. Math. Programming 57(1–3):325–335.Crossref, Google Scholar
• [62] Ye Y (1994) Toward probabilistic analysis of interior-point algorithms for linear programming. Math. Oper. Res. 19(1):38–52.Link, Google Scholar
• [63] Ye Y (1997) Interior Point Algorithms: Theory and Analysis (Wiley-Interscience, New York).Crossref, Google Scholar
• [64] 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
• [65] Zhang Y (1994) On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4(1):208–227.Crossref, Google Scholar
• [66] Zhang Y, Zhang D (1994) Superlinear convergence of infeasible-interior-point methods for linear programming. Math. Programming 66(1–3):361–377.Crossref, Google Scholar