On the Relationships among GPU-Accelerated First-Order Methods for Solving Linear Programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912620239388672 |
|---|---|
| author | Chen, Kaihuang Sun, Defeng Yuan, Yancheng Zhang, Guojun Zhao, Xinyuan |
| author_facet | Chen, Kaihuang Sun, Defeng Yuan, Yancheng Zhang, Guojun Zhao, Xinyuan |
| contents | This paper aims to understand the relationships among recently developed GPU-accelerated first-order methods (FOMs) for linear programming (LP), with particular emphasis on HPR-LP -- a Halpern Peaceman--Rachford (HPR) method for LP. Our findings can be summarized as follows: (i) the base algorithm of cuPDLPx, a recently released GPU solver, is a special case of the base algorithm of HPR-LP, thereby showing that cuPDLPx is another concrete implementation instance of HPR-LP; (ii) once the active sets have been identified, HPR-LP and EPR-LP -- an ergodic PR method for LP -- become equivalent under the same initialization; and (iii) extensive numerical experiments on benchmark datasets demonstrate that HPR-LP achieves the best overall performance among current GPU-accelerated LP solvers. These findings provide a strong motivation for using the HPR method as a baseline to further develop GPU-accelerated LP solvers and beyond. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_23903 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Relationships among GPU-Accelerated First-Order Methods for Solving Linear Programming Chen, Kaihuang Sun, Defeng Yuan, Yancheng Zhang, Guojun Zhao, Xinyuan Optimization and Control 90C05, 90C06, 90C25, 65Y20 This paper aims to understand the relationships among recently developed GPU-accelerated first-order methods (FOMs) for linear programming (LP), with particular emphasis on HPR-LP -- a Halpern Peaceman--Rachford (HPR) method for LP. Our findings can be summarized as follows: (i) the base algorithm of cuPDLPx, a recently released GPU solver, is a special case of the base algorithm of HPR-LP, thereby showing that cuPDLPx is another concrete implementation instance of HPR-LP; (ii) once the active sets have been identified, HPR-LP and EPR-LP -- an ergodic PR method for LP -- become equivalent under the same initialization; and (iii) extensive numerical experiments on benchmark datasets demonstrate that HPR-LP achieves the best overall performance among current GPU-accelerated LP solvers. These findings provide a strong motivation for using the HPR method as a baseline to further develop GPU-accelerated LP solvers and beyond. |
| title | On the Relationships among GPU-Accelerated First-Order Methods for Solving Linear Programming |
| topic | Optimization and Control 90C05, 90C06, 90C25, 65Y20 |
| url | https://arxiv.org/abs/2509.23903 |