Consensus-ADMM for General Quadratically Constrained Quadratic Programming

Kejun Huang, Nicholas D. Sidiropoulos

Research output: Contribution to journalArticlepeer-review

67 Scopus citations

Abstract

Nonconvex quadratically constrained quadratic programming (QCQP) problems have numerous applications in signal processing, machine learning, and wireless communications, albeit the general QCQP is NP-hard, and several interesting special cases are NP-hard as well. This paper proposes a new algorithm for general QCQP. The problem is first reformulated in consensus optimization form, to which the alternating direction method of multipliers can be applied. The reformulation is done in such a way that each of the subproblems is a QCQP with only one constraint (QCQP-1), which is efficiently solvable irrespective of (non)convexity. The core components are carefully designed to make the overall algorithm more scalable, including efficient methods for solving QCQP-1, memory efficient implementation, parallel/distributed implementation, and smart initialization. The proposed algorithm is then tested in two applications: multicast beamforming and phase retrieval. The results indicate superior performance over prior state-of-the-art methods.

Original languageEnglish (US)
Article number7517329
Pages (from-to)5297-5310
Number of pages14
JournalIEEE Transactions on Signal Processing
Volume64
Issue number20
DOIs
StatePublished - Oct 15 2016

Bibliographical note

Funding Information:
This work was supported in part by National Science Foundation under Project CIF-1525194.

Keywords

  • Alternating direction method of multipliers (ADMM)
  • feasible point pursuit
  • multicast beamforming
  • non-convex quadratically constrained quadratic programming (QCQP)
  • phase retrieval
  • semi-definite relaxation (SDR)

Fingerprint Dive into the research topics of 'Consensus-ADMM for General Quadratically Constrained Quadratic Programming'. Together they form a unique fingerprint.

Cite this