Further Results on Approximating Nonconvex Quadratic Optimizationby Semidefinite Programming Relaxation

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

Article

Download

View Further Results on Approximating Nonconvex Quadratic Optimizationby Semidefinite Programming Relaxation