Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation

Paul Tseng (tsengmath.washington.edu)

Abstract: 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.

Keywords: Quadratically constrained quadratic optimization, semidefinite programming relaxation, approximation algorithm

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Report, Department of Mathematics, University of Washington, Seattle, October 2001

Download: [Postscript][Compressed Postscript]

Entry Submitted: 12/17/2001
Entry Accepted: 12/18/2001
Entry Last Modified: 12/17/2001

Modify/Update this entry