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

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(\kappa \mathrm{\Phi }·\ln (\frac{\kappa \mathrm{\Phi }\Vert w^{\star }\Vert }{\epsilon }))$, where $\epsilon$ is the target tolerance, $\kappa$ is the standard matrix condition number, $\Vert w^{\star }\Vert$ is the norm of the optimal solution, and $\mathrm{\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 $\mathrm{\Phi }$. This enables an analysis of the “two-stage performance” of rPDHG: we show that the first stage identifies the optimal basis in $O(\kappa \mathrm{\Phi }·\ln (\kappa \mathrm{\Phi }))$ iterations, and the second stage computes an $\epsilon$-optimal solution in $O\left(\Vert B^{-1}\Vert \Vert A\Vert ·\ln \left(\frac{\xi }{\epsilon }\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.

Funding: Part of this work was performed at the Massachusetts Institute of Technology and was supported by the Air Force Office of Scientific Research (AFOSR) [Grant FA9550-22-1-0356]. Another part of this work was performed at Georgia Institute of Technology and was supported by the Office of Naval Research (ONR) [Grant N00014-25-1-2088].