Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Complete Facial Reduction in One Step for Spectrahedra
arXiv.org
20 Oct 2017
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.
Metrics
7 Record Views
Details
- Title
- Complete Facial Reduction in One Step for Spectrahedra
- Creators
- Stefan SremacHugo WoerdemanHenry Wolkowicz
- Publication Details
- arXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021866368704721