Computational guarantees for restarted PDHG for LP based on “Limiting Error Ratios” and LP sharpness
- 1Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, USA
- 2MIT Sloan School of Management, Cambridge, USA
Abstract
In recent years, there has been growing interest in solving linear optimization problems – or more simply “LP” – using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances. The restarted primal-dual hybrid gradient method (PDHG) – together with some heuristic techniques – has emerged as a powerful tool for solving huge-scale LPs. However, the theoretical understanding of the restarted PDHG and the validation of various heuristic implementation techniques are still very limited. Existing complexity analyses have relied on the Hoffman constant of the LP KKT system, which is known to be overly conservative, difficult to compute (and hence difficult to empirically validate), and fails to offer insight into instance-specific characteristics of the LP problems. These limitations have limited the capability to discern which characteristics of LP instances lead to easy versus difficult LP instances from the perspective of computation. With the goal of overcoming these limitations, in this paper we introduce and develop two purely geometry-based condition measures for LP instances: “limiting error ratio” and LP sharpness. We provide new computational guarantees for the restarted PDHG based on these two condition measures. For limiting error ratio, we provide a computable upper bound and show its relationship with the data instance’s proximity to infeasibility under perturbation. For LP sharpness, we prove its equivalence to the stability of the LP optimal solution set under perturbation of the objective function. We validate our computational guarantees in terms of these condition measures via specially constructed instances. Conversely, our computational guarantees validate the practical efficacy of certain heuristic techniques (row preconditioners and step-size tuning) that improve computational performance in practice. Finally, we present computational experiments on LP relaxations from the MIPLIB dataset that demonstrate the promise of various implementation strategies.
Related
- On the cyclic limiting behavior of the restarted Arnoldi algorithm for real symmetric matrices with restart length s=2
- Computational and Statistical Guarantees of the c-Rectified flow
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- Restarted Fixed-Point Acceleration of Proximal ADMM for Capped-ℓ1 Penalized Optimization
- Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization
BibTeX
@article{xiong2026computational,
title = {{Computational guarantees for restarted PDHG for LP based on “Limiting Error Ratios” and LP sharpness}},
author = {Zikai Xiong and Robert M. Freund},
journal = {Mathematical Programming},
year = {2026},
month = may,
doi = {10.1007/s10107-026-02358-w},
url = {https://doi.org/10.1007/s10107-026-02358-w},
note = {CC BY},
}
RIS
TY - JOUR
TI - Computational guarantees for restarted PDHG for LP based on “Limiting Error Ratios” and LP sharpness
AU - Zikai Xiong
AU - Robert M. Freund
PY - 2026
DA - 2026/05/26
JO - Mathematical Programming
DO - 10.1007/s10107-026-02358-w
UR - https://doi.org/10.1007/s10107-026-02358-w
AB - In recent years, there has been growing interest in solving linear optimization problems – or more simply “LP” – using first-order methods in order to avoid the costly matrix factorizations of traditional methods for huge-scale LP instances. The restarted primal-dual hybrid gradient method (PDHG) – together with some heuristic techniques – has emerged as a powerful tool for solving huge-scale LPs. However, the theoretical understanding of the restarted PDHG and the validation of various heuristic implementation techniques are still very limited. Existing complexity analyses have relied on the Hoffman constant of the LP KKT system, which is known to be overly conservative, difficult to compute (and hence difficult to empirically validate), and fails to offer insight into instance-specific characteristics of the LP problems. These limitations have limited the capability to discern which characteristics of LP instances lead to easy versus difficult LP instances from the perspective of computation. With the goal of overcoming these limitations, in this paper we introduce and develop two purely geometry-based condition measures for LP instances: “limiting error ratio” and LP sharpness. We provide new computational guarantees for the restarted PDHG based on these two condition measures. For limiting error ratio, we provide a computable upper bound and show its relationship with the data instance’s proximity to infeasibility under perturbation. For LP sharpness, we prove its equivalence to the stability of the LP optimal solution set under perturbation of the objective function. We validate our computational guarantees in terms of these condition measures via specially constructed instances. Conversely, our computational guarantees validate the practical efficacy of certain heuristic techniques (row preconditioners and step-size tuning) that improve computational performance in practice. Finally, we present computational experiments on LP relaxations from the MIPLIB dataset that demonstrate the promise of various implementation strategies.
SN - 0025-5610
SN - 1436-4646
ER -