Anderson Accelerated Primal-Dual Hybrid Gradient for Solving LP

Jul 16, 2026

Upload by Himbo

Anderson Accelerated Primal–Dual Hybrid Gradient (AA-PDHG) integrates Anderson Acceleration into the PDHG method for solving linear programming (LP) problems. The framework uses fixed-point formulation, aiming to replace the common PDHG restart strategy with multi-step historical extrapolation. Global convergence is established under a safeguard condition, and a filtered variant (FAA-PDHG) enforces uniform boundedness of the coefficient matrix via angle and length filtering to ensure rigorous convergence. Experiments on MIPLIB 2017 LP instances show substantial speedups over vanilla PDHG, with AA-PDHG outperforming benchmark baselines on most pre-solved instances.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages43

Reading Time1 h 48 min

Abstract

Introduction

Primal Dual Hybrid Gradient (PDHG) and matrix-free iterations

Motivation: stagnation and lack of strong convexity in LP

Anderson Acceleration as an alternative acceleration strategy

Related work on restarted and accelerated PDHG

arXiv :2508 .08062v2 [math .OC] 10 Jul 2026 Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP Yingxin Zhou Cipolla Stefano Phan T. Vuong School of Mathematical Sciences, University of Southampton [yz11u24@soton.ac.uk](yz11u24@soton.ac.uk), [S.Cipolla@soton.ac.uk](S.Cipolla@soton.ac.uk), [T.V.Phan@soton.ac.uk](T.V.Phan@soton.ac.uk) Abstract We present the Anderson Accelerated Primal–Dual Hybrid Gradient (AA-PDHG), a fixedpoint-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. Keywords: Anderson Acceleration, Primal Dual Hybrid Gradient method, fixed-point, Global Convergence, Linear Programming 1 Introduction In recent years, first-order methods have become increasingly popular for solving large-scale convex optimisation problems, particularly due to their low per-iteration cost and favourable scalability. Among them, the Primal Dual Hybrid Gradient (PDHG) method has received considerable attention. If we consider a min-max problem in the form: min max f (x) + z ⊤ Kx − g∗(z), x z where f and g are proper, closed, and convex functions, g ∗ denotes the conjugate function of g , and K is a linear operator, then the corresponding PDHG scheme can be written as xk+1 in 􀀚 f (x) + 12τ 􀀍 x − 􀀐xk − τK⊤ zk􀀑 􀀍 2 􀀛 , 􀀼 (1) z k+1 in 􀀚 g∗ (z) + 21σ 􀀍 z − 􀀐zk + σK 􀀐 2xk+1 − xk􀀑􀀑 􀀍 2 􀀛 , being τ, σ step-sizes. This algorithm is also commonly referred to as the Chambolle–Pock algorithm Chambolle and Pock (2011) . When the updates in (1) are specialised for the solution of linear programs (LP), see (8), it is possible to observe a major advantage of PDHG when compared to other first or second-order optimisation methods, that is, it requires only matrix-vector multiplications at each iteration, thereby avoiding solution of linear systems and related expensive matrix factorisations. Such a characteristic is often referred to as matrix-free in the literature, as also discussed in Chambolle and Pock (2011) . This characteristic, combined with the fact that the matrix-vector product is a highly parallelisable task, makes PDHG particularly attractive for large-scale applications. The use of PDHG for solving LP problems has attracted considerable attention in recent years, see, e.g., Calamai and Mor´e (1987), Chang and Murty (1989), Lan et al. (2011), Wang and Shroff (2017), Renegar (2019), Applegate et al. (2023, 2021, 2025), which have demonstrated that PDHG can offer a more scalable alternative to classical LP methods, such as interior-point or simplex methods. In addition, Lu and Yang (2025) reported engineering results for restarted PDHG for linear programming from the GPU perspective. Related developments also include the work of Liu and Lu (2025), who studied the geometric behavior of PDHG for LP and proposed a crossover algorithm based on the spiral trajectory of PDHG. A related geometric analysis of PDHG was also provided by Lu and Yang (2024) . We also note that recent progr

FAQs

What do numerical experiments on MIPLIB 2017 indicate?

On LP instances derived from MIPLIB 2017, both AA-PDHG and FAA-PDHG achieve significant speedups over vanilla PDHG. On pre-solved instances, AA-PDHG is fastest on about 70% of the benchmark under the stated update settings and remains competitive when compared to restart PDHG.

Jul 16, 2026

Upload by Himbo