CIF: Small: Feasible Point Pursuit for Non-convex QCQPs: Algorithms and Signal Processing Applications

Over the last 20 years, convex optimization has become an indispensable design and analysis tool in science and engineering. Still, many important design and analysis problems are non-convex and NP-hard. Among them, non-convex quadratically constrained quadratic programs (QCQPs) are nowadays often encountered in wireless communications, networking, and signal processing. Examples include phased-array unicast and multicast beamforming, and phase retrieval and its applications in X-ray crystallography, optics, diffraction imaging, astronomical imaging, and microscopy. Few methods are currently effective for non-convex QCQPs, and only in special cases. This research investigates several promising new approaches to obtaining and refining feasible points for general non-convex QCQPs, and their applications in phase retrieval, beamforming, radar, and wireless networking. The project offers rich opportunities for graduate and undergraduate student engagement in cross-disciplinary research, as well as freshman and K12 outreach.

In preliminary work, a Feasible Point Pursuit - Successive Convex Approximation (FPP-SCA) method was proposed, and initial tests revealed exciting results ? motivating further research that comprises two intertwined thrusts: one on design and analysis of new FPP methods and algorithms; and another on new signal processing applications of non-convex QCQP methods. In addition to analyzing and improving the original FPP-SCA, two new approaches are being considered. One is derived using bilinearization, leading to alternating optimization; the other using proportional fairness as a surrogate for max-min fairness, leading to low-complexity FPP using an adaptively weighted cyclically projected gradient approach. The optimality gap for fixed points of this iteration is analyzed, pertinent simplifications are pursued for special problem instances, and the link between max-min and proportional fairness is further explored ? all with an eye towards improving our fundamental understanding of non-convex QCQPs.