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

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.
However, the existence of an exact algorithm with polynomial complexity for both SDO and PO is still an open problem. The focus of my talk is computational complexity in SDO and PO, through the lens of real algebraic geometry. While SDO can be solved “efficiently” using path-following interior point methods, PO can be approximately solved using a converging hierarchy of SDO relaxations. 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.

Share this Event