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

合作研究：AF：小：通过实代数几何的视角探讨半定和多项式优化的复杂性

• 批准号: 2128702
• 负责人: Saugata Basu
• 金额: $ 24.76万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2128702&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; Complexity

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.

半定和多项式优化（SDO 和 PO）是具有重大理论和实践意义的主题，在理论计算机科学、控制理论、量子信息科学和统计学中有大量应用。高效内点方法 (IPM) 的稳步进步证明了 SDO 作为新兴计算工具在 PO 和量子计算中的重要作用。 SDO 和 PO 的复杂性在计算的位模型中是众所周知的：还没有多项式时间算法来找到此类优化问题的精确最优解。然而，即使对于近似解决方案，也存在 IPM 或 PO 松弛层次结构无法解决的病态实例。鉴于这一挑战，显然需要通过更广泛的复杂性度量来研究复杂性。这种新颖的方法可以对高复杂性的实例进行更精细的分类。该项目通过实代数几何的视角解决有关 SDO 和 PO 复杂性的几个关键问题来实现上述目标。该项目的结果将增强对 SDO 和 PO 复杂性的理解，并有可能影响其他学科，包括量子信息科学中，量子IPM的新兴领域以其独特的优势提出了前所未有的智力挑战。由于该项目的多学科性质，研究人员将通过邀请专家和年轻研究人员来培训研究生并组织会议，以便在优化和真实代数几何界之间进行富有成效的互动。该项目的第一部分重点关注有关优化和真实代数几何社区之间的定量和算法问题。从中心路径的角度来看SDO的复杂性。由于 IPM 在中心路径的邻域中运行，因此它们的效率受到中心路径的解析和代数几何特性的影响。研究人员根据规则实例和近不适定实例的中心路径的度、最坏情况收敛率和几何曲率探索了几种复杂性度量。特别是，通过这些复杂性度量，我们可以在其特殊结构表现出严格互补条件失败的情况下定量地证明 IPM 的复杂性。该项目的第二部分通过误差界限和可行集的拓扑研究 PO 的复杂性。与 IPM 不同，矩/平方和方法仅处理一系列目标值（而不是解），这可能无法充分反映朝向最优集的进展。因此，矩/平方和方法的当前复杂度界限是纯代数的，不依赖于可行集的拓扑/几何。研究人员将探索基于拓扑的复杂性度量，这些度量允许包含可行集的 Betti 数，从而通过更精确的复杂性估计来增强 PO 求解器。这将严格解释为什么迭代算法更有可能停止在 PO 问题的局部最优处，因为连接组件的数量或可行集中的漏洞数量增加。该奖项反映了 NSF 的法定使命，并通过使用以下方法进行评估被认为值得支持：基金会的智力价值和更广泛的影响审查标准。

项目成果

On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate

半定优化的中心路径：度和最坏情况收敛率

• DOI: 10.1137/21m1419933
• 发表时间: 2022-07
• 期刊: SIAM journal on applied algebra and geometry
• 作者: Basu, Saugata;Mohammad
• 通讯作者: Mohammad

Efficient simplicial replacement of semialgebraic sets

半代数集的高效单纯替换

• DOI: 10.1017/fms.2023.36
• 发表时间: 2023-01
• 期刊: Sigma
• 作者: Basu, Saugata;Karisani, Negin
• 通讯作者: Karisani, Negin

Persistent Homology of Semialgebraic Sets

半代数集的持久同调

• DOI: 10.1137/22m1494415
• 发表时间: 2023-09
• 期刊: SIAM Journal on Applied Algebra and Geometry
• 影响因子: 1.2
• 作者: Basu, Saugata;Karisani, Negin
• 通讯作者: Karisani, Negin

Topology of real multi-affine hypersurfaces and a homological stability property

真实多重仿射超曲面的拓扑及其同调稳定性

• DOI: 10.1016/j.aim.2023.108982
• 发表时间: 2023-05
• 期刊: Advances in Mathematics
• 影响因子: 1.7
• 作者: Basu, Saugata;Perrucci, Daniel
• 通讯作者: Perrucci, Daniel