Yingxin Zhou, Stefano Cipolla, Phan Tu Vuong
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.