Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone

Understand

We develop a practical semidefinite programming (SDP) facial reduction procedure that utilizes computationally efficient approximations of the positive semidefinite cone.

• The proposed method simplifies SDPs with no strictly feasible solution (a frequent output of parsers) by solving a sequence of easier optimization problems and could be a useful pre-processing technique for SDP solvers.
• We demonstrate effectiveness of the method on SDPs arising in practice, and describe our publicly-available software implementation.
• We also show how to find maximum rank matrices in our PSD cone approximations (which helps us find maximal simplifications), and we give a post-processing procedure for dual solution recovery that generally applies to facial-reduction-based pre-processing techniques.