Answers are grounded in this paper and cite their sources.
We study approximation bounds for the semidefinite programming (SDP) relaxation ofquadratically constrained quadratic optimization: min 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 γ=√[b]maxₖ 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.
No takes yet. Share an insight, caveat, or question.
Paul Tseng (2003) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: