Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP

Yingxin Zhou, Stefano Cipolla, Phan Tu Vuong · 2025

Read Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP by Yingxin Zhou, Stefano Cipolla, Phan Tu Vuong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08062.txt.

Description

Yingxin Zhou and co-authors speed a classic solver for linear programs in a 2025 paper. Linear programs sit inside planning, logistics, and mixed-integer tools used daily. A hybrid gradient method solves them at scale, but restarts are its usual trick to keep pace.

The authors fold in Anderson acceleration, which reuses many past steps to jump ahead. They prove the blend settles to a solution under a guard rule, and a filtered variant tightens that proof. On hard library cases both versions beat the plain method by wide margins. Reuse of history, they argue, rivals restarts as the go-to boost.

Catalog record

CREATORYingxin Zhou, Stefano Cipolla, Phan Tu Vuong
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08062

Browse the full library · About the Tower of Babel