GPU-Accelerated Conic Quadratic Programming with Local Linear Convergence under Strict Complementarity
2026-08-10 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster ComputingMathematical Software
AI summaryⓘ
The authors developed PDHCG-CQP, a fast solver that runs on GPUs for solving big problems involving convex quadratic programming with various cone constraints. Their method uses a special iterative approach combining primal-dual updates and approximate solving of smaller subproblems, and they proved it converges quickly under certain mathematical conditions. The implementation uses advanced GPU techniques and supports multi-GPU setups to handle very large problem sizes efficiently. Their tests show that PDHCG-CQP is reliable and scalable compared to other first-order methods. The solver is freely available as open-source software.
convex quadratic programmingprimal-dual hybrid gradient (PDHG)cone programmingsecond-order coneproximal methodsGPU accelerationlocal linear convergenceKKT residualsmulti-GPUrotated second-order cone
Authors
Hongpei Li, Yicheng Huang, Huikang Liu, Dongdong Ge, Yinyu Ye
Abstract
We present PDHCG-CQP, a GPU-accelerated first-order solver for large-scale conic convex quadratic programming. PDHCG-CQP supports affine constraints and Cartesian products of nonnegative, second-order, rotated second-order, exponential, and three-dimensional power cones. At its core is a restarted averaged primal-dual hybrid gradient (PDHG) method, whose primal update is computed inexactly by solving a conic quadratic proximal subproblem with projected gradient iterations. We establish local linear convergence of the restarted averaged scheme with both exact and inexact primal proximal evaluations under a uniform local quadratic-growth condition on the smoothed primal-dual gap. We further show that this condition holds under strict complementarity by exploiting a rotated second-order-cone lifting together with local primal and dual regularity conditions. Our C/CUDA implementation combines matrix-free linear algebra, batched cone projections, adaptive inner solves, reflected-Halpern acceleration, and fully device-resident KKT residual computations. It also supports multi-GPU execution through a two-dimensional partitioning of the problem data. Extensive experiments on standard and large-scale quadratic programming (QP), convex quadratically constrained quadratic programming (QCQP), second-order cone programming (SOCP), and quasilinear Fisher equilibrium benchmarks demonstrate that PDHCG-CQP achieves state-of-the-art robustness among first-order solvers while scaling efficiently to 8 GPUs and instances with up to $4.4\times10^8$ stored primal coordinates. PDHCG-CQP is open source and available at https://github.com/Lhongpei/PDHCG.