Gpu solver speeds up large convex quadratic programming problems
cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
Mathematical Software
Summary
Convex quadratic programming is a math method used to find the best solution under certain conditions, but solving large problems can be slow and complicated. The authors developed cuPDQPx, a software that runs on graphics cards to solve these problems faster without needing complex matrix factorizations. Their approach uses new math tricks to update the solution efficiently and guarantees reliable progress. Tests show that this solver works well on real and synthetic large problems at different accuracy levels.
What this means in practice
- •For operations research teams: Solve large-scale convex quadratic programs faster in industries like logistics and finance using GPU acceleration without complex matrix decompositions.
- •For machine learning engineers: Accelerate training tasks requiring large quadratic optimization problems by integrating a GPU-first order solver optimized for sparse data.
Authors
Haihao Lu, Zedong Peng, Jinwen Yang
Abstract
We present cuPDQPx, a GPU-accelerated, factorization-free first-order solver for large-scale convex quadratic programming (QP). Building on the restarted reflected Halpern primal-dual framework of cuPDLPx, we introduce an auxiliary-variable splitting that yields explicit updates without linearizing the quadratic objective or solving inner quadratic subproblems. A preconditioned proximal point interpretation yields both sublinear and linear fixed-point residual convergence guarantees. For practical efficiency, cuPDQPx integrates diagonal preconditioning, step-size selection, adaptive restart, and adaptive primal and quadratic weight updates. cuPDQPx is implemented in C and CUDA with optimized sparse matrix-vector products, kernel fusion, and CUDA Graphs. Numerical experiments on the Maros-Mészáros collection, a convex subset of QPLIB, and synthetic large-scale QPs demonstrate that cuPDQPx has strong numerical performance at both $10^{-4}$ and $10^{-8}$ tolerances.