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不等式)。我们开发的技术揭示了最优化、复杂性和不变量理论之间的深刻联系。我们已经展示了在其他科学领域的广泛应用，就像上面提到的那些领域。尽管最近取得了进展，但许多问题仍然悬而未决。我们算法和分析的改进可能会在更多领域产生深远影响。代数复杂性的下限技术：代数电路是研究计算多项式的复杂性的主要计算模型。尽管最近在有限类电路的下界方面取得了显著的进展，但我们仍不能改进S在80年代得到的一般代数电路的(弱)下界。我们最近证明了一类非常一般的下界技巧的第一个无条件障碍结果(限制)，这类技巧涵盖了代数环境中大多数已知的下界技巧。我们的目标是将我们的结果推广到更强的下界方法，并改进现有的障碍。我们还致力于开发新的技术来克服这些障碍，并获得更强的代数电路下界。实稳定性、最优化和代数复杂性：半定规划(SDP)和双曲规划(HP)(SDP的推广)问题具有内在的代数结构：它们是由具有特殊正性性质的多项式描述的优化问题。SDP用对称矩阵的行列式来刻画，而HPS用双曲多项式来刻画。与HPS相比，SPS得到了更广泛的应用和更好的理解。然而，后者最近受到了更多的关注，因为它们在统计物理、组合学和近似计数算法等不同领域的问题中自然出现。这一领域的一个根本问题是，医疗保险是否真的比医疗保险更强大、更普遍。这项研究结合了实代数几何、组合学和代数复杂性的最新发展，以弥合两类优化问题之间的结构和计算差距。