Optimization, Complexity, Algebra and Invariant Theory

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

• 批准号: RGPIN-2020-04599
• 负责人: MendesdeOliveira, Rafael
• 金额: $ 2.91万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=717230
• 关键词: 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 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 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的特征在于双曲多项式。与HP相比，SDP得到了更广泛的使用，也得到了更好的理解。然而，后者最近受到了更大的关注，由于其自然外观的问题，从不同的领域，从统计物理，组合数学和近似计数算法。这一领域的一个基本问题是，卫生政策是否确实比卫生政策更有力和更普遍。本研究结合了真实的代数几何，组合学和代数复杂性的最新发展，以弥合两类优化问题之间的结构和计算差距。