Sums of Squares Polynomials in Optimization, Combinatorics, and Computer Vision

科学和工程中的许多问题都可以建模为多项式优化问题，其目标是在给定一组对模型参数的实际约束的情况下找到一个最优解。在过去的二十年里，这个领域经历了一场革命，融合了源自数学和计算机科学的几个领域的新想法。这些进展使多项式优化在许多应用中成为一种可行的工具。一个重要的例子是计算机视觉，它的一个关键目标是在给定一组二维图像的情况下估计和描述场景中的三维形状。这项研究项目结合了最优化、计算机视觉和组合学的技术，解决了这些挑战。特别强调设计有效和实用的计算算法。研究生将参与这个跨学科的研究项目，为学生提供广泛的数学培训，使理论和计算相互交织。本研究调查了多项式优化领域的三个主题。第一个项目扩展了先前关于多面体的半正定表示的工作，以创建多面体实现空间的规范模型。这项研究有可能通过多面体的松弛理想开创一种新的代数观点，简化几何结果，并解决诸如理解射影唯一性等长期存在的问题。第二个项目的重点是代数视觉，其目的是将代数几何和多项式优化的技术应用于计算机视觉中的问题，具有潜在的重要实际应用。同时，对应用公式的研究有可能启发新的数学理论。代数视觉的研究继续与计算机视觉社区建立牢固的联系，并将有助于在数学和视觉之间进行智力交流，使这两个领域都受益，并为有志于在工业领域就业的数学学生提供一个刺激的培训环境。最后一个项目的长期目标是在对称情况下发展多项式优化的计算方面。应用程序中的许多问题都伴随着对称性，而利用这一特性的能力通常决定了问题能否得到解决。

Many questions in science and engineering can be modeled as questions in polynomial optimization, in which the goal is to find an optimal solution given a set of practical constraints on the model parameters. This field has undergone a revolution in the last two decades by incorporating novel ideas originating from several fields of mathematics and computer science. These advances have made polynomial optimization a viable tool in many applications. An important example is computer vision, for which a key goal is to estimate and characterize the three-dimensional shapes within a scene, given a set of two-dimensional images. This research project tackles such challenges by combining techniques from optimization, computer vision, and combinatorics. Special emphasis is placed on designing efficient and practical computational algorithms. Graduate students will be involved in this cross-disciplinary research project, providing the students with broad training in mathematics that intertwines theory and computation.This research investigates three topics in the field of polynomial optimization. The first project extends prior work on positive semi-definite representations of polytopes for the creation of a canonical model of realization spaces of polytopes. This research has the potential to initiate a new algebraic viewpoint of polytopes via their slack ideals, simplifying geometric results and settling longstanding questions such as understanding projective uniqueness. For the second project the focus is on algebraic vision, for which the aim is to apply techniques from algebraic geometry and polynomial optimization to questions in computer vision, with potentially important practical application. Concurrently, the study of applied formulations has the potential to inspire new mathematical theories. Research in algebraic vision continues to create strong ties to the computer vision community and will help create an intellectual exchange between mathematics and vision, benefiting both fields and providing a stimulating training environment for mathematics students looking toward careers in industry. The long-term aim of the last project is to develop the computational aspects of polynomial optimization in the presence of symmetry. Numerous problems in applications come with symmetries, and the ability to exploit this feature often determines whether or not the problem can be solved.