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 $${\mathcal{O}(r)}$$ -approximation solution of the original bi-quadratic optimization problem, where the constant in $${\mathcal{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.