An Optimal-Storage Approach to Semidefinite Programming using Approximate Complementarity

Understand

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.