May 5, 2015, 2:00pm
Frank Permenter, EECS Department, MIT.
Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
Abstract: Semidefinite programs (SDPs) arising in practice frequently have no interior and hence can be reformulated as smaller problems more easily solved. Unfortunately, finding these reformulations requires executing a facial reduction procedure, which is typically computationally expensive. In this talk, we develop a practical facial reduction procedure based on computationally efficient approximations of the positive semidefinite cone. The proposed method simplifies SDPs with no interior by solving a sequence of easier optimization problems (e.g. linear programs) and could be a useful pre-processing step for SDP solvers. We demonstrate effectiveness of the method on SDPs arising in practice, and describe our publicly-available software implementation. We also give a post-processing procedure for dual solution recovery that generally applies to facial-reduction-based pre-processing techniques. Joint work with Pablo Parrilo.