Deciding Polyhedrality of Spectrahedra
Avinash Bhardwaj, Philipp Rostalski, Raman Sanyal · SIAM Journal on Optimization · 2015
Spectrahedra are linear sections of the cone of positive semidefinite matrices which, as convex bodies, generalize the class of polyhedra. In this paper we investigate the problem of recognizing when a spectrahedron is polyhedral. We generalize and strengthen results of [M. V. Ramana, Polyhedra, spectrahedra, and semidefinite programming, in Topics in Semidefinite and Interior-Point Methods, Fields Inst. Commun. 18, AMS, Providence, RI, 1998, pp. 27--38] 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.