# Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2025.

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

- [Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming](https://mlsanity.com/paper/2610.01546/) (2026)

## Abstract (arXiv)

We present the Anderson Accelerated Primal--Dual Hybrid Gradient (AA-PDHG), a fixed-point-based framework that integrates Anderson Acceleration into the PDHG method for solving linear programming (LP) problems. A central motivation is to investigate whether Anderson Acceleration, which systematically exploits multi-step historical information, can serve as a viable alternative to the restart strategy for PDHG. We establish the global convergence of AA-PDHG under a safeguard condition and propose a filtered variant (FAA-PDHG) that enforces the uniform boundedness of the coefficient matrix through angle and length filtering, thereby providing a rigorous convergence guarantee. Numerical experiments on LP instances derived from MIPLIB 2017 demonstrate that both AA-PDHG and FAA-PDHG deliver significant speedups over vanilla PDHG. On pre-solved MIPLIB instances, AA-PDHG is the fastest method on about 70% of the benchmark when neither method uses primal-weight updates, and remains competitive when both AA-PDHG and restart PDHG use their respective primal-weight update strategies, establishing Anderson Acceleration as a competitive alternative to the restart mechanism.