Semidefinite relaxation approximation for multivariate bi-quadratic optimization with quadratic constraints

In this paper, we consider the NP-hard problem of finding global minimum of quadratically constrained multivariate bi-quadratic optimization. We present some bounds of the considered problem via approximately solving the related bi-linear semidefinite programming (SDP) relaxation. Based on the bi-linear SDP relaxation, we also establish some approximation solution methods, which generalize the methods for the quadratic polynomial optimization in (SIAM J. Optim. 2003; 14:268-283). Finally, we present a special form, whose bi-linear SDP relaxation can be approximately solved in polynomial time.