Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 28, 2021 | metadata_only
Journal Article

An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity


This paper develops a new storage-optimal algorithm that provably solves almost all semidefinite programs (SDPs). This method is particularly effective for weakly constrained SDPs under appropriate regularity conditions. The key idea is to formulate an approximate complementarity principle: Given an approximate solution to the dual SDP, the primal SDP has an approximate solution whose range is contained in the eigenspace with small eigenvalues of the dual slack matrix. For weakly constrained SDPs, this eigenspace has very low dimension, so this observation significantly reduces the search space for the primal solution. This result suggests an algorithmic strategy that can be implemented with minimal storage: (1) solve the dual SDP approximately; (2) compress the primal SDP to the eigenspace with small eigenvalues of the dual slack matrix; (3) solve the compressed primal SDP. The paper also provides numerical experiments showing that this approach is successful for a range of interesting large-scale SDPs.

Additional Information

© 2021, Society for Industrial and Applied Mathematics. Received by the editors February 14, 2019; accepted for publication (in revised form) June 10, 2021; published electronically October 28, 2021. The first and fifth authors were supported in part by DARPA award FA8750-17-2-0101. The second author received support through Early Postdoc Mobility Fellowship P2ELP2 187955 from the Swiss National Science Foundation (SNSF) and partial postdoctoral support from NSF-CAREER grant IIS-1846088. The third author received funding for this project from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement 725594-time-data) and from the SNSF under grant 200021 178865/1. The fourth author was supported in part by ONR awards N-00014-11-1002, N-00014-17-12146, and N-00014-18-12363. Parts of this research were conducted while the fifth author was in residence at the Simons Institute and the second author was at EPFL. Ahmet Alacaoglu suggested we consider the Chambolle-Pock method for solving (MinObjSDP) in numerical experiments. We would also like to thank the editor and reviewers for their feedback.

Additional details

August 22, 2023
September 11, 2023