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

Aritra Konar; Nicholas D. Sidiropoulos

doi:10.1109/ICASSP.2017.7952920

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

Aritra Konar, Nicholas D. Sidiropoulos

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

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.

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.
Pages	4064-4068
Number of pages	5
ISBN (Electronic)	9781509041176
DOIs	https://doi.org/10.1109/ICASSP.2017.7952920
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

Publication series

Name	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)	1520-6149

Other

Other	2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017
Country/Territory	United States
City	New Orleans
Period	3/5/17 → 3/9/17

Bibliographical note

Funding Information:
Supported in part by NSF CIF-1525194, and the Univ. of Minnesota through a Doctoral Dissertation Fellowship.

Publisher Copyright:
© 2017 IEEE.

Publisher link

10.1109/ICASSP.2017.7952920

Find It

Find It at U of M Libraries

Cite this

Konar, A., & Sidiropoulos, N. D. (2017). Fast feasibility pursuit for non-convex QCQPS via first-order methods. In 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings (pp. 4064-4068). Article 7952920 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2017.7952920

Fast feasibility pursuit for non-convex QCQPS via first-order methods. / Konar, Aritra; Sidiropoulos, Nicholas D.
2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. p. 4064-4068 7952920 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Konar, A & Sidiropoulos, ND 2017, Fast feasibility pursuit for non-convex QCQPS via first-order methods. in 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings., 7952920, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 4064-4068, 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017, New Orleans, United States, 3/5/17. https://doi.org/10.1109/ICASSP.2017.7952920

Konar A, Sidiropoulos ND. Fast feasibility pursuit for non-convex QCQPS via first-order methods. In 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2017. p. 4064-4068. 7952920. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2017.7952920

Konar, Aritra ; Sidiropoulos, Nicholas D. / Fast feasibility pursuit for non-convex QCQPS via first-order methods. 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 4064-4068 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{e3a1cf6f6f144f95beff7e1f6e97a72d,

title = "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.",

author = "Aritra Konar and Sidiropoulos, {Nicholas D.}",

note = "Funding Information: Supported in part by NSF CIF-1525194, and the Univ. of Minnesota through a Doctoral Dissertation Fellowship. Publisher Copyright: {\textcopyright} 2017 IEEE.; 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 ; Conference date: 05-03-2017 Through 09-03-2017",

year = "2017",

month = jun,

day = "16",

doi = "10.1109/ICASSP.2017.7952920",

language = "English (US)",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "4064--4068",

booktitle = "2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings",

}

TY - GEN

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

AU - Konar, Aritra

AU - Sidiropoulos, Nicholas D.

PY - 2017/6/16

Y1 - 2017/6/16

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

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

UR - http://www.scopus.com/inward/record.url?scp=85023777024&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85023777024&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2017.7952920

DO - 10.1109/ICASSP.2017.7952920

M3 - Conference contribution

AN - SCOPUS:85023777024

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 4064

EP - 4068

BT - 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017

Y2 - 5 March 2017 through 9 March 2017

ER -

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

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this