A Low-Rank ADMM Splitting Approach for Semidefinite Programming

We introduce a new first order method for solving the semidefinite programming (SDP) problem with a convex and differentiable objective based on the alternating direction method of multipliers (ADMM) and a matrix-splitting technique. Our algorithm has an advantage over the Burer–Monteiro (BM) approach as it involves much easier quadratically regularized subproblems in each iteration. For a linear objective, the subproblems are well-conditioned quadratic programs that can be efficiently solved by the standard conjugate gradient method. We show that our algorithm achieves sublinear or linear convergence rates to the Karush–Kuhn–Tucker solutions under different conditions. Based on this theoretical development, we present LoRADS, a new solver for linear SDP based on the low-rank ADMM splitting approach. LoRADS applies several strategies to significantly improve its efficiency. First, it initiates with a warm-start phase that uses the BM approach. Moreover, motivated by the advances on the SDP low-rank theory, LoRADS chooses an initial rank of logarithmic order and employs a dynamic approach to increase the rank. Although LoRADS does not necessarily ensure global optimality, it performs well on many important and large-scale problems, such as MaxCut and matrix completion. Notably, LoRADS solved (i) a MaxCut problem with the dimension of 1,048,576 in less than seven minutes and (ii) a matrix completion problem with 71,681,424 constraints and a 180,000 × 180,000 matrix in about half an hour, achieving accuracies below 1e-5 for both problems.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous.

Funding: C. Li, Z. Lin, and D. Ge were supported in part by the National Natural Science Foundation of China [Grants 72225009, 72394360, and 72394365]. C. Chen was supported in part by the National Natural Science Foundation of China [Grants 72394363/72394360, 12431011 and 12122107] and the Fundamental Research Funds for the Central Universities. Q. Deng was supported in part by the National Natural Science Foundation of China [Grants 72394364/72394360 and 12571325] and the Natural Science Foundation of Shanghai [Grant 24ZR1421300]. H. Liu was supported in part by the Young Elite Scientists Sponsorship Program [Grant CAST 2023QNRC001] and the National Natural Science Foundation of China [Grants NSFC-72192830 and 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.0701) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0701). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.