Collaborative Research: AF: Small: On the Complexity of Semidefinite and Polynomial Optimization through the Lens of Real Algebraic Geometry

点击翻译按钮获取中文摘要

Semidefinite and polynomial optimization (SDO and PO) are topics of great theoretical andpractical interest, with numerous applications in theoretical computer science, control theory,quantum information sciences, and statistics. The steady advances in efficient interior-pointmethods (IPMs) lends credence to the impactful role of SDO, as an emerging computationaltool, in PO and quantum computing. The complexity of SDO and PO is well-known in thebit model of computation: there is no polynomial-time algorithm yet to find an exact optimalsolution of these classes of optimization problems. However, even for an approximate solution,there are pathological instances that IPMs or relaxation hierarchies for PO fail to solve.In view of this challenge, the need to investigate the complexity through a broader spectrumof complexity measures is obvious. Such a novel approach allows for a finer classification ofinstances with high complexity. This project pursues the above goal by addressing severalkey questions on the complexity of SDO and PO, through the lens of real algebraic geometry.The results of this project will enhance understanding of the complexity in SDO and POand have the potential to impact other disciplines, including quantum information sciences,where the emerging area of quantum IPMs with their unique advantages offer unprecedentedintellectual challenges. Due to the multidisciplinary nature of this project, the investigators willtrain graduate students and organize meetings by inviting experts as well as young researchersfor fruitful interaction amongst the optimization and real algebraic geometry communities.The first part of the project focuses on quantitative and algorithmic questions about the complexityof SDO from the perspective of the central path. Since IPMs operate in a neighborhoodof the central path, their efficiency is influenced by the analytic and algebro-geometric propertiesof the central path. The investigators explore several complexity measures based on thedegree, worst-case convergence rate, and geometric curvature of the central path for regularand near to ill-posed instances. By means of these complexity measures, in particular, onecan quantitatively justify the complexity of IPMs on instances whose special structures exhibitfailure of the strict complementarity condition. The second part of the project investigates thecomplexity of PO through error bounds and the topology of the feasible set. Unlike IPMs, themoment/sum of squares approach only deals with a sequence of objective values (rather thansolutions), which may not adequately reflect the progress toward the optimal set. As a result,the current complexity bounds from the moment/sum of squares approach are purely algebraicwith no reliance on the topology/geometry of the feasible set. The investigators will exploretopology based complexity measures which allow for the inclusion of the Betti numbers of thefeasible set and thus enhance PO solvers with more precise complexity estimates. That willrigorously explain why iterative algorithms are more likely to stop at a local optima of a POproblem, as the number of connected components or the holes in the feasible set increases.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.