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

arXiv: https://arxiv.org/abs/2105.12715 · HTML: https://mlsanity.com/paper/2105.12715/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2021.

## Built on by (most cited first, 13 of 13)

- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)
- [Coordinate Linear Variance Reduction for Generalized Linear Programming](https://mlsanity.com/paper/2111.01842/) (2021)
- [A Fast and Accurate Splitting Method for Optimal Transport: Analysis and Implementation](https://mlsanity.com/paper/2110.11738/) (2021)
- [MPAX: Mathematical Programming in JAX](https://mlsanity.com/paper/2412.09734/) (2024)
- [FairWASP: Fast and Optimal Fair Wasserstein Pre-processing](https://mlsanity.com/paper/2311.00109/) (2023)
- [Bringing regularized optimal transport to lightspeed: a splitting method adapted for GPUs](https://mlsanity.com/paper/2305.18483/) (2023)
- [Restarts subject to approximate sharpness: A parameter-free and optimal scheme for first-order methods](https://mlsanity.com/paper/2301.02268/) (2023)
- [Relaxation-Informed Training of Neural Network Surrogate Models](https://mlsanity.com/paper/2604.22746/) (2026)
- [WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditions](https://mlsanity.com/paper/2110.12437/) (2021)
- [Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming](https://mlsanity.com/paper/2111.05530/) (2021)
- [Batched First-Order Methods for Parallel LP Solving in MIP](https://mlsanity.com/paper/2601.21990/) (2026)
- [Multi-Timescale Primal Dual Hybrid Gradient with Application to Distributed Optimization](https://mlsanity.com/paper/2506.15387/) (2025)
- [Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming](https://mlsanity.com/paper/2610.01546/) (2026)

## Abstract (arXiv)

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(kappa2 log(1/ε)), while with restarts we show an iteration count upper bound of O(kappa log(1/ε)), where kappa is a condition number and ε 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.