Improved semidefinite approximation bounds for nonconvex nonhomogeneous quadratic optimization with ellipsoid constraints

We study the problem of approximating nonconvex quadratic optimization with ellipsoid constraints (ECQP) and establish a new semidefinite approximation bound, which greatly improves Tseng’s result (Tseng, 2003). As an application, we strictly improve the approximation ratio for the assignment-polytope constrained quadratic program. Finally, based on a randomized algorithm, we obtain a new approximation bound for (ECQP) which is sharp in the order of the number of the ellipsoid constraints.