2024/04/22 by Chu, Ya-Chi, Santos, Luiz-Rafael, Udell, Madeleine · 1 citation
#65F08 #90C06 #90C20 #90C51 #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2404.14524
We present a new algorithm for convex separable quadratic programming (QP) called Nys-IP-PMM, a regularized interior-point solver that uses low-rank structure to accelerate solution of the Newton system. The algorithm combines the interior point proximal method of multipliers (IP-PMM) with the randomized Nyström preconditioned conjugate gradient method as the inner linear system solver. Our algorithm is matrix-free: it accesses the input matrices solely through matrix-vector products, as opposed to methods involving matrix factorization. It works particularly well for separable QP instances with dense constraint matrices. We establish convergence of Nys-IP-PMM. Numerical experiments demonstrate its superior performance in terms of wallclock time compared to previous matrix-free IPM-based approaches.