An Improved Analysis of Semidefinite Approximation Bound for Nonconvex Nonhomogeneous Quadratic Optimization with Ellipsoid Constraints
arXiv:1410.3571 · doi:10.1016/j.orl.2015.05.002
Abstract
We consider the problem of approximating nonconvex quadratic optimization with ellipsoid constraints (ECQP). We show some SDP-based approximation bounds for special cases of (ECQP) can be improved by trivially applying the extened Pataki's procedure. The main result of this paper is to give a new analysis on approximating (ECQP) by the SDP relaxation, which greatly improves Tseng's result [SIAM Journal Optimization, 14, 268-283, 2003]. As an application, we strictly improve the approximation ratio for the assignment-polytope constrained quadratic program.
12 pages