Optimization, Complexity, Algebra and Invariant Theory

最优化、复杂性、代数和不变理论

• 批准号: RGPIN-2020-04599
• 负责人: MendesdeOliveira, Rafael
• 金额: $ 2.91万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750218
• 关键词: Optimization; Complexity; Algebra; Invariant; Theory

The research we propose is based on the long-term paradigm: How can we use the inherent algebraic structure of a computational problem to design better algorithms for it? And how can we use the inherent algebraic structure of a lower bound technique to understand its limitations and design better lower bound techniques? Optimization, Algebraic Complexity & Invariant Theory: We aim to develop new algorithmic techniques to solve certain classes of non-convex optimization problems and exponentially large linear programs (moment polytopes). These problems are described by algebraic groups acting linearly on vector spaces. Such non-convex optimization problems arise naturally in diverse areas, such as machine learning (optimal transport distances), quantum information theory (quantum marginal problem), invariant theory (null cone) and functional analysis (Brascamp-Lieb inequalities). The techniques we developed bring out deep connections between optimization, complexity and invariant theory. We have shown vast applications in other areas of science, as the ones mentioned above. Despite the recent developments, many questions remain open. Improvements to our algorithms and analyses could have profound impact in many more areas. Lower bound techniques in algebraic complexity: Algebraic circuits are the main computational model to study the complexity of computing polynomials. Despite remarkable recent progress on lower bounds for restricted classes of circuits, we haven't been able to improve on the (weak) lower bounds obtained in the 80's for general algebraic circuits. We recently proved the first unconditional barrier result (limitations) for a very general class of lower bound techniques which encompass most of the known lower bound techniques in the algebraic setting. We aim to generalize our results to stronger lower bound methods and improve the current barriers. We also aim to develop new techniques to overcome such barriers and obtain stronger algebraic circuit lower bounds. Real Stability, Optimization & Algebraic Complexity: Semidefinite programming (SDP) and hyperbolic programming (HP) (a generalization of SDP) problems have an inherent algebraic structure: they are optimization problems described by polynomials possessing special positivity properties. SDPs are characterized by determinants of symmetric matrices whereas HPs are characterized by hyperbolic polynomials. SDPs have been more widely used and are better understood than HPs. However, the latter has recently received greater attention due to their natural appearance in problems from diverse areas, ranging from statistical physics, combinatorics and approximate counting algorithms. A fundamental question in the area is whether HPs are indeed more powerful and general than SDPs. This research combines recent developments from real algebraic geometry, combinatorics and in algebraic complexity to bridge structural and computational gaps between two classes of optimization problems.

我们提出的研究基于长期范式：我们如何利用计算问题固有的代数结构来为其设计更好的算法？我们如何利用下界技术固有的代数结构来理解其局限性并设计更好的下界技术？优化、代数复杂性和不变理论：我们的目标是开发新的算法技术来解决某些类别的非凸优化问题和指数级大型线性程序（矩多胞形）。这些问题由线性作用于向量空间的代数群来描述。这种非凸优化问题自然出现在不同的领域，例如机器学习（最佳传输距离）、量子信息理论（量子边际问题）、不变理论（空锥）和泛函分析（Brascamp-Lieb 不等式）。我们开发的技术揭示了优化、复杂性和不变理论之间的深刻联系。正如上面提到的，我们已经在其他科学领域展示了广泛的应用。尽管最近取得了进展，但许多问题仍然悬而未决。我们的算法和分析的改进可能会对更多领域产生深远的影响。代数复杂性的下界技术：代数电路是研究计算多项式复杂性的主要计算模型。尽管最近在限制类电路的下界方面取得了显着的进展，但我们还无法改进 80 年代为一般代数电路获得的（弱）下界。我们最近证明了非常通用的一类下界技术的第一个无条件障碍结果（限制），该技术涵盖了代数环境中大多数已知的下界技术。我们的目标是将我们的结果推广到更强大的下界方法并改善当前的障碍。我们还致力于开发新技术来克服这些障碍并获得更强的代数电路下界。实稳定性、优化和代数复杂性：半定规划 (SDP) 和双曲规划 (HP)（SDP 的推广）问题具有固有的代数结构：它们是由具有特殊正性质的多项式描述的优化问题。 SDP 的特征在于对称矩阵的行列式，而 HP 的特征在于双曲多项式。 SDP 比 HP 得到更广泛的使用和更好的理解。然而，后者最近由于其自然出现在统计物理、组合学和近似计数算法等不同领域的问题中而受到了更多关注。该领域的一个基本问题是 HP 是否确实比 SDP 更强大、更通用。这项研究结合了实代数几何、组合数学和代数复杂性的最新进展，以弥合两类优化问题之间的结构和计算差距。