Semidefinite Programming Relaxation: Approximation Algorithms, Performance Analysis and Applications

半定规划松弛：近似算法、性能分析和应用

• 批准号: 1015346
• 负责人: Zhi-Quan Luo
• 金额: $ 12万
• 依托单位: University of Minnesota-Twin Cities
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-15 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1015346&HistoricalAwards=false
• 关键词: Semidefinite; Programming; Relaxation; Approximation; Algorithms

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.

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