Semidefinite Relaxation for Quadratic and Quartic Optimization with Applications to Wireless Communication

Abstract

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 the semidefinite programming 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 one (namely, outer products of some given so-called {\it 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. When the homogeneous quadratic constraints are separable and $m=n$, we show that the SDP relaxation is actually tight. All theoretical results will be illustrated through a transmit beamforming application in wireless communication.