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.