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.
@cite_4: We prove that the hyperbolicity cones of elementary symmetric polynomials are spectrahedral, i.e., they are slices of the cone of positive semidefinite matrices. The proof uses the matrix-tree theorem, an idea already present in
Recently Br "a nd 'e n @cite_4 settled this conjecture in the affirmative giving spectrahedral representations of @math for @math of size @math . For each @math Br "a nd 'e n constructs a graph @math together with edge weights @math that are linear forms in @math so that where @math is the @math edge-weighted Laplacian of @math . Since @math is linear in the edge weights, and the edge weights are linear forms in @math , is a spectrahedral representation of size @math . With the exception of two distinguished vertices, the vertices of @math are indexed by all @math -tuples (for @math ) consisting of distinct elements of @math . Hence @math showing that Br "a nd 'e n's spectrahedral representation of @math has size @math . While Br "a nd 'e n's construction is of considerable theoretical interest, these representations (unlike ours) are not practical for optimization due to their prohibitive size.