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.