Fast Approximation Algorithms for a Class of Non-convex QCQP Problems Using First-Order Methods

Aritra Konar, Nicholas D. Sidiropoulos

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

A number of important problems in engineering can be formulated as non-convex quadratically constrained quadratic programming (QCQP). The general QCQP problem is NP-Hard. In this paper, we consider a class of non-convex QCQP problems that are expressible as the maximization of the point-wise minimum of homogeneous convex quadratics over a 'simple' convex set. Existing approximation strategies for such problems are generally incapable of achieving favorable performance-complexity tradeoffs. They are either characterized by good performance but high complexity and lack of scalability, or low complexity but relatively inferior performance. This paper focuses on bridging this gap by developing high performance, low complexity successive non-smooth convex approximation algorithms for problems in this class. Exploiting the structure inherent in each subproblem, specialized first-order methods are used to efficiently compute solutions. Multicast beamforming is considered as an application example to showcase the effectiveness of the proposed algorithms, which achieve a very favorable performance-complexity tradeoff relative to the existing state of the art.

Original languageEnglish (US)
Article number7891594
Pages (from-to)3494-3509
Number of pages16
JournalIEEE Transactions on Signal Processing
Volume65
Issue number13
DOIs
StatePublished - Jul 1 2017

Keywords

  • convergence
  • first-order methods
  • massive multiple-input multiple-output (MIMO) communications
  • multicasting
  • Nemirovski saddle point reformulation
  • Nesterov smoothing
  • Non-convex optimization
  • non-smooth optimization
  • per-antenna power constraints
  • quadratically constrained quadratic programming (QCQP)

Fingerprint Dive into the research topics of 'Fast Approximation Algorithms for a Class of Non-convex QCQP Problems Using First-Order Methods'. Together they form a unique fingerprint.

  • Cite this