  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. Moreover, the upper bound is optimal for a
wide class of primal-dual methods, and applies to the strictly more general
class of sharp primal-dual problems. We develop an adaptive restart scheme and
verify that restarts significantly improve the ability of PDHG, EGM, and ADMM
to find high accuracy solutions to LP problems.
