Optimization Online


Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation

Paul Tseng (tseng***at***math.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society