Spectrahedral relaxations of hyperbolicity cones

Abstract

Let p be a real zero polynomial in n variables. Then p defines a rigidly convex set C(p). We construct a linear matrix inequality of size n+1 in the same n variables that depends only on the cubic part of p and defines a spectrahedron S(p) containing C(p). The proof of the containment uses the characterization of real zero polynomials in two variables by Helton and Vinnikov. We exhibit many cases where C(p)=S(p). In terms of optimization theory, we introduce a small semidefinite relaxation of a potentially huge hyperbolic program. If the hyperbolic program is a linear program, we introduce even a finitely convergent hierachy of semidefinite relaxations. With some extra work, we discuss the homogeneous setup where real zero polynomials correspond to homogeneous polynomials and rigidly convex sets correspond to hyperbolicity cones. The main aim of our construction is to attack the generalized Lax conjecture saying that C(p) is always a spectrahedron. To this end, we conjecture that real zero polynomials in fixed degree can be "amalgamated" and show it in three special cases with three completely different proofs. We show that this conjecture would imply the following partial result towards the generalized Lax conjecture: Given finitely many planes in Rn, there is a spectrahedron containing C(p) that coincides with C(p) on each of these planes. This uses again the result of Helton and Vinnikov.