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^2)$ 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 $\pi/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.