Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness

Understand

First-order primal-dual methods are appealing for their low memory overhead, fast iterations, and effective parallelization.

• However, they are often slow at finding high accuracy solutions, which creates a barrier to their use in traditional linear programming (LP) applications.
• This paper exploits the sharpness of primal-dual formulations of LP instances to achieve linear convergence using restarts in a general setting that applies to ADMM (alternating direction method of multipliers), PDHG (primal-dual hybrid gradient method) and EGM (extragradient method).
• In the special case of PDHG, without restarts we show an iteration count lower bound of $\Omega(\kappa^2 \log(1/\epsilon))$, while with restarts we show an iteration count upper bound of $O(\kappa \log(1/\epsilon))$, where $\kappa$ is a condition number and $\epsilon$ is the desired accuracy.