Approximating global quadratic optimization with convex quadratic constraints

Yinyu Ye

We consider the problem of approximating the global maximum of a quadratic program (QP) subject to convex non-homogeneous quadratic constraints. We prove an approximation quality bound that is related to a condition number of the convex feasible set; and is the currently best for approximating certain problems, such as quadratic optimization over the assignment polytope.

Working Paper, Department of Management Sciences, The University of Iowa, Iowa City, Iowa 52242, U.S.A.