TY - JOUR

T1 - Semidefinite relaxation bounds for indefinite homogeneous quadratic optimization

AU - He, Simai

AU - Luo, Zhi Quan

AU - Nie, Jiawang

AU - Zhang, Shuzhong

PY - 2008/6

Y1 - 2008/6

N2 - 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.

AB - 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.

KW - Approximation ratio

KW - Probabilistic solution

KW - Quadratic optimization

KW - SDP relaxation

UR - http://www.scopus.com/inward/record.url?scp=61449222263&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=61449222263&partnerID=8YFLogxK

U2 - 10.1137/070679041

DO - 10.1137/070679041

M3 - Article

AN - SCOPUS:61449222263

SN - 1052-6234

VL - 19

SP - 503

EP - 523

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 2

ER -