Optimization Online


Complete Facial Reduction in One Step for Spectrahedra

Stefan Sremac(ssremac***at***uwaterloo.ca)
Hugo Woerdeman(hugo***at***math.drexel.edu)
Henry Wolkowicz(hwolkowi***at***uwaterloo.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 (Semi-definite 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
Entry Accepted: 10/19/2017
Entry Last Modified: 10/19/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society