Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints

摘要

This paper studies the relationship between the so-called bi-quadratic optimization problem and its semidefinite programming (SDP) relaxation. It is shown that each r-bound approximation solution of the relaxed bi-linear SDP can be used to generate in randomized polynomial time an O(r)-approximation solution of the original bi-quadratic optimization problem, where the constant in O(r) does not involve the dimension of variables and the data of problems. For special cases of maximization model, we provide an approximation algorithm for the considered problems.