Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation

We study approximation bounds for the semidefinite programming (SDP) relaxation ofquadratically constrained quadratic optimization: f⁰ (x) subject to fᵏ (x) 0, k=1, , m, where fk (x) =xTAkx+ (bk) Tx+ck. 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 Math. Oper. Res. , to appear, yields a feasible solution of the original problem with objective value at most (1-) ²/ (m+) ² times the optimal objective value, where =ₖ fᵏ (0) +1. 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 Optim. Methods Softw. , 9 (1998), pp. 141--160; working paper, CORE, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1998, Ye Math. Program. , 84 (1999), pp. 219--226, and Nesterov, Wolkowicz, and Ye in Handbook of Semidefinite Programming, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds. , Kluwer Academic Publishers, Dordrecht, The Netherlands, 2000, pp. 360--419 for the special case where Aᵏ is diagonal and bk =0 for k=1,. . . , m. We also discuss the generation of approximate solutions with high probability.