Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones

• 成果类型: Article
• 署名作者: Saunderson, James; Parrilo, Pablo A.
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0804-y
• 发表日期: 2015
• 页码: 309-331
• 关键词: elementary symmetric polynomials; hyperbolic polynomials; sets; INEQUALITY

摘要

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 kth directional derivatives of polynomials of the form p(x) = det(Sigma(n)(i=1) A(i) x(i)) where the A(i) are m x 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.