Polynomial-sized Semidefinite Representations of Derivative Relaxations of Spectrahedral Cones

Abstract

We give explicit polynomial-sized (in $n$ and $k$) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree $k$ in $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 $k,m$, and $n$) of the hyperbolicity cones associated with $k$th directional derivatives of polynomials of the form $p(x)=\det ({\sum }_{i=1}^n{A}_i{x}_i)$ where the $A_i$ are $m\times 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.

20 pages, 1 figure. Minor changes, expanded proof of Lemma 9

References in corpus (2)

• Lifts of convex sets and cone factorizations
• The Lax conjecture is true

Cited by in corpus (7)

• Spectral linear matrix inequalities
• Absolutely $k$-Incoherent Quantum States and Spectral Inequalities for Factor Width of a Matrix
• Approximate cone factorizations and lifts of polytopes
• A spectrahedral representation of the first derivative relaxation of the positive semidefinite cone
• Symbolic computation in hyperbolic programming
• Automorphisms of rank-one generated hyperbolicity cones and their derivative relaxations
• Spectral Polyhedra