On the Relationships among GPU-Accelerated First-Order Methods for Solving Linear Programming
Authors:
- 18 August 2026
- journal article
- Published by Global Science Press in Journal of Computational Mathematics
- Vol. 45 (1) , 30-51
Abstract
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.Keywords
All Related Versions
Funding Information
- Research Center for Intelligent Operations Research
- RGC Senior Research Fellow Scheme (SRFS2223-5S02)
- GRF (15307822)
- RGC Early Career Scheme (25305424)
- NSFC Young Scientists Fund (12501440)
- National Natural Science Foundation of China (12271015)
This publication has 36 references indexed in Scilit:
- A Practical and Optimal First-Order Method for Large-Scale Convex Quadratic ProgrammingMathematical Programming, 2025
- Faster first-order primal-dual methods for linear programming using restarts and sharpnessMathematical Programming, 2022
- Conic Optimization via Operator Splitting and Homogeneous Self-Dual EmbeddingJournal of Optimization Theory and Applications, 2016
- On the Convergence Properties of a Majorized Alternating Direction Method of Multipliers for Linearly Constrained Convex Optimization Problems with Coupled Objective FunctionsJournal of Optimization Theory and Applications, 2016
- Convergence Rate Analysis of Several Splitting Schemes2016
- On the ergodic convergence rates of a first-order primal–dual algorithmMathematical Programming, 2015
- A Class of Linearized Proximal Alternating Direction MethodsJournal of Optimization Theory and Applications, 2011
- A First-Order Primal-Dual Algorithm for Convex Problems with Applications to ImagingJournal of Mathematical Imaging and Vision, 2010
- Approximation of fixed points of nonexpansive mappingsArchiv der Mathematik, 1992
- On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operatorsMathematical Programming, 1992