Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911101626613760 |
|---|---|
| author | Zhou, Yingxin Cipolla, Stefano Vuong, Phan Tu |
| author_facet | Zhou, Yingxin Cipolla, Stefano Vuong, Phan Tu |
| contents | We present the Anderson Accelerated Primal-Dual Hybrid Gradient (AA-PDHG), a fixed-point-based framework designed to overcome the slow convergence of the standard PDHG method for the solution of linear programming (LP) problems. We establish the global convergence of AA-PDHG under a safeguard condition. In addition, we propose a filtered variant (FAA-PDHG) that applies angle and length filtering to preserve the uniform boundedness of the coefficient matrix, a property crucial for guaranteeing convergence. Numerical results show that both AA-PDHG and FAA-PDHG deliver significant speedups over vanilla PDHG for large-scale LP instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_08062 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP Zhou, Yingxin Cipolla, Stefano Vuong, Phan Tu Optimization and Control Numerical Analysis 65K05, 90C05, 90C06, 90C25, 90C33 We present the Anderson Accelerated Primal-Dual Hybrid Gradient (AA-PDHG), a fixed-point-based framework designed to overcome the slow convergence of the standard PDHG method for the solution of linear programming (LP) problems. We establish the global convergence of AA-PDHG under a safeguard condition. In addition, we propose a filtered variant (FAA-PDHG) that applies angle and length filtering to preserve the uniform boundedness of the coefficient matrix, a property crucial for guaranteeing convergence. Numerical results show that both AA-PDHG and FAA-PDHG deliver significant speedups over vanilla PDHG for large-scale LP instances. |
| title | Anderson Accelerated Primal-Dual Hybrid Gradient for solving LP |
| topic | Optimization and Control Numerical Analysis 65K05, 90C05, 90C06, 90C25, 90C33 |
| url | https://arxiv.org/abs/2508.08062 |