Exploiting low-rank structure in semidefinite programming by approximate operator splitting

Abstract

In contrast to many other convex optimization classes, state-of-the-art semidefinite programming solvers are still unable to efficiently solve large-scale instances. This work aims to reduce this scalability gap by proposing a novel proximal algorithm for solving general semidefinite programming problems. The key characteristic of the proposed algorithm is to be able to exploit the low-rank property inherent to several semidefinite programming problems. Exploiting the low-rank structure provides a substantial speedup and allows the operator splitting method to efficiently scale to larger instances. As opposed to other low-rank based methods, the proposed algorithm has convergence guarantees for general semidefinite programming problems. Additionally, an open-source semidefinite programming solver called ProxSDP is made available and its implementation details are discussed. Case studies are presented in order to evaluate the performance of the proposed methodology.

Keywords:

• Semidefinite programming
• operator splitting methods
• inexact fixed point iteration
• approximate proximal point
• convex optimization
• low-rank matrix approximation

Acknowledgements

Firstly, we would like to thank the Brazilian agencies CNPq and CAPES for financial support. We extend many thanks to all members of LAMPS (Laboratory of Applied Mathematical Programming and Statistics), in special Thuener Silva and Raphael Saavedra, for the daily support and fruitful discussions. We would also like to thank the developers of MOI and JuMP for making comparisons between solvers much easier and especially Benoît Legat for helping with ProxSDP's MOI interface.

Disclosure statement

No potential conflict of interest was reported by the author(s).