Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones
Polynomial-sized semidefinite representations of derivative relaxations of spectrahedral cones
复制标题
谱面锥导数弛豫的多项式大小半定表示
DOI：
10.1007/s10107-014-0804-y
复制
发表时间：
2012
影响因子：
2.7
通讯作者：
P. Parrilo
中科院分区：
文献类型：
--
作者：
J. Saunderson;P. Parrilo
我们给明确的多项式大小（在$$n和$k）半定表示的双曲锥与初等对称多项式的次数$k在$n变量。这些凸锥形成非负正交的非多面体外近似的家庭，保留低维的面，而连续丢弃高维的面。更一般地说，我们构造了双曲锥的显式半定表示（在$$k，m$$k，m和$n$$n中的多项式大小），这些表示与以下形式的多项式的$$k$$k方向导数相关联：$$p（x）=\det（\sum _{i=1}^{n}A_i x_i）$$p（x）=\det（∑i= 1 nAixi）其中$A_i$$Ai是$$m\times m$m×m对称矩阵。这些凸锥形成了一个类似的家庭外近似任何光谱面体锥。我们的表示允许我们使用半定规划来解决与这些凸锥以及它们的（不太好理解的）对偶锥相关的线性锥规划。
We give explicit polynomial-sized (in $$n$$n and $$k$$k) semidefinite representations of the hyperbolicity cones associated with the elementary symmetric polynomials of degree $$k$$k in $$n$$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$$k,m, and $$n$$n) of the hyperbolicity cones associated with $$k$$kth directional derivatives of polynomials of the form $$p(x)=\det (\sum _{i=1}^{n}A_i x_i)$$p(x)=det(∑i=1nAixi) where the $$A_i$$Ai are $$m\times m$$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.