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.
|Original language||English (US)|
|Title of host publication||2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||5|
|State||Published - Jun 16 2017|
|Event||2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - New Orleans, United States|
Duration: Mar 5 2017 → Mar 9 2017
|Name||ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings|
|Other||2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017|
|Period||3/5/17 → 3/9/17|
Bibliographical noteFunding Information:
Supported in part by NSF CIF-1525194, and the Univ. of Minnesota through a Doctoral Dissertation Fellowship.
© 2017 IEEE.