Vertices of Spectrahedra arising from the Elliptope, the Theta Body, and Their Relatives

2013/09/28 by Marcel K. de Carli Silva, Silva, Marcel K. de Carli, Levent Tunçel +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Control (math.OC) #math.CO #math.MG #math.OC

paper · pdf · doi:10.48550/arxiv.1309.7415

arxiv created 2013/09/28 · arxiv updated 2013/10/01

Abstract

Utilizing dual descriptions of the normal cone of convex optimization problems in conic form, we characterize the vertices of semidefinite representations arising from Lovász theta body, generalizations of the elliptope, and related convex sets. Our results generalize vertex characterizations due to Laurent and Poljak from the 1990's. Our approach also leads us to nice characterizations of strict complementarity and to connections with some of the related literature.

Related

• Positive Polynomials and Projections of Spectrahedra
• Spectrahedral Lifts of Convex Sets
• Deciding polyhedrality of spectrahedra
• A Note on the Convex Hull of Finitely Many Projections of Spectrahedra
• The extremal volume ellipsoids of convex bodies, their symmetry properties, and their determination in some special cases