Title: A Semidefinite Relaxation Scheme for Multivariate Quartic Polynomial Optimization With Quadratic Constraints

We present a general semidefinite relaxation scheme for n-variate quartic polynomial optimization under homogeneous quadratic constraints. Unlike the existing sum-of-squares (SOS) approach which relaxes the quartic optimization problems to a sequence of (typically large) linear semidefinite programs (SDP), our relaxation scheme leads to a (possibly nonconvex) quadratic optimization problem with linear constraints over the semidefinite matrix cone in $\Re^{n x n}$. It is shown that each $\alpha$-approximate solution of the relaxed quadratic SDP can be used to generate in randomized polynomial time an O(\alpha)-approximate solution for the original quartic optimization problem, where the constant in O(\cdot) depends only on problem dimension.
In the case where only one positive definite quadratic constraint is present, we provide a polynomial time \Omega(n^{-2})-approximation algorithm for the quartic maximization problem.