Feasible Point Pursuit and Successive Approximation of Non-Convex QCQPs

作者：Mehanna Omar^*; Huang Kejun; Gopalakrishnan Balasubramanian; Konar Aritra; Sidiropoulos Nicholas D

来源：IEEE Signal Processing Letters, 2015, 22(7): 804-808.

DOI：10.1109/LSP.2014.2370033

• Feasible point pursuit
• linearization
• multicast beamforming
• non-convex QCQP
• semi-definite relaxation
• successive convex approximation

Quadratically constrained quadratic programs QCQPs) have a wide range of applications in signal processing and wireless communications. Non-convex QCQPs are NP-hard in general. Existing approaches relax the non-convexity using semi-definite relaxation SDR) or linearize the non-convex part and solve the resulting convex problem. However, these techniques are seldom successful in even obtaining a feasible solution when the QCQP matrices are indefinite. In this letter, a new feasible point pursuit successive convex approximation FPP-SCA) algorithm is proposed for non-convex QCQPs. FPP-SCA linearizes the non-convex parts of the problem as conventional SCA does, but adds slack variables to sustain feasibility, and a penalty to ensure slacks are sparingly used. When FPP-SCA is successful in identifying a feasible point of the non-convex QCQP, convergence to a Karush-Kuhn-Tucker KKT) point is thereafter ensured. Simulations show the effectiveness of our proposed algorithm in obtaining feasible and near-optimal solutions, significantly outperforming existing approaches.

• 出版日期2015-7