  


Complete Facial Reduction in One Step for Spectrahedra
Stefan Sremac(ssremacuwaterloo.ca) Abstract: A spectrahedron is the feasible set of a semidefinite program, SDP, i.e., the intersection of an affine set with the positive semidefinite cone. While strict feasibility is a generic property for random problems, there are many classes of problems where strict feasibility fails and this means that strong duality can fail as well. If the minimal face containing the spectrahedron is known, the SDPcan easily be transformed into an equivalent problem where strict feasibility holds and thus strong duality follows as well. The minimal face is fully characterized by the range or nullspace of any of the matrices in its relative interior. Obtaining such a matrix may require many facial reduction steps and is currently not known to be a tractable problem for spectrahedra with singularity degree greater than one. We propose a single parametric optimization problem with a resulting type of central path and prove that the optimal solution is unique and in the relative interior of the spectrahedron. Numerical tests illustrate the efficacy of our approach and its usefulness in regularizing SDPs. Keywords: Semidefinite programming, facial reduction, singularity degree, maximizing log det Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Convex and Nonsmooth Optimization (Convex Optimization ) Citation: Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1, October 2017 Download: [PDF] Entry Submitted: 10/19/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  