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.
Results on intellectual merit: The PI developed effective semidefinite programming (SDP) relaxation techniques for some mixed binary quadratically constrained quadratic programs (MBQCQP) and analyzed their approximation performance Xu et al. (2013). This relaxation technique extends the SDP approach to nonconvex optimization problems with integer variables, and has been successfully applied to the joint admission control and beamforming problem in wireless networks. In addition, the PI and his students have analyzed the convergence of block successive upper bound minimization (BSUM) algorithm Razaviyayn et al. (2012) and established the convergence of multiblock alternating direction method of multipliers Hong and Luo (2013). These algorithms are well suited for large optimization problems involving big data. Results on broader impact: 1. Two Masters’ students have been trained and are continuing as Ph.D students in the PI’s research group. One female graduate student is being trained. 2. The PI has worked closely with industry partners (Huawei Technologies Canada and Starkey Labs) on the use of optimization techniques for advanced signal processing applications. Evidence of research products: The PI published a SIAM J. Optimization paper Razaviyayn et al. (2012), and two papers are under second round review by Mathematical Programming Hong and Luo (2013) and SIAM J. Optimization Xu et al. (2013).
