Semidefinite positive relaxation of the maximum-likelihood criterion applied to multiuser detection in a CDMA context

Many signal processing applications reduce to solving combinatorial optimization problems. Recently, semidefinite programming (SDP) has been shown to be a very promising approach to combinatorial optimization, where SDP serves as a tractable convex relaxation of NP-hard problems. In this paper, we present a nonlinear programming algorithm for solving SDP, based on a change of variables that replaces the symmetrical, positive semidefinite variable X in SDP with a rectangular variable R according to X = RR ^T. Very encouraging results are obtained to solve even large-scale combinatorial optimization programs, as the one arising in multiuser detection for code division multiple access (CDMA) systems.