A Dual Riemannian Augmented Lagrangian Method for Low-Rank SDPs with Unit Diagonal

Abstract

We propose ManiDSDP, a dual Riemannian augmented Lagrangian method for solving low-rank semidefinite programs in the dual form whose positive semidefinite variable has unit diagonal. The method first eliminates the unconstrained variable by a variable projection, expresses affine consistency through an orthogonal-projector residual, and then applies the Burer--Monteiro factorization. The resulting subproblems are optimization problems on the oblique manifold and are solved by a Riemannian trust-region method with dynamic rank adjustment. A negative-curvature direction extracted from the certificate of a completed subproblem is carried into the next subproblem, leading to a one-step-delayed curvature-correction design. Under controlled inner errors, we prove that every cluster point returned by the method is a KKT point. Under additional full-sequence convergence, strict complementarity, and finite-tail exact complementarity, the iterations identify the rank of the limiting solution in finitely many steps. Under a strictly complementary rank-one solution, we further establish a local one-step locking theorem, providing a mechanism for the observed residue diving phenomenon. Numerical experiments on dense and sparse BQPs and on UCQPs demonstrate high accuracy and favorable efficiency and scalability relative to MOSEK, SDPNAL+, and ManiSDP.

30 pages, 4 figures, 4 tables