  


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 rank1 decomposition result of Sturm and Zhang, yields a feasible solution of the original problem with objective value at most (1gamma)^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 trustregion 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 (Semidefinite Programming ) Citation: Report, Department of Mathematics, University of Washington, Seattle, October 2001 Download: [Postscript][Compressed Postscript] Entry Submitted: 12/17/2001 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  