TY - JOUR

T1 - Approximation bounds for quadratic optimization with homogeneous quadratic constraints

AU - Luo, Zhi Quan

AU - Sidiropoulos, Nicholas D.

AU - Tseng, Paul

AU - Zhang, Shuzhong

PY - 2007/12/1

Y1 - 2007/12/1

N2 - We consider the NP-hard problem of finding a minimum norm vector in n-dimensional real or complex Euclidean space, subject to m concave homogeneous quadratic constraints. We show that a semidefinite programming (SDP) relaxation for this nonconvex quadratically constrained quadratic program (QP) provides an O(m2) approximation in the real case and an O(m) approximation in the complex case. Moreover, we show that these bounds are tight up to a constant factor. When the Hessian of each constraint function is of rank 1 (namely, outer products of some given so-called steering vectors) and the phase spread of the entries of these steering vectors are bounded away from π/2, we establish a certain "constant factor" approximation (depending on the phase spread but independent of m and n) for both the SDP relaxation and a convex QP restriction of the original NP-hard problem. Finally, we consider a related problem of finding a maximum norm vector subject to m convex homogeneous quadratic constraints. We show that an SDP relaxation for this nonconvex QP provides an O(1/ ln(m)) approximation, which is analogous to a result of Nemirovski et al. [Math. Program., 86 (1999), pp. 463-473] for the real case.

AB - We consider the NP-hard problem of finding a minimum norm vector in n-dimensional real or complex Euclidean space, subject to m concave homogeneous quadratic constraints. We show that a semidefinite programming (SDP) relaxation for this nonconvex quadratically constrained quadratic program (QP) provides an O(m2) approximation in the real case and an O(m) approximation in the complex case. Moreover, we show that these bounds are tight up to a constant factor. When the Hessian of each constraint function is of rank 1 (namely, outer products of some given so-called steering vectors) and the phase spread of the entries of these steering vectors are bounded away from π/2, we establish a certain "constant factor" approximation (depending on the phase spread but independent of m and n) for both the SDP relaxation and a convex QP restriction of the original NP-hard problem. Finally, we consider a related problem of finding a maximum norm vector subject to m convex homogeneous quadratic constraints. We show that an SDP relaxation for this nonconvex QP provides an O(1/ ln(m)) approximation, which is analogous to a result of Nemirovski et al. [Math. Program., 86 (1999), pp. 463-473] for the real case.

KW - Approximation bound

KW - Nonconvex quadratic optimization

KW - Semidefinite programming relaxation

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

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

U2 - 10.1137/050642691

DO - 10.1137/050642691

M3 - Article

AN - SCOPUS:39449091997

VL - 18

SP - 1

EP - 28

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 1

ER -