A Restarted Primal-Dual Hybrid Conjugate Gradient Method for Large-Scale Quadratic Programming

Convex quadratic programming (QP) is an essential class of optimization problems with broad applications across various fields. Traditional QP solvers, typically based on simplex or barrier methods, face significant scalability challenges. In response to these limitations, recent research has shifted toward matrix-free first order methods to enhance scalability in QP. Among these, the restarted accelerated primal-dual hybrid gradient (rAPDHG) method proposed by Lu and Yang has recently gained notable attention because of its linear convergence rate to an optimal solution and its straightforward implementation on graphics processing units (GPUs). Building on this framework, this paper introduces a restarted primal-dual hybrid conjugate gradient (PDHCG) method, which incorporates conjugate gradient techniques to address the primal subproblems inexactly. We demonstrate that PDHCG maintains a linear convergence rate with an improved convergence constant and is also straightforward to implement on GPUs. Extensive numerical experiments on both synthetic and real-world data sets demonstrate that our method significantly reduces the number of iterations required to achieve the desired accuracy compared with rAPDHG. Additionally, the GPU implementation of our method achieves state-of-the-art performance on large-scale problems. In large-scale scenarios, our method demonstrates superior performance compared with existing methods. These results highlight the substantial potential of the proposed PDHCG method to greatly improve both the efficiency and scalability of solving complex quadratic programming challenges.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: Y. Huang, W. Zhang, H. Li, and D. Ge were supported in part by the National Natural Science Foundation of China (NSFC) [Grants 72225009, 72394360, 72394365]. H. Liu was also supported in part by the NSFC [Grants 12301403, 72192830, 72192832].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0983) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0983). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.