A Practical GPU-Enhanced Matrix-Free Primal-Dual Method for Large-Scale Conic Programs
This provides a practical solution for researchers and practitioners dealing with computationally intensive conic programs, though it is incremental as it builds on existing methods with enhancements.
The authors tackled large-scale conic programming problems by developing a GPU-enhanced matrix-free primal-dual method, resulting in cuPDCS, which outperforms state-of-the-art commercial solvers and other first-order methods in efficiency, scalability, and robustness, especially for large-scale, lower-accuracy settings.
In this paper, we introduce a practical GPU-enhanced matrix-free first-order method for solving large-scale conic programming problems, which we refer to as PDCS, standing for the Primal-Dual Conic Programming Solver. Problems that it solves include linear programs, second-order cone programs, convex quadratic programs, and exponential cone programs. The method avoids matrix factorizations and leverages sparse matrix-vector multiplication as its core computational operation, which is both memory-efficient and well-suited for GPU acceleration. The method builds on the restarted primal-dual hybrid gradient method but further incorporates several enhancements. Additionally, it employs a bisection-based method to compute projections onto rescaled cones. Furthermore, cuPDCS is a GPU implementation of PDCS and it implements customized computational schemes that utilize different levels of GPU architecture to handle cones of different types and sizes. Numerical experiments demonstrate that cuPDCS is generally more efficient than state-of-the-art commercial solvers and other first-order methods on large-scale conic program applications, including Fisher market equilibrium problems, Lasso regression, and multi-period portfolio optimization. Furthermore, cuPDCS also exhibits better scalability, efficiency, and robustness compared to other first-order methods on the conic program benchmark dataset CBLIB. These advantages are more pronounced in large-scale, lower-accuracy settings.