A Practical and Optimal First-Order Method for Large-Scale Convex Quadratic Programming
提出一种重启加速原始对偶混合梯度方法(rAPDHG)用于求解凸二次规划，其计算瓶颈为矩阵向量乘法，具有线性收敛速度且最优，并开发了开源求解器PDQP.jl，在GPU和CPU上均有效。
Abstract Convex quadratic programming (QP) is an important class of optimization problem with wide applications in practice. The classic QP solvers are based on either simplex or barrier method, both of which suffer from the scalability issue because their computational bottleneck is solving linear equations. In this paper, we design and analyze a first-order method for QP, called restarted accelerated primal-dual hybrid gradient (rAPDHG), whose computational bottleneck is matrix-vector multiplication. We show that rAPDHG has a linear convergence rate to an optimal solution when solving QP, and the obtained linear rate is optimal among a wide class of primal-dual methods. Furthermore, we connect the linear rate with a sharpness constant of the KKT system of QP, which is a standard quantity to measure the hardness of a continuous optimization problem. Numerical experiments demonstrate that both restarts and acceleration can significantly improve the performance of the algorithm. Lastly, we present PDQP.jl, an open-source solver based on rAPDHG that can be run on both GPU and CPU. With a numerical comparison with SCS and OSQP on standard QP benchmark sets and large-scale synthetic QP instances, we demonstrate the effectiveness of rAPDHG for solving QP.