🔢 mathematics

Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP

This paper introduces Anderson Accelerated Primal-Dual Hybrid Gradient (AA-PDHG) and its filtered variant (FAA-PDHG) as a globally convergent, fixed-point-based alternative to restart strategies for solving linear programming problems, demonstrating significant speedups over vanilla PDHG on MIPLIB 2017 benchmarks.

Original authors: Yingxin Zhou, Stefano Cipolla, Phan Tu Vuong

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yingxin Zhou, Stefano Cipolla, Phan Tu Vuong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect spot to park a massive, awkwardly shaped truck in a crowded lot. You have a map (the math problem) and a set of rules (the constraints), but the lot is huge, and the truck is tricky. This is what solving a Linear Programming (LP) problem feels like for a computer. It's about finding the absolute best solution among millions of possibilities, like minimizing costs or maximizing efficiency.

For a long time, computers used a method called PDHG (Primal-Dual Hybrid Gradient) to do this. Think of PDHG as a very polite, steady walker. It takes small, careful steps toward the solution. It's great because it doesn't need to carry heavy luggage (it avoids complex math calculations), making it fast for huge problems. But there's a catch: as it gets closer to the finish line, it starts to wander. It gets stuck in a loop, taking tiny, inefficient steps, like a hiker who knows the mountain peak is right there but keeps walking in circles.

To fix this, experts usually use a "Restart" strategy. Imagine the hiker gets tired of circling, so they just teleport back to the start of the path and try a fresh, straight line. This works well, but it feels a bit like throwing away all the knowledge you just gained about the terrain.

The Big Idea: Learning from the Past
The authors of this paper asked a simple question: What if, instead of teleporting back to the start, the hiker looked at their last few steps to figure out the best direction to go next?

They introduced a technique called Anderson Acceleration (AA). Instead of forgetting history, AA acts like a smart navigator. It looks at the last few steps the hiker took, calculates a weighted average of those paths, and says, "Hey, if we combine these moves, we can cut straight to the solution!" It's like a GPS that doesn't just look at where you are, but uses your recent driving history to predict the fastest route forward.

The Challenge: Staying on the Road
There was a problem with just using this "smart navigator." The math behind Anderson Acceleration sometimes suggests a path that goes off-road, violating the rules of the parking lot (the constraints). If the computer takes a step that breaks the rules, the whole solution becomes useless.

To fix this, the authors built a safety net. They added a projection step, which is like a bouncer at a club. If the smart navigator suggests a move that goes outside the allowed area, the bouncer gently pushes the computer back inside the lines before it takes the step. This ensures the solution always stays valid.

They also added a safeguard. Imagine the navigator gets too confident and suggests a crazy, wild jump. The safeguard checks: "Is this jump actually helping?" If the answer is no, the computer ignores the navigator and goes back to the steady, polite walking of the original PDHG method. This guarantees that the computer never gets lost, even if the smart navigator has a bad day.

The Results: Does it Work?
The team tested their new method, which they call AA-PDHG, on a massive collection of real-world problems from a database called MIPLIB 2017. They compared it against the old "Restart" method and the original "steady walker."

Here is what they found:

Speed: On about 70% of the pre-solved problems, the new AA-PDHG method was the fastest, beating the restart strategy.
Consistency: Even when they added extra tricks (called "primal-weight updates") to both methods to make them smarter, AA-PDHG remained competitive, winning on about 60% of the instances.
Reliability: They proved mathematically that their method will eventually find the solution, provided the "navigator's" calculations don't get too wild. To be extra safe, they created a "filtered" version (FAA-PDHG) that strictly checks the math to ensure it never goes crazy, though this version is a bit slower in practice.

What They Ruled Out
The paper explicitly argues against the idea that you must use the "Restart" strategy (teleporting back to the start) to get good results. They show that using history (Anderson Acceleration) is a viable, and often better, alternative. They also clarify that while the "filtered" version is mathematically perfect, the unfiltered version is usually stable enough for real-world use without the extra slowdown.

How Sure Are They?
The authors are very confident in their math; they have proved that the method converges (finds the answer) under certain conditions. Their speed claims are based on simulations and experiments on 381 specific computer problems. They didn't just guess; they ran the code on a supercomputer and measured the time. The results suggest that Anderson Acceleration is a powerful new tool that can replace the old "restart" habit for many difficult problems, offering a faster way to solve the world's biggest optimization puzzles.

Technical Summary: Anderson Accelerated Primal-Dual Hybrid Gradient for Solving LP

Problem Statement
The paper addresses the challenge of accelerating the Primal-Dual Hybrid Gradient (PDHG) method for solving large-scale Linear Programming (LP) problems. While PDHG is attractive for its matrix-free nature and scalability, it often suffers from slow, sub-linear convergence in practice, particularly in the later stages of optimization when approaching optimal solutions. This stagnation is attributed to the lack of strong convexity in LP problems. Although restart strategies (e.g., by Applegate et al., 2023) have proven effective by periodically reinitializing the algorithm to exploit problem sharpness, the authors investigate whether Anderson Acceleration (AA)—which systematically exploits multi-step historical information—can serve as a viable alternative acceleration mechanism that avoids discarding historical data.

Methodology
The authors propose a framework that integrates Anderson Acceleration into the PDHG method by reformulating the PDHG iteration as a fixed-point problem. The core methodology involves three key adaptations to apply AA to the LP setting:

Fixed-Point Reformulation: The PDHG updates are expressed as a fixed-point iteration $u_{k+1} = T(u_k)$ , where $u$ contains both primal and dual variables.
Feasibility Preservation: Since standard AA computes affine combinations of past iterates which may violate the box and cone constraints inherent in LP, the authors introduce an explicit projection step ( $P$ ) onto the feasible set after every AA update. This ensures that accelerated iterates remain feasible without restricting the AA coefficients to convex combinations (which would limit acceleration potential).
Safeguard Mechanism: To guarantee global convergence, a safeguard condition is implemented. If the new fixed-point residual does not satisfy a specific decay threshold relative to the initial residual, the algorithm defaults to a standard PDHG step. This prevents the algorithm from diverging due to unstable AA updates.
Filtered Variant (FAA-PDHG): To address the theoretical requirement of the uniform boundedness of the AA coefficient matrix $H_k$ , the authors propose a filtered variant (FAA-PDHG). This variant employs "Angle Filtering" and "Length Filtering" procedures (adapted from Pollock and Rebholz, 2023) to enforce the boundedness of $H_k$ algorithmically, thereby providing a rigorous convergence guarantee.
Preconditioning: A diagonal matrix $\hat{D}$ is incorporated into the AA update to precondition the system, exploiting the structure of the constraint matrix to improve conditioning.

Key Contributions
The paper makes the following specific contributions:

Integration and Convergence: It integrates Anderson Acceleration into the PDHG framework for LP and establishes global convergence under a safeguard condition (Theorem 2).
Theoretical Rigor via Filtering: It proposes the FAA-PDHG variant, which enforces the uniform boundedness of the coefficient matrix $H_k$ through angle and length filtering. This provides a rigorous, algorithmically verifiable convergence guarantee (Theorem 3), demonstrating that the boundedness assumption required for convergence can be enforced.
Structural Comparison: The authors highlight a fundamental difference between AA-PDHG and restart PDHG (rPDHG). While rPDHG relies on problem-dependent properties (sharpness constants), AA-PDHG relies on algorithm-dependent properties (boundedness of $H_k$ ). This offers a complementary convergence guarantee.
Empirical Validation: The paper conducts an extensive numerical comparison on 381 LP relaxations from the MIPLIB 2017 dataset, systematically comparing AA-PDHG against rPDHG with and without primal-weight updates.

Experimental Results
Numerical experiments were conducted on the University of Southampton's Iridis 6 HPC cluster using Julia 1.6.5.

Comparison with Vanilla PDHG: Both AA-PDHG and FAA-PDHG demonstrated significant speedups over vanilla PDHG on selected instances, reducing KKT residuals at a faster rate in terms of both iterations and wall-clock time.
Comparison with Restart PDHG (rPDHG):
- On pre-solved MIPLIB instances where neither method used primal-weight updates, AA-PDHG was the fastest method on approximately 70% of the benchmark instances.
- When both methods utilized their respective primal-weight update strategies, AA-PDHG remained competitive, outperforming rPDHG on approximately 60% of the instances.
- The results indicate that AA-PDHG is particularly effective on challenging instances, with performance profiles showing convergence behavior comparable to or better than rPDHG.
Unresolved Instances: On the unresolved dataset, AA-PDHG remained competitive, outperforming rPDHG on about 60% of instances in terms of iteration count.

Significance and Claims
The paper claims that Anderson Acceleration serves as a viable and competitive alternative to the restart mechanism for accelerating first-order methods in linear programming. The significance of the work lies in:

Alternative Acceleration Strategy: It demonstrates that history-based acceleration (AA) can effectively replace or compete with the history-discarding restart strategy, achieving acceleration in both early and late stages of optimization.
Theoretical Foundation: It provides a rigorous convergence analysis for AA in the context of PDHG for LP, addressing the feasibility and boundedness challenges that were previously unaddressed in general nonlinear settings.
Practical Utility: The unfiltered AA-PDHG variant, while lacking the explicit boundedness enforcement of FAA-PDHG, is shown to be numerically stable with moderate memory sizes ( $m_A=5$ ) and serves as a practical, high-performance solver.

The authors conclude that while the filtering overhead makes FAA-PDHG less competitive in wall-clock time, it plays a crucial theoretical role in validating the boundedness assumptions. The unfiltered variant is recommended for practical use, offering a robust alternative to restart strategies for large-scale LP problems.

More like this