Feasible Point Pursuit and Successive Approximation of Non-convex QCQPs

Abstract

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 paper, 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.

Submitted to the IEEE Signal Processing Letters

Cited by in corpus (6)

• Optimal Solutions for Joint Beamforming and Antenna Selection: From Branch and Bound to Graph Neural Imitation Learning
• Ultra-Low-Complexity Algorithms with Structurally Optimal Multi-Group Multicast Beamforming in Large-Scale Systems
• Fast First-Order Algorithm for Large-Scale Max-Min Fair Multi-Group Multicast Beamforming
• Multi-Group Multicast Beamforming by Superiorized Projections onto Convex Sets
• Cooperative Beamforming for Wireless Fronthaul and Access Links in Ultra-Dense C-RANs with SWIPT: A First-Order Approach
• Efficient Rotating Synthetic Aperture Radar Imaging via Robust Sparse Array Synthesis