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 -