pith. sign in

arxiv: 2410.04043 · v4 · pith:U2DGEMRNnew · submitted 2024-10-05 · 🧮 math.OC

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

Zikai Xiong This is my paper

Pith reviewed 2026-05-23 20:27 UTC · model grok-4.3

classification 🧮 math.OC
keywords restarted primal-dual hybrid gradientlinear programmingiteration complexitycondition numberunique optimumgeometric condition numbertwo-stage performance
0
0 comments X

The pith

For linear programs with unique optima, restarted PDHG reaches ε-accuracy in O(κ Φ ln(κ Φ ||w^*|| / ε)) iterations where Φ is a closed-form geometric condition number of the sublevel sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that restarted primal-dual hybrid gradient (rPDHG) applied to linear programs possessing a unique optimal solution attains any target accuracy ε after a number of iterations bounded by O(κ Φ ln(κ Φ ||w^*|| / ε)), with κ the usual matrix condition number. The quantity Φ is presented as a geometric condition number of the sublevel sets that admits an explicit, closed-form expression and can be evaluated at essentially the same cost as solving the linear program itself. The same analysis decomposes the algorithm into an initial stage that recovers the optimal basis after O(κ Φ ln(κ Φ)) iterations and a second stage that refines the solution to ε-accuracy in O(||B^{-1}|| ||A|| ln(ξ / ε)) further iterations. The iteration bound is shown to stand in reciprocal relation to the stability of the instance under data perturbation.

Core claim

For linear programs with unique optima the restarted primal-dual hybrid gradient method identifies the optimal basis after O(κ Φ ln(κ Φ)) iterations and then reaches ε-accuracy in an additional O(||B^{-1}|| ||A|| ln(ξ / ε)) iterations, where the overall iteration count is governed by the product of the matrix condition number κ and the geometric condition number Φ of the sublevel sets.

What carries the argument

The geometric condition number Φ of the LP sublevel sets, which admits a closed-form expression and controls the iteration complexity alongside the standard condition number κ.

If this is right

  • The first stage recovers the optimal basis in O(κ Φ ln(κ Φ)) iterations.
  • The second stage produces an ε-optimal solution in O(||B^{-1}|| ||A|| ln(ξ / ε)) additional iterations.
  • The iteration bound stands in reciprocal relation to stability of the solution under data perturbation.
  • Proximity to multiple optima increases both the iteration bound and sensitivity to perturbations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A cheaply computable Φ could serve as a practical a-priori estimate of the number of iterations rPDHG will require on a concrete LP instance.
  • The equivalence between the iteration bound and LP sharpness indicates that sharpness constants from the broader optimization literature may yield analogous complexity statements for other first-order primal-dual schemes.
  • Instances whose sublevel sets yield small Φ may remain tractable for rPDHG even when the matrix condition number κ is moderately large.

Load-bearing premise

The linear program possesses a unique optimizer.

What would settle it

Running restarted PDHG on LPs with unique optima but systematically varied values of Φ, while holding κ, ||w^*|| and ε fixed, and checking whether observed iteration counts scale linearly with Φ.

Figures

Figures reproduced from arXiv: 2410.04043 by Zikai Xiong.

Figure 1
Figure 1. Figure 1: Convergence performance of rPDHG on two families of LP instances. (a) LP1 𝛾 (b) LP2 𝛾 We further construct another family of standard-form LP instances (1.1) with data 𝐴 2 , 𝑏2 , 𝑐2  , where 𝐴 2 = [PITH_FULL_IMAGE:figures/full_fig_p024_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Number of OnePDHG iterations in Stage I (optimal basis identification) and Stage II (local convergence) and the corresponding values of 𝜅Φln(𝜅Φ) and ∥𝐵 −1 ∥ ∥𝐴∥. (a) Stage I + Stage II (b) Stage I (c) Stage II 7. Optimized Reweighting and Step-Size Ratio Having shown the new accessible iteration bounds and confirmed their tightness via experiments, in this section, we show how to use the expression of the … view at source ↗
read the original abstract

The restarted primal-dual hybrid gradient method (rPDHG) has recently emerged as an important tool for solving large-scale linear programs (LPs). For LPs with unique optima, we present an iteration bound of $O\left(\kappa\Phi\cdot\ln\left(\frac{\kappa\Phi\|w^*\|}{\varepsilon}\right)\right)$, where $\varepsilon$ is the target tolerance, $\kappa$ is the standard matrix condition number, $\|w^*\|$ is the norm of the optimal solution, and $\Phi$ is a geometric condition number of the LP sublevel sets. This iteration bound is "accessible" in the sense that computing it is typically no more difficult than computing the optimal solution itself. Indeed, we present a closed-form and tractably computable expression for $\Phi$. This enables an analysis of the "two-stage performance" of rPDHG: we show that the first stage identifies the optimal basis in ${O}\left(\kappa\Phi\cdot\ln(\kappa\Phi)\right)$ iterations, and the second stage computes an $\varepsilon$-optimal solution in $O\left(\|B^{-1}\|\|A\|\cdot\ln\left(\frac{\xi}{\varepsilon}\right)\right)$ additional iterations, where $A$ is the constraint matrix, $B$ is the optimal basis and $\xi$ is the smallest nonzero in the optimal solution. . Furthermore, computational tests are consistent with our iteration bounds. We also show a reciprocal relation between the iteration bound and stability under data perturbation, which is also equivalent to (i) proximity to multiple optima, and (ii) the LP sharpness of the instance.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript derives accessible iteration complexity bounds for the restarted primal-dual hybrid gradient (rPDHG) algorithm applied to linear programs possessing a unique optimizer. The central result is an O(κ Φ ln(κ Φ ||w^*|| / ε)) iteration bound, where κ is the matrix condition number, ||w^*|| the norm of the optimum, and Φ a geometric condition number of the sublevel sets for which a closed-form, tractably computable expression is provided. The analysis includes a two-stage decomposition (basis identification followed by refinement) and establishes a reciprocal relationship between the iteration bound and stability under data perturbation, which is also linked to proximity to multiple optima and LP sharpness. Computational experiments are reported to be consistent with the derived bounds.

Significance. If the derivations hold, the work is significant for providing practical, computable complexity estimates for rPDHG on LPs, a method used for large-scale problems. The accessibility of Φ (no more difficult to compute than the solution itself) and the explicit two-stage analysis are notable strengths. The connection to perturbation stability offers a new perspective on instance difficulty. The paper ships closed-form expressions and consistency with computational tests, which strengthens the assessment.

minor comments (3)
  1. [Abstract] Abstract: the statement that computational tests are 'consistent with our iteration bounds' would be strengthened by a brief indication of the test set size, problem dimensions, and the precise metric of consistency (e.g., observed iteration counts versus the predicted O(κ Φ ln(...)) scaling).
  2. [§3.2] §3.2, Eq. (17): the transition from the sublevel-set geometry to the closed-form expression for Φ is presented without an intermediate lemma stating the equivalence; adding one sentence of justification would improve readability.
  3. [Table 1] Table 1: the column reporting observed versus predicted iterations for the basis-identification stage lacks error bars or the number of random seeds; this is a minor clarity issue given the claim of consistency.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation is self-contained under the explicit assumption of a unique optimizer. The iteration bound O(κΦ · ln(κΦ ||w*|| / ε)) and the closed-form expression for the geometric condition number Φ are derived directly from the LP geometry and the uniqueness premise; Φ is stated to be independently computable without reference to the iteration count or fitted parameters. The two-stage decomposition (basis identification then refinement) follows from the same assumption without reducing to a self-definition or self-citation chain. No load-bearing step equates a claimed prediction to its input by construction, and the reciprocal relation to perturbation stability is presented as an equivalence under the stated premise rather than a circular justification.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The analysis rests on the domain assumption of a unique optimizer and introduces Φ as a new geometric quantity whose independent evidence is limited to the claimed closed-form expression.

axioms (1)
  • domain assumption The linear program has a unique optimal solution.
    Invoked throughout the abstract and title to obtain the stated bound and two-stage result.
invented entities (1)
  • Φ (geometric condition number of the LP sublevel sets) no independent evidence
    purpose: Quantifies geometry that governs convergence rate of rPDHG.
    Introduced as part of the new bound; no external falsifiable handle supplied in the abstract.

pith-pipeline@v0.9.0 · 5826 in / 1240 out tokens · 28503 ms · 2026-05-23T20:27:15.699019+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages · 1 internal anchor

  1. [1]

    Alizadeh F, Haeberly JPA, Overton ML (1998) Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results.SIAM Journal on Optimization8(3):746–768

    work page 1998

  2. [2]

    Complexity in Numerical Optimization, 1–15 (World Scientific)

    Anstreicher KM, Ji J, Potra FA, Ye Y (1993) Average performance of a self–dual interior point algorithm for linear programming. Complexity in Numerical Optimization, 1–15 (World Scientific)

    work page 1993

  3. [3]

    Anstreicher KM, Ji J, Potra FA, Ye Y (1999) Probabilistic analysis of an infeasible-interior-point algorithm for linear programming.Mathematics of Operations Research24(1):176–192

    work page 1999

  4. [4]

    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.Proceedings of the Advances in Neural Information Processing Systems 34, volume 34, 20243–20257

    work page 2021

  5. [5]

    ApplegateD,DíazM,LuH,LubinM(2024)Infeasibilitydetectionwithprimal-dualhybridgradientforlarge-scale linear programming.SIAM Journal on Optimization34(1):459–484

    work page 2024

  6. [6]

    Applegate D, Hinder O, Lu H, Lubin M (2023) Faster first-order primal-dual methods for linear programming using restarts and sharpness.Mathematical Programming201(1-2):133–184

    work page 2023

  7. [7]

    Proceedings of the 37th International Conference on Machine Learning, 704–714 (PMLR)

    Basu K, Ghoting A, Mazumder R, Pan Y (2020) Eclipse: An extreme-scale linear program solver for web- applications. Proceedings of the 37th International Conference on Machine Learning, 704–714 (PMLR)

    work page 2020

  8. [8]

    Bertsimas D, Tsitsiklis JN (1997)Introduction to linear optimization, volume 6 (Athena scientific Belmont, MA)

    work page 1997

  9. [9]

    https://community.fico.com/s/blog-post/ a5QQi0000019II5MAM/fico4824

    Biele A, Gade D (2024) FICO ® Xpress solver 9.4. https://community.fico.com/s/blog-post/ a5QQi0000019II5MAM/fico4824. Accessed: 2024-09-11

    work page 2024

  10. [10]

    Borgwardt KH (1987)The simplex method: A probabilistic analysis, volume 1 (Springer Nature)

    work page 1987

  11. [11]

    Bowman EH (1956) Production scheduling by the transportation method of linear programming.Operations Research4(1):100–103

    work page 1956

  12. [12]

    Journal of Mathematical Imaging and Vision40:120–145

    ChambolleA,PockT(2011)Afirst-orderprimal-dualalgorithmforconvexproblemswithapplicationstoimaging. Journal of Mathematical Imaging and Vision40:120–145

    work page 2011

  13. [13]

    Charnes A, Cooper WW (1954) The stepping stone method of explaining linear programming calculations in transportation problems.Management Science1(1):49–69

    work page 1954

  14. [14]

    Chen K, Sun D, Yuan Y, Zhang G, Zhao X (2024) HPR-LP: An implementation of an HPR method for solving linear programming.arXiv preprint arXiv:2408.12179

    work page arXiv 2024

  15. [15]

    Cormen TH, Leiserson CE, Rivest RL, Stein C (2022)Introduction to algorithms(MIT Press), 4th edition

    work page 2022

  16. [16]

    Dantzig GB (2002) Linear programming.Operations Research50(1):42–47

    work page 2002

  17. [17]

    De Rosa A, Khajavirad A (2024) On the power of linear programming for k-means clustering.arXiv preprint arXiv:2402.01061

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  18. [18]

    DengQ,FengQ,GaoW,GeD,JiangB,JiangY,LiuJ,LiuT,XueC,YeY,ZhangC(2024)Anenhancedalternating direction method of multipliers-based interior point method for linear and conic optimization.INFORMS Journal on Computing0(0)

    work page 2024

  19. [19]

    Drusvyatskiy D, Lewis AS (2011) Generic nondegeneracy in convex optimization.Proceedings of the American Mathematical Society2519–2527

    work page 2011

  20. [20]

    EsserE,ZhangX,ChanTF(2010)Ageneralframeworkforaclassoffirstorderprimal-dualalgorithmsforconvex optimization in imaging science.SIAM Journal on Imaging Sciences3(4):1015–1046

    work page 2010

  21. [21]

    https://resources.nvidia.com/ en-us-ai-optimization-content/gtc24-s62495

    Fender A (2024) Advances in optimization AI. https://resources.nvidia.com/ en-us-ai-optimization-content/gtc24-s62495 . Accessed: 2024-09-11

    work page 2024

  22. [22]

    Freund RM (2003) On the primal-dual geometry of level sets in linear and conic optimization.SIAM Journal on Optimization13(4):1004–1013

    work page 2003

  23. [23]

    Freund RM, Vera JR (1999) Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm.SIAM Journal on Optimization10(1):155–176

    work page 1999

  24. [24]

    Accessed: 2024-09-11

    Ge D, Hu H, Huangfu Q, Liu J, Liu T, Lu H, Yang J, Ye Y, Zhang C (2024) cuPDLP-C.https://github.com/ COPT-Public/cuPDLP-C. Accessed: 2024-09-11. Xiong: Accessible Theoretical Complexity of the Restarted PDHG for LPs with Unique Optima 33

    work page 2024

  25. [25]

    Greene WH (2017)Econometric analysis(Pearson), 7th edition

    work page 2017

  26. [26]

    Güler O, Ye Y (1993) Convergence behavior of interior-point algorithms.Mathematical Programming60(1- 3):215–228

    work page 1993

  27. [27]

    Management Science1(1):46–51

    Hanssmann F, Hess SW (1960) A linear programming approach to production and employment scheduling. Management Science1(1):46–51

    work page 1960

  28. [28]

    arXiv preprint arXiv:2309.03988

    HinderO(2023)Worst-caseanalysisofrestartedprimal-dualhybridgradientontotallyunimodularlinearprograms. arXiv preprint arXiv:2309.03988

    work page arXiv 2023

  29. [29]

    Hough M, Vavasis SA (2024) A primal-dual Frank-Wolfe algorithm for linear programming.arXiv preprint arXiv:2402.18514

    work page arXiv 2024

  30. [30]

    Huang Y, Zhang W, Li H, Xue W, Ge D, Liu H, Ye Y (2024) Restarted primal-dual hybrid conjugate gradient method for large-scale quadratic programming.arXiv preprint arXiv:2405.16160

    work page arXiv 2024

  31. [31]

    Koch T, Berthold T, Pedersen J, Vanaret C (2022) Progress in mathematical programming solvers from 2001 to 2020.EURO Journal on Computational Optimization10:100031

    work page 2022

  32. [32]

    Li B, Yang L, Chen Y, Wang S, Chen Q, Mao H, Ma Y, Wang A, Ding T, Tang J, Sun R (2024) PDHG-unrolled learning-to-optimize method for large-scale linear programming.arXiv preprint arXiv:2406.01908

    work page arXiv 2024

  33. [33]

    Optimization Methods and Software36(2-3):389–424

    Lin T, Ma S, Ye Y, Zhang S (2021) An ADMM-based interior-point method for large-scale linear programming. Optimization Methods and Software36(2-3):389–424

    work page 2021

  34. [34]

    arXiv preprint arXiv:2208.03672

    Liu XW, Dai YH, Huang YK (2022) A primal-dual majorization-minimization method for large-scale linear programs. arXiv preprint arXiv:2208.03672

    work page arXiv 2022

  35. [35]

    Accessed: 2024-09-26

    Lu H, Applegate D (2024) Scaling up linear programming with PDLP.https://research.google/blog/ scaling-up-linear-programming-with-pdlp/. Accessed: 2024-09-26

    work page 2024

  36. [36]

    Lu H, Simester D, Zhu Y (2023) Optimizing scalable targeted marketing policies with constraints.Available at SSRN 4668582

    work page 2023

  37. [37]

    Lu H, Yang J (2022) On the infimal sub-differential size of primal-dual hybrid gradient method.arXiv preprint arXiv:2206.12061

    work page arXiv 2022

  38. [38]

    Lu H, Yang J (2023) cuPDLP.jl: A GPU implementation of restarted primal-dual hybrid gradient for linear programming in Julia.arXiv preprint arXiv:2311.12180

    work page arXiv 2023

  39. [39]

    arXiv preprint arXiv:2311.07710

    Lu H, Yang J (2023) A practical and optimal first-order method for large-scale convex quadratic programming. arXiv preprint arXiv:2311.07710

    work page arXiv 2023

  40. [40]

    Mathematical Programming1–39

    Lu H, Yang J (2024) On the geometry and refined rate of primal–dual hybrid gradient for linear programming. Mathematical Programming1–39

    work page 2024

  41. [41]

    arXiv preprint arXiv:2407.19689

    Lu H, Yang J (2024) PDOT: A practical primal-dual algorithm and a GPU-based solver for optimal transport. arXiv preprint arXiv:2407.19689

    work page arXiv 2024

  42. [42]

    Lu H, Yang J (2024) Restarted Halpern PDHG for linear programming.arXiv preprint arXiv:2407.16144

    work page arXiv 2024

  43. [43]

    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.arXiv preprint arXiv:2312.14832

    work page arXiv 2023

  44. [44]

    Mehrotra S, Ye Y (1993) Finding an interior point in the optimal face of linear programs.Mathematical Programming62(1-3):497–515

    work page 1993

  45. [45]

    https://ai.googleblog.com/2023/02/ google-research-2022-beyond-algorithmic.html

    Mirrokni V (2023) 2022 & beyond: Algorithmic advances. https://ai.googleblog.com/2023/02/ google-research-2022-beyond-algorithmic.html. Accessed: 2024-09-11

    work page 2023

  46. [46]

    SIAM Journal on Optimization31(3):1999–2023

    O’Donoghue B (2021) Operator splitting for a homogeneous embedding of the linear complementarity problem. SIAM Journal on Optimization31(3):1999–2023

    work page 2021

  47. [47]

    O’donoghue B, Chu E, Parikh N, Boyd S (2016) Conic optimization via operator splitting and homogeneous self-dual embedding.Journal of Optimization Theory and Applications169:1042–1068

    work page 2016

  48. [48]

    Mathematical Programming187:79–109

    Pena J, Vera JC, Zuluaga LF (2021) New characterizations of Hoffman constants for systems of linear constraints. Mathematical Programming187:79–109. 34 Xiong: Accessible Theoretical Complexity of the Restarted PDHG for LPs with Unique Optima

    work page 2021

  49. [49]

    Proceedings of the 2009 International Conference on Computer Vision, 1133–1140 (IEEE)

    Pock T, Cremers D, Bischof H, Chambolle A (2009) An algorithm for minimizing the Mumford–Shah functional. Proceedings of the 2009 International Conference on Computer Vision, 1133–1140 (IEEE)

    work page 2009

  50. [50]

    Potra FA (1994) A quadratically convergent predictor—corrector method for solving linear programs from infeasible starting points.Mathematical Programming67(1):383–406

    work page 1994

  51. [51]

    MathematicsofOperationsResearch 16(4):671–693

    ToddMJ(1991)Probabilisticmodelsforlinearprogramming. MathematicsofOperationsResearch 16(4):671–693

    work page 1991

  52. [52]

    Todd MJ, Ye Y (1990) A centered projective algorithm for linear programming.Mathematics of Operations Research15(3):508–529

    work page 1990

  53. [53]

    Mathematical Programming74(1):79–120

    Vavasis SA, Ye Y (1996) A primal-dual interior point method whose running time depends only on the constraint matrix. Mathematical Programming74(1):79–120

    work page 1996

  54. [54]

    Mathematical Programming101:301–318

    Wagner M, Meller J, Elber R (2004) Large-scale linear programming techniques for the design of protein folding potentials. Mathematical Programming101:301–318

    work page 2004

  55. [55]

    Wang H, Ghosal P, Mazumder R (2023) Linear programming using diagonal linear networks.arXiv preprint arXiv:2310.02535

    work page arXiv 2023

  56. [56]

    limiting error ratios

    Xiong Z, Freund RM (2023) Computational guarantees for restarted PDHG for LP based on “limiting error ratios” and LP sharpness.arXiv preprint arXiv:2312.14774

    work page arXiv 2023

  57. [57]

    Xiong Z, Freund RM (2023) On the relation between LP sharpness and limiting error ratio and complexity implications for restarted PDHG.arXiv preprint arXiv:2312.13773

    work page arXiv 2023

  58. [58]

    Xiong Z, Freund RM (2024) The role of level-set geometry on the performance of PDHG for conic linear optimization.arXiv preprint arXiv:2406.01942

    work page arXiv 2024

  59. [59]

    Yang T, Lin Q (2018) Rsg: Beating subgradient method without smoothness and strong convexity.The Journal of Machine Learning Research19(1):236–268

    work page 2018

  60. [60]

    Ye Y (1992) On the finite convergence of interior-point algorithms for linear programming.Mathematical Programming57(1):325–335

    work page 1992

  61. [61]

    Ye Y (1994) Toward probabilistic analysis of interior-point algorithms for linear programming.Mathematics of Operations Research19(1):38–52

    work page 1994

  62. [62]

    Ye Y (2011) The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate.Mathematics of Operations Research36(4):593–603

    work page 2011