Max-min feasible point pursuit for non-convex QCQP

Charilaos I. Kanatsoulis, Nicholas D. Sidiropoulos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Quadratically constrained quadratic programming (QCQP) has a variety of applications in signal processing, communications, and networking - but in many cases the associated QCQP is non-convex and NP-hard. In such cases, semidefinite relaxation (SDR) followed by randomization, or successive convex approximation (SCA) are typically used for approximation. SDR and SCA work with one-sided non-convex constraints, but typically fail to produce a feasible point when there are two-sided or more generally indefinite constraints. A feasible point pursuit (FPP-SCA) algorithm that combines SCA with judicious use of slack variables and a penalty term was recently proposed to obtain feasible and near-optimal solutions with high probability in these difficult cases. In this contribution, we revisit FPP- SCA from a different point of view and recast the feasibility problem in a simpler, more compact way. Simulations show that the new approach outperforms the original FPP-SCA under certain conditions, thus providing a useful addition to our non-convex QCQP toolbox.

Original languageEnglish (US)
Title of host publicationConference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Number of pages5
ISBN (Electronic)9781467385763
StatePublished - Feb 26 2016
Event49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 - Pacific Grove, United States
Duration: Nov 8 2015Nov 11 2015

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393


Other49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
Country/TerritoryUnited States
CityPacific Grove

Bibliographical note

Publisher Copyright:
© 2015 IEEE.


Dive into the research topics of 'Max-min feasible point pursuit for non-convex QCQP'. Together they form a unique fingerprint.

Cite this