High Performance Approximation Algorithms for Nonconvex Quadratic Optimization with Applications in Signal Processing and Communication

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

The proposed research deals with polynomial time approximation algorithms for a class of nonconvex quadratic optimization problems which can deliver guaranteed high quality approximate solutions. These approximation algorithms are based on interior point methods for semi-definite programming (SDP) relaxations of the nonconvex problems, followed by some randomized rounding procedure. The investigator of this project proposes to analyze both the worst-case and the average-case performance ratios of the SDP relaxations for nonconvex quadratic optimization problems under some realistic probabilistic models arising from wireless communication. The focus of proposed research is on (i) design and performance analysis of SDP relaxation algorithms for quadratically constrained nonconvex quadratic programs, and (ii) probabilistic analysis of SDP relaxation algorithms for the binary least squares problem. The choice of these topics is strongly motivated by the applications from signal processing and wireless communications. The approach will be to combine the modern interior point optimization methodology with the theory of random matrices to estimate the asymptotic performance of SDP relaxations for large systems. Overall, the proposed research is built on the past successes the investigator has had in developing new and applying the state-of-the-art optimization techniques to solve some fundamental problems in signal processing and digital communication. The latter two areas had been relying mostly on the gradient descent or the least squares methods in the past thirty years. With the recent advance of highly efficient interior point methods in mathematical programming, the opportunity is ripe to use these modern optimization techniques and the related software tools to help advance the field of signal processing and digital communication, both of which are known to have intensive computational requirement.