Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization

Simai He, Zhi Quan Luo, Jiawang Nie, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

72 Scopus citations

Abstract

This paper studies the relationship between the optimal value of a homogeneous quadratic optimization problem and its semidefinite programming (SDP) relaxation. We consider two quadratic optimization models: (1) min{x*Cx * Akx ≥ 1, k = 0,1,..., m, x € F n} and (2) max{x*Cx | x* Akx ≤ 1, k = 0,1,..., m, x € F n}, where F is either the real field R or the complex field C, and Ak,C are symmetric matrices. For the minimization model (1), we prove that if the matrix C and all but one of the Ak's are positive semidefinite, then the ratio between the optimal value of (1) and its SDP relaxation is upper bounded by 0(m 2) when F = R, and by 0(m) when F = C. Moreover, when two or more of the Ak's are indefinite, this ratio can be arbitrarily large. For the maximization model (2), we show that if C and at most one of the A3/4 's are indefinite while other Ak's are positive semidefinite, then the ratio between the optimal value of (2) and its SDP relaxation is bounded from below by 0(1/ logm) for both the real and the complex case. This result improves the bound based on the so-called approximate S-Lemma of Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535-560]. When two or more of the Ak's in (2) are indefinite, we derive a general bound in terms of the problem data and the SDP solution. For both optimization models, we present examples to show that the derived approximation bounds are essentially tight.

Original languageEnglish (US)
Pages (from-to)503-523
Number of pages21
JournalSIAM Journal on Optimization
Volume19
Issue number2
DOIs
StatePublished - Jun 2008

Keywords

  • Approximation ratio
  • Probabilistic solution
  • Quadratic optimization
  • SDP relaxation

Fingerprint

Dive into the research topics of 'Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization'. Together they form a unique fingerprint.

Cite this