Modified Interior-Point Method for Large-and-Sparse Low-Rank Semidefinite Programs
For practitioners solving large-scale SDPs in fields like graph theory and control theory, this work provides a practical algorithm that dramatically improves scalability.
This paper presents a modified interior-point method for large-and-sparse low-rank semidefinite programs, using a preconditioned conjugate gradient approach that corrects a low-rank perturbation in the Hessian matrix. The method reduces solution time and memory requirements for large-scale matrix-completion problems by several orders of magnitude.
Semidefinite programs (SDPs) are powerful theoretical tools that have been studied for over two decades, but their practical use remains limited due to computational difficulties in solving large-scale, realistic-sized problems. In this paper, we describe a modified interior-point method for the efficient solution of large-and-sparse low-rank SDPs, which finds applications in graph theory, approximation theory, control theory, sum-of-squares, etc. Given that the problem data is large-and-sparse, conjugate gradients (CG) can be used to avoid forming, storing, and factoring the large and fully-dense interior-point Hessian matrix, but the resulting convergence rate is usually slow due to ill-conditioning. Our central insight is that, for a rank-$k$, size-$n$ SDP, the Hessian matrix is ill-conditioned only due to a rank-$nk$ perturbation, which can be explicitly computed using a size-$n$ eigendecomposition. We construct a preconditioner to "correct" the low-rank perturbation, thereby allowing preconditioned CG to solve the Hessian equation in a few tens of iterations. This modification is incorporated within SeDuMi, and used to reduce the solution time and memory requirements of large-scale matrix-completion problems by several orders of magnitude.