Accurately and Efficiently Solving Structured Nonconvex Optimization Problems

Alex Wang, Carnegie Mellon University
DOE supercomputer

Description: Convex optimization has found numerous applications in a variety of domains due to the existence of accurate and highly efficient algorithms for broad classes of convex problems. Unfortunately, a growing number of problems encountered in practice and by the scientific community at large are by nature highly nonconvex. In this talk, we will discuss recent progress towards understanding the ability of convex optimization to solve structured nonconvex problems both accurately and efficiently. To this end, we will focus on the rich class of nonconvex quadratically constrained quadratic programs (QCQPs) and their convex semidefinite program (SDP) relaxations. In the first part of the talk, we will examine general conditions under which the SDP relaxation of a nonconvex QCQP is exact. This will allow us to identify structural properties of QCQPs that admit equivalent tractable SDP reformulations. In the second part of this talk, we will review algorithmic developments for solving certain classes of nonconvex QCQPs and their SDP relaxations efficiently. Specifically, we will see accelerated first-order methods and linear convergence rates among certain classes of nonconvex QCQPs.