We study approximation bounds for the SDP relaxation of quadratically constrained quadratic optimization: min f^0(x) subject to f^k(x) <= 0, k=1,...,m, where f^k(x)=x'A^kx + (b^k)'x + c^k. In the special case of ellipsoid constraints with interior feasible solution at 0, we show that the SDP relaxation, coupled with a rank-1 decomposition result of Sturm and Zhang, yields a feasible solution of the original problem with objective value at most (1-gamma)^2/(sqrt{m} + gamma)^2 times the optimal objective value, where gamma=sqrt{max_k f^k(0)+1}. If the ellipsoids have a common center, this improves on the estimate 1/( 2 ln(2(m+1)^2) ) of Nemirovski et al. when m<= 11. For the single trust-region problem, corresponding to m=1, this yields an exact optimal solution. In the general case, we extend some bounds derived by Nesterov and Ye for the special case where A^k is diagonal and b^k=0 for k=1,...,m. We also discuss the generation of approximate solutions with high probability.
Citation
Report, Department of Mathematics, University of Washington, Seattle, October 2001