We give explicit polynomial-sized (in @math n and @math k) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree @math k in @math n variables. These convex cones form a family of non-polyhedral outer approximations of the non-negative orthant that preserve low-dimensional faces while successively discarding high-dimensional faces. More generally we construct explicit semidefinite representations (polynomial-sized in @math k,m, and @math n) of the hyperbolicity cones associated with @math kth directional derivatives of polynomials of the form @math p(x)=det(?i=1nAixi) where the @math Ai are @math m×m symmetric matrices. These convex cones form an analogous family of outer approximations to any spectrahedral cone. Our representations allow us to use semidefinite programming to solve the linear cone programs associated with these convex cones as well as their (less well understood) dual cones.
A spectrahedral representation of @math is implicit in the work of @cite_2 that studies the relationships between matroids and hyperbolic polynomials. observe that if @math is a matroid represented by the rows of a totally unimodular matrix @math then @math is the basis generating polynomial of @math . In particular, the uniform matroid @math is regular and has @math as its basis generating polynomial, yielding a symmetric determinantal representation of @math and hence a spectrahedral representation of @math .
@cite_2
1488782662
We study the convex hull of @math , the set of @math orthogonal matrices with unit determinant, from the point of view of semidefinite programming. We show that the convex hull of @math is doubly spectrahedral, i.e., both it and its polar have a description as the intersection of a cone of positive semidefinite matrices with an affine subspace. Our spectrahedral representations are explicit and are of minimum size, in the sense that there are no smaller spectrahedral representations of these convex bodies.