1. An Optimal-Storage Approach to Semidefinite Programming Using Approximate Complementarity
- Author
-
Lijun Ding, Alp Yurtsever, Madeleine Udell, Volkan Cevher, and Joel A. Tropp
- Subjects
norm ,FOS: Computer and information sciences ,Computer Science - Machine Learning ,semidefinite programs ,Mathematical optimization ,0211 other engineering and technologies ,MathematicsofComputing_NUMERICALANALYSIS ,Mathematics::Optimization and Control ,010103 numerical & computational mathematics ,02 engineering and technology ,Computer Science::Computational Complexity ,algorithms ,low rank ,01 natural sciences ,Theoretical Computer Science ,Machine Learning (cs.LG) ,power ,Computer Science::Systems and Control ,interior-point methods ,FOS: Mathematics ,0101 mathematics ,Computer Science::Data Structures and Algorithms ,Mathematics - Optimization and Control ,storage optimality ,Mathematics ,Semidefinite programming ,convergence ,021103 operations research ,rank ,Optimization and Control (math.OC) ,Complementarity (molecular biology) ,primal recovery ,complementary slackness ,optimization ,Software - Abstract
This paper develops a new storage-optimal algorithm that provably solves generic semidefinite programs (SDPs) in standard form. This method is particularly effective for weakly constrained SDPs. 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., Comment: 35 pages, 24 pages of main text, 17 figures
- Full Text
- View/download PDF