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 [Formula: see text], where [Formula: see text] is the target tolerance, [Formula: see text] is the standard matrix condition number, [Formula: see text] is the norm of the optimal solution, and [Formula: see text] 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 [Formula: see text]. This enables an analysis of the “two-stage performance” of rPDHG: we show that the first stage identifies the optimal basis in [Formula: see text] iterations, and the second stage computes an [Formula: see text]-optimal solution in [Formula: see text] additional iterations, where A is the constraint matrix, B is the optimal basis, and [Formula: see text] 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].