An Enhanced SDR Based Global Algorithm for Nonconvex Complex Quadratic Programs With Signal Processing Applications

IEEE Open Journal of Signal Processing

Jing Zhou¹  Cheng Lu²  Ya-Feng Liu³ 

[1] Department of Applied Mathematics, College of Science, Zhejiang University of Technology, Hangzhou, China;School of Economics and Management, North China Electric Power University, Beijing, China;State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China;

关键词: Branch-and-bound algorithm;    enhanced SDR;    MIMO detection;    nonconvex CQP;    virtual beamforming;   

DOI  :  10.1109/OJSP.2020.3020221

来源: DOAJ

【 摘 要 】

In this paper, we consider a class of nonconvex complex quadratic programming (CQP) problems, which find a broad spectrum of signal processing applications. By using the polar coordinate representations of the complex variables, we first derive a new enhanced semidefinite relaxation (SDR) for problem (CQP). Based on the newly derived SDR, we further propose an efficient branch-and-bound algorithm for solving problem (CQP). 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. We apply our proposed algorithm to solve the multi-input multi-output (MIMO) detection problem, the unimodular radar code design problem, and the virtual beamforming design problem. Simulation results show that our proposed enhanced SDR, when applied to the above problems, is generally much tighter than the conventional SDR, and our proposed global algorithm can efficiently solve these problems. In particular, our proposed algorithm significantly outperforms the state-of-the-art sphere decode algorithm for solving the MIMO detection problem in the hard cases (where the number of inputs and outputs is equal or the signal-to-noise-ratio is low), and a state-of-the-art general-purpose global optimization solver called Baron for solving the virtual beamforming design problem.

【 授权许可】

Unknown