Semidefinite relaxation of . . .

In recent years, the semidefinite relaxation (SDR) technique has been at the center of some of very exciting developments in the area of signal processing and communications, and it has shown great significance and relevance on a variety of applications. Roughly speaking, SDR is a powerful, computationally efficient approximation technique for a host of very difficult optimization problems. In particular, it can be applied to many nonconvex quadratically constrained quadratic programs (QCQPs) in an almost mechanical fashion, including the following problem: min x[Rn xTCx s.t. xTFi x $ gi, i5 1,c, p, xTHi x5 li, i5 1,c, q, (1) where the given matrices C, F1,c, Fp, H1,c, Hq are assumed to be general real symmetric matrices, possibly indefinite. The class of nonconvex QCQPs (1) captures many problems that are of interest to the signal process-ing and communications community. For instance, con-sider the Boolean quadratic program (BQP) min x[Rn xTCx s.t. xi 2 5 1, i5 1,c, n. (2) The BQP is long known to be a computationally difficult problem. In particular, it belongs to the class of NP-hard problems. Nevertheless, being able to handle the BQP well has an enormous impact on multiple-input, multiple-output (MIMO) detection and multiuser detection. Another important yet NP-hard problem in the nonconvex QCQP class (1) i