Title: On the Computational Complexity of Semidefinite and Polynomial Optimization: A real Algebraic Geometry Approach

Speaker: Ali Mohammad Nezhad (Carnegie Mellon University)

Abstract: Semidefinite and polynomial optimization (SDO and PO) are topics of great theoretical and practical interest, with numerous applications in theoretical computer science, control theory, and statistics. Due to advances in efficient interior point methods, there has been lots of interest in SDO, as an emerging computational tool, in PO and quantum information sciences. 

In theory, on one hand, the existence of an exact algorithm with polynomial complexity for both SDO and PO is still an open problem. Nevertheless, thanks to the tools in real algebra and path-following interior point methods, PO can be approximately solved using a converging hierarchy of SDO relaxations, and SDO can be solved “efficiently” using path-following interior point methods. In practice, on the other hand, SDO itself may be intractable, even approximately. 

The focus of my talk is computational complexity in SDO and PO, through the lens of real algebraic geometry.I show how recent developments in theoretical and algorithmic real algebraic geometry can be utilized to quantify complexity of the central path and improve error bounds that are significant in proving convergence rate of numerical optimization schemes for PO. I end this talk by illuminating promising interactions between continuous optimization, real algebraic geometry, and data science, which form the backbone of my research program.