Collaborative Research: AF: Medium: Polynomial Optimization: Algorithms, Certificates and Applications

在不同的科学和工程领域中出现的计算问题可以建模为在一组约束条件下优化一个适当的目标函数。当目标函数是一个低次多项式时，一个引起广泛兴趣的例子捕获了一系列令人惊讶的问题。丰富的理论和应用工作使我们对在诸如单位球或高维超立方体等域上优化线性和二次函数的算法和难度有了相当广泛的理解。然而，对于大于2次多项式的情况，我们还没有很好地理解。该项目的目标是在算法估计和证明方面推进优化高次多项式的前沿，以近似地约束其最优解，然后在各种应用中利用这种增强的理解。其动机是多项式优化的内在重要性，以及一些无关的上下文（约束满足、图论、高维几何、证明复杂性和伪随机性，仅举几例），其中多项式/张量优化自然产生，并可能成为进一步发展的关键。一个在现代学习和推理应用中非常重要的例子方向是将矩阵值数据的常用主成分分析推广到高阶张量。这个项目提出了三个精心设计和相互交织的方向，以显着推进对多项式优化的理解。这包括一种寻找新的舍入算法的新方法，这种方法将导致具有最大化三次多项式和高次多项式的改进保证的近似算法，这反过来又有望导致突破长期存在的离散问题的障碍，例如图上的最大切割或小集展开。该项目还涉及近似多项式优化硬度结果的新方法；目前只知道非常弱的边界，已知的算法和硬度结果之间存在巨大差距。第三，由于研究人员最近在反驳约束满足问题上的一些工作提供了动力，该项目将开始通过最优点上的证书来研究多项式优化，扩展到最先进的线性代数和谱证书。这样的证书可能会对伪随机性产生重大影响，产生“经过认证的随机对象”，这些对象在功能上与黄金标准（但通常非常难以捉摸）明确的结构一样好。该项目的研究和推广活动将为代数几何、统计学、运筹学、信号处理和机器学习等相关研究社区搭建桥梁。项目调查人员将培训和指导几名研究生，并为本科生提供引人入胜的研究经验。研究结果将通过统一多项式优化下的几个问题来指导研究生水平的近似优化课程。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Computational problems arising in diverse fields of sciences and engineering can be modeled as optimizing an appropriate objective function subject to a set of constraints. A case of wide interest that captures a surprising array of problems is when the objective function is a polynomial of low-degree. A rich body of theoretical and applied work has led to a fairly extensive understanding of algorithms and hardness for optimizing linear and quadratic functions on domains such as the unit sphere or the hypercube in high dimensions. The situation for polynomials of degree greater than two is, however, not yet well understood. The goal of this project is to advance the frontiers of optimizing higher-degree polynomials in terms of algorithms to estimate and proofs to approximately bound their optima, and then leverage this enhanced understanding in diverse applications. The motivation is both the intrinsic importance of polynomial optimization, as well as several extraneous contexts (constraint satisfaction, graph theory, high-dimensional geometry, proof complexity, and pseudo-randomness, to name a few) where polynomial/tensor optimization arises naturally and could hold the key to further progress. An an example direction, of high importance in modern learning and inference applications, is the generalization of the frequently used principal-component analysis of matrix-valued data to higher-order tensors.This project presents three carefully crafted and intertwined directions to significantly advance the understanding of polynomial optimization. This includes a fresh approach to finding new rounding algorithms that will lead to approximation algorithms with improved guarantees for maximizing cubic and higher-degree polynomials, which in turn is expected to lead to progress beyond longstanding barriers for discrete problems such as Maximum Cut or Small Set Expansion on graphs. The project also involves new approaches towards hardness results for approximate polynomial optimization; currently only very weak bounds are known, and there is a huge gap between the known algorithmic and hardness results. Third, with impetus provided by some recent work by the investigators on refuting constraint-satisfaction problems, the project will embark on a study of polynomial optimization through the lens of certificates on their optima, extending beyond the state of the art linear-algebraic and spectral certificates. Such certificates could have significant ramifications in pseudo-randomness, producing "certified random objects" that are functionally as good as the gold standard (but often highly elusive) explicit constructions. The research and outreach activities of the project will build bridges to allied research communities in algebraic geometry, statistics, operations research, signal processing, and machine learning. The project investigators will train and mentor several graduate students, and also provide engaging research experiences to undergraduates. The research findings will inform graduate level courses on approximate optimization by unifying several problems under the umbrella of polynomial optimization.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.