Exploiting low-rank structure in semidefinite programming by approximate operator splitting. (2nd January 2022)

• Record Type: Journal Article
• Authors: Souto, Mario; Garcia, Joaquim D.; Veiga, Álvaro
• Is Part Of: Optimization. Volume 71:Number 1(2022)
• Page Start: 117
• Page End: 144
• Publication Date: 2022-01-02
• Subjects: Semidefinite programming -- operator splitting methods -- inexact fixed point iteration -- approximate proximal point -- convex optimization -- low-rank matrix approximation; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1823387
• Languages: English
• ISSNs: 0233-1934

Abstract

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.