Feasible point pursuit and successive approximation of non-convex QCQPs

Omar Mehanna, Kejun Huang, Balasubramanian Gopalakrishnan, Aritra Konar, Nicholas D. Sidiropoulos

Research output: Contribution to journalArticlepeer-review

125 Scopus citations

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

Original languageEnglish (US)
Article number6954488
Pages (from-to)804-808
Number of pages5
JournalIEEE Signal Processing Letters
Volume22
Issue number7
DOIs
StatePublished - Jul 1 2015

Bibliographical note

Publisher Copyright:
© 1994-2012 IEEE.

Keywords

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

Fingerprint

Dive into the research topics of 'Feasible point pursuit and successive approximation of non-convex QCQPs'. Together they form a unique fingerprint.

Cite this