High Performance Approximation Algorithms for Nonconvex Quadratic Optimization with Applications in Signal Processing and Communication

针对一类非凸二次优化问题，提出了一种多项式时间近似算法，该算法能够保证得到高质量的近似解。这些近似算法是基于半定规划（SDP）松弛的非凸问题的内点方法，其次是一些随机舍入过程。本计画的研究者提出在无线通讯的实际机率模型下，分析非凸二次最佳化问题的SDP松弛的最坏情形与平均情形的效能比。建议的研究重点是（i）二次约束非凸二次规划的SDP松弛算法的设计和性能分析，以及（ii）二进制最小二乘问题的SDP松弛算法的概率分析。这些主题的选择是强烈的动机从信号处理和无线通信的应用。该方法将联合收割机现代内点优化方法与随机矩阵理论相结合，以估计大系统的SDP松弛的渐近性能。 总的来说，拟议的研究是建立在过去的成功，研究人员已经在开发新的和应用国家的最先进的优化技术，以解决信号处理和数字通信中的一些基本问题。后两个领域在过去的三十年里主要依赖于梯度下降法或最小二乘法。随着数学规划中高效内点方法的最新进展，使用这些现代优化技术和相关软件工具来帮助推进信号处理和数字通信领域的机会已经成熟，这两个领域都具有密集的计算需求。

The proposed research deals with polynomial time approximation algorithms for a class of nonconvex quadratic optimization problems which can deliver guaranteed high quality approximate solutions. These approximation algorithms are based on interior point methods for semi-definite programming (SDP) relaxations of the nonconvex problems, followed by some randomized rounding procedure. The investigator of this project proposes to analyze both the worst-case and the average-case performance ratios of the SDP relaxations for nonconvex quadratic optimization problems under some realistic probabilistic models arising from wireless communication. The focus of proposed research is on (i) design and performance analysis of SDP relaxation algorithms for quadratically constrained nonconvex quadratic programs, and (ii) probabilistic analysis of SDP relaxation algorithms for the binary least squares problem. The choice of these topics is strongly motivated by the applications from signal processing and wireless communications. The approach will be to combine the modern interior point optimization methodology with the theory of random matrices to estimate the asymptotic performance of SDP relaxations for large systems. Overall, the proposed research is built on the past successes the investigator has had in developing new and applying the state-of-the-art optimization techniques to solve some fundamental problems in signal processing and digital communication. The latter two areas had been relying mostly on the gradient descent or the least squares methods in the past thirty years. With the recent advance of highly efficient interior point methods in mathematical programming, the opportunity is ripe to use these modern optimization techniques and the related software tools to help advance the field of signal processing and digital communication, both of which are known to have intensive computational requirement.