A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints

We present a general semidefinite relaxation scheme for general n-variate quartic polynomial optimization under homogeneous quadratic constraints. Unlike the existing sum-ofsquares 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 R ^n×n. It is shown that each α-factor approximate solution of the relaxed quadratic SDP can be used to generate in randomized polynomial time an O(α)-factor approximate solution for the original quartic optimization problem, where the constant in O(-) depends only on problem dimension. In the case where only one positive definite quadratic constraint is present in the quartic optimization problem, we present a randomized polynomial time approximation algorithm which can provide a guaranteed relative approximation ratio of (1 - O(n^-2)).