Semidefinite Programming Relaxation: Approximation Algorithms, Performance Analysis and Applications

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

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.