# Restarted Halpern PDHG for Linear Programming

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2024.

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

- [MPAX: Mathematical Programming in JAX](https://mlsanity.com/paper/2412.09734/) (2024)
- [Batched First-Order Methods for Parallel LP Solving in MIP](https://mlsanity.com/paper/2601.21990/) (2026)
- [RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation](https://mlsanity.com/paper/2603.22155/) (2026)
- [Parameter Tuning with Generalization Guarantees for GPU-Accelerated Linear Programming](https://mlsanity.com/paper/2606.08638/) (2026)
- [Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming](https://mlsanity.com/paper/2610.01546/) (2026)

## Abstract (arXiv)

In this paper, we propose and analyze a new matrix-free primal-dual algorithm, called restarted Halpern primal-dual hybrid gradient (rHPDHG), for solving linear programming (LP). We show that rHPDHG can achieve optimal accelerated linear convergence on feasible and bounded LP. Furthermore, we present a refined analysis that demonstrates an accelerated two-stage convergence of rHPDHG over the vanilla PDHG with an improved complexity for identification and an accelerated eventual linear convergence that does not depend on the conservative global Hoffman constant. Regarding infeasible LP, we show that rHPDHG can recover infeasibility certificates with an accelerated linear rate, improving the previous convergence rates. Furthermore, we discuss an extension of rHPDHG by adding reflection operation (which is dubbed as r2HPDHG), and demonstrate that it shares all theoretical guarantees of rHPDHG with an additional factor of 2 speedup in the complexity bound. Lastly, we build up a GPU-based LP solver using rHPDHG/r2HPDHG, and the experiments on 383 MIPLIB instances showcase an improved numerical performance compared cuPDLP.jl.