Fast feasibility pursuit for non-convex QCQPS via first-order methods

Aritra Konar; Nicholas D. Sidiropoulos

ICASSP 2017accepted0 citations

Fast feasibility pursuit for non-convex QCQPS via first-order methods

Abstract

Quadratically Constrained Quadratic Programming (QCQP) is NP-hard in its general non-convex form, but it frequently arises in engineering design and applications ranging from state estimation to beamforming and clustering. Several polynomial-time approximation algorithms exist for non-convex QCQP problems (QCQPs), but their success hinges upon the ability to find at least one feasible point - which is also hard for a general problem instance. In this paper, we present a framework for computing feasible points of general non-convex QCQPs using simple first-order methods. Our approach features low computational and memory requirements, which makes it well-suited for application on large-scale problems. Experiments indicate the empirical effectiveness of our approach, despite currently lacking theoretical guarantees.

BibTeX

@inproceedings{icassp2017_fastfeasibilityp,
  title = {Fast feasibility pursuit for non-convex QCQPS via first-order methods},
  author = {Aritra Konar and Nicholas D. Sidiropoulos},
  booktitle = {ICASSP 2017},
  year = {2017}
}