Semidefinite Relaxations of Products of Nonnegative Forms
We study the problem of maximizing the geometric mean of d low-degree non-negative forms on the real or complex sphere in n variables. This problem generalizes many different problems in optimization, such as Kantorovich's inequality, optimizing monomials over the sphere, linear polarization constants for Hilbert spaces, approximating permanents of PSD matrices, certifying feasibility for systems of quadratic equations and bounding the relative entropy distance between a quadratic map and its convex hull. This problem is equivalent to optimizing a homogeneous polynomial of degree O(d) on the sphere and we show that it is NP-hard to approximate even when the forms are quadratic. The standard Sum-of-Squares based convex relaxation for this polynomial optimization problem requires solving a semidefinite program (SDP) of size n^O(d), with multiplicative approximation guarantees of Omega(1/n). We exploit the compact representation of this polynomial to introduce a SDP relaxation of size polynomial in n and d, and prove that it achieves a constant factor multiplicative approximation when maximizing the geometric mean of PSD quadratic forms. We also show that this analysis is asymptotically tight, with a sequence of instances where the gap between the relaxation and true optimum approaches this constant factor as d -> infinity. Next we propose a series of intermediate relaxations of increasing complexity that interpolate to the full Sum-of-Squares relaxation, as well as a rounding algorithm that finds an approximate solution from the solution of any intermediate relaxation. Finally we show that this approach can be generalized for relaxations of products of non-negative forms of any degree. Joint work with Pablo Parrilo.