Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints

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 (m²) 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/ (m) ) approximation, which is analogous to a result of Nemirovski et al. Math. Program. , 86 (1999), pp. 463–473 for the real case.