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

在过去的20年里，凸优化已经成为科学和工程中不可或缺的设计和分析工具。尽管如此，许多重要的设计和分析问题都是非凸的和NP难的。其中，非凸二次约束二次规划(QCQP)是当今无线通信、网络和信号处理中经常遇到的问题。例子包括相控阵单播和多播波束形成，以及相位恢复及其在X射线结晶学、光学、衍射成像、天文成像和显微镜中的应用。目前很少有方法能有效地处理非凸的QCQP，而且只在特殊情况下有效。本文研究了几种新的获得和精化一般非凸QCQP可行点的新方法，以及它们在相位恢复、波束形成、雷达和无线组网中的应用。该项目为研究生和本科生参与跨学科研究以及新生和K12外展提供了丰富的机会。在前期工作中，提出了一种可行点追踪-逐次凸逼近(FPP-SCA)方法，初步测试结果令人振奋。推动进一步的研究，包括两个相互交织的主题：一个是关于新的FPP方法和算法的设计和分析；另一个是关于非凸QCQP方法的新的信号处理应用。除了分析和改进原有的FPP-SCA外，正在考虑两种新的方法。一种是使用双线性化，导致交替优化；另一种是使用比例公平性作为最大-最小公平性的替代，使用自适应加权循环投影梯度方法得到低复杂度的FPP。分析了该迭代不动点的最优性差距，对特殊问题实例进行了适当的简化，并进一步探讨了max-min与比例公平性之间的联系。所有这些都着眼于提高我们对非凸QCQP的基本理解。

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.