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_11: Hyperbolic polynomials have their origins in partial differential equations. We show in this paper that they have applications in interior point methods for convex programming. Each homogeneous hyperbolic polynomial p has an associated open and convex cone called its hyperbolicity cone. We give an explicit representation of this cone in terms of polynomial inequalities. The function Fx = -log px is a logarithmically homogeneous self-concordant barrier function for the hyperbolicity cone with barrier parameter equal to the degree of p. The function Fx possesses striking additional properties that are useful in designing long-step interior point methods. For example, we show that the long-step primal potential reduction methods of Nesterov and Todd and the surface-following methods of Nesterov and Nemirovskii extend to hyperbolic barrier functions. We also show that there exists a hyperbolic barrier function on every homogeneous cone.
From a computational perspective, G " u ler @cite_11 showed that if @math has degree @math and is hyperbolic with respect to @math then @math is a self-concordant barrier function (with barrier parameter @math ) for the hyperbolicity cone @math . As such, as long as @math and its gradient and Hessian can be computed efficiently, one can use interior point methods to minimize a linear functional over an affine slice of @math efficiently. Renegar [Section 9] renegar2006hyperbolic gave an efficient interpolation-based method for computing @math (and its gradient and Hessian) whenever @math (and its gradient and Hessian) can be evaluated efficiently. G " u ler and Renegar's observations together yield efficient computational methods to optimize a linear functional over an affine slice of a derivative relaxation of a spectrahedral cone. Our results complement these, giving a method to solve optimization problems of this type using existing numerical procedures for semidefinite programming.