Semidefinite Programming Relaxation: Approximation Algorithms, Performance Analysis and Applications

PI将通过该奖项进行的研究包括对对称矩阵提升技术的系统研究，以解决非凸多项式优化问题。这包括一个完整的复杂性理论分析以及多项式时间近似算法的设计。本研究的核心是确定哪类多项式优化问题在计算上是难以处理的，以及它们在多大程度上可以用多项式大小和解精度的复杂性来近似解决。在每种情况下，研究重点将放在深入理解所研究问题的基础理论的发展，以及解决这些问题的稳健和有效的数值方法的设计，实施和分析上。本研究旨在发展多项式时间近似算法，为某些多项式优化问题提供有保证的高质量近似解。这些逼近算法基于对称矩阵提升技术和半定规划松弛，然后通过特殊的程序得到可证明的高质量可行解。该方法得到的非线性半定规划的大小明显小于平方和松弛法得到的规划，因此有望在计算上更有效。将进行计算测试以验证所提出的近似方法的效率和准确性。该奖项将由PI进行的研究受到多项式优化在无线通信和自组织无线传感器网络中的应用的强烈推动。他的研究不仅有望推动非凸多项式优化领域的发展，而且对多用户通信、压缩感知和稀疏主成分分析中干扰管理的计算方法设计具有重要影响。

The PI's research to be carried out through this award consists of a systematic study of a symmetric matrix lifting technique to solve nonconvex polynomial optimization problems. This includes a complete complexity-theoretic analysis as well as the design of polynomial time approximation algorithms. Central to this study is to identify what classes of polynomial optimization problems are computationally intractable, and how well they can be approximately solved with a complexity that is polynomial in size and solution accuracy. In each case, the research focus will be on the development of a fundamental theory for an in-depth understanding of the problems under study, and the design, implementation, and analysis of robust and efficient numerical methods for solving these problems. The proposed research aims to develop polynomial time approximation algorithms which can deliver guaranteed high quality approximate solutions for some classes of polynomial optimization problems. These approximation algorithms are based on a symmetric matrix lifting technique and semidefinite programming relaxation, followed by special procedure to obtain a provably high quality feasible solution. The proposed approach leads to nonlinear semidefinite programs whose size is significantly smaller than those obtained from the Sum of Squares relaxation approach, and is therefore expected to be much more efficient computationally. Computational testing will be conducted to verify the efficiency and accuracy of the proposed approximation approach. The research to be performed by the PI for this award is strongly motivated by applications of polynomial optimization in wireless communication and ad hoc wireless sensor networks. His research is expected to not only advance the field of nonconvex polynomial optimization, but also significantly impact design of computational methods for interference management in multi-user communication, compressive sensing and sparse principal component analysis.