A Dual Riemannian ADMM Algorithm for Low-Rank SDPs with Unit Diagonal
Preprint
Abstract
This paper proposes a dual Riemannian alternating direction method of multipliers (ADMM) for solving low-rank semidefinite programs with unit diagonal constraints. We recast the ADMM subproblem as a Riemannian optimization problem over the oblique manifold by performing the Burer-Monteiro factorization. Global convergence of the algorithm is established assuming that the subproblem is solved to certain optimality. Numerical experiments demonstrate the excellent performance of the algorithm. It outperforms, by a significant margin, a few advanced SDP solvers (MOSEK, COPT, SDPNAL+, ManiSDP) in terms of accuracy, efficiency, and scalability on second-order SDP relaxations of dense and sparse binary quadratic programs.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Solving Low-Rank Semidefinite Programs via Manifold OptimizationJournal of Scientific Computing, 2025
- Local Geometry Determines Global Landscape in Low-Rank Factorization for SynchronizationFoundations of Computational Mathematics, 2025
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimizationMathematical Programming, 2022
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysisMathematical Programming, 2022
- COSMO: A Conic Operator Splitting Method for Convex Conic ProblemsJournal of Optimization Theory and Applications, 2021
- Chordal decomposition in operator-splitting methods for sparse semidefinite programsMathematical Programming, 2019
- Phase recovery, MaxCut and complex semidefinite programmingMathematical Programming, 2013
- Trust-Region Methods on Riemannian ManifoldsFoundations of Computational Mathematics, 2006
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorizationMathematical Programming, 2003
- On implementing a primal-dual interior-point method for conic quadratic optimizationMathematical Programming, 2003