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.