Nonconvex Complex Quadratic Programs: New Semidefinite Relaxations, Global Algorithms, and Signal Processing Applications

The presenters consider a class of nonconvex complex quadratic programming problems, which find a broad spectrum of signal processing applications. By using the polar coordinate representations of the complex variables, they first derive a new enhanced semidefinite relaxation for the problem. Based on the newly derived semidefinite relaxation, we further propose an efficient branch-and-bound algorithm for solving the problem. Key features of our proposed algorithm are: (1) it is guaranteed to find the global solution of the problem (within any given error tolerance); (2) it is computationally efficient because it carefully utilizes the special structure of the problem. They apply the proposed algorithm to solve a series of signal processing problems. Simulation results show that our proposed enhanced semidefinite relaxation is generally much tighter than the conventional semidefinite relaxation, and the proposed global algorithm can efficiently solve these problems.