Deciding polyhedrality of spectrahedra
arXiv:1102.4367
Abstract
Spectrahedra are linear sections of the cone of positive semidefinite matrices that, as convex bodies, generalize the class of polyhedra. In this paper we investigate the problem of recognizing when a spectrahedron is polyhedral. We reprove a result of Ramana (1998) regarding the structure of spectrahedra and we devise a normal form of representations of spectrahedra. This normal form is effectively computable and leads to an algorithm for deciding polyhedrality.
12 pages, 3 figures; v3: minor improvements; SIAM J. Opt, accepted for publication