This study focuses on problems from polynomial optimization and convex algebraic geometry. The latter is a new research area that concerns convex sets and convex hulls of sets that are described algebraically and arise in optimization. The key tool is the use of efficient algorithms in semidefinite programming, a branch of convex optimization that is used in polynomial optimization. The first set of questions studies the general phenomenon of when a given convex body is the linear projection of a slice (by an affine plane) of a closed convex cone. This phenomena is central to all lift-and-project methods for discrete and polynomial optimization. This study provides a uniform view of all lift-and-project methods via new notions of cone factorizations of certain operators associated to the convex body. The investigator and collaborators have recently constructed a new hierarchy of convex relaxations for algebraic sets called theta bodies. Various open questions about these bodies are posed. The methods from polynomial optimization and convex algebraic geometry can be applied to problems from computer vision. Here the application is primarily to object reconstruction from images taken by multiple cameras.
The work of the PI with her collaborators improvies our understanding of the algebraic and geometric structures that underlie optimization problems that involve polynomials. Such problems have a wide array of applications and admit methods from both the algebraic and analytic sides of mathematics. This research considers both improvements in our understanding of the theoretical aspects of polynomial optimization, and the application of these methods to problems in computer vision.
This grant supported two research projects in the area of mathematical optimization: The first project concerned the development of the notion of positive semidefinite (psd) rank of a nonnegative matrix which parallels the notion of nonnegative rank of a nonnegative matrix. This invariant was defined earlier by the PI and collaborators in the context of understanding representations of convex sets as projections of slices of psd cones. This is a topic that has been of much interest in engineering and mathematics (real algebraic geometry) since such projection representations allow very complicated convex sets to be expressed as projections of much simpler sets. This translates to efficient algorithms for optimizing linear functions over the original set. A particular case of the main result is that a polytope can be expressed as the projection of a slice of the cone of k x k psd matrices if and only if a certain nonnegative matrix associated to the polytope, known as its "slack matrix", has psd rank at least k. These results have become the cornerstone of an active area of research at the intersection of combinatorial optimization, theoretical computer science and quantum communication. The following new results (each a paper) were found under this grant support: (i) A theory for how an approximate factorization of the slack matrix can yield inner and outer convex approximations of a polytope. The significance of this result is that in practise, we never have an exact factorization, just numerical approximations of it. The approximations we construct have potential in approximation algorithms for combinatorial optimization. This paper is a robust version of previous results on this topic. (ii) A characterization of polytopes with minimum psd rank. This focusses on the merits of psd lifts as opposed to the hardness of the method and understands the polytopes that can most easily be written as the projection of a slice of a psd cone. (iii) A characterization of those nonnegative matrices that are slack matrices of polytopes. (iv) Several new results on worst case behavour of psd rank. (v) The PI and collaborators have also completed a survey on psd rank with the aim of popularizing this invariant in other parts of mathematics and its applications. We feel that psd rank has significant uses outside of the purpose we invented it for and hope that the survey will achieve this goal. The second project involved the use of polynomial optimization in the area of 3D resconstruction in computer vision. Here the goal was to examine the mathematical structures that underlie foundational problems in multi-view geometry with the goal of designing efficient algorithms that exploit structure. In this subject our work resulted in several papers: (i) We successfully applied methods from computational and theoretical algebraic geometry to the triangulation problem (which is concerned with reconstructing 3D scenes from noisy images in known cameras), revealing several algebraic structures that were not known before. (ii) We studied the maximum likelihood optimization problem that arises in triangulation and showed that almost always it can be solved easily using semidefinite programming, a feature that was observable only by paying attention to the geometric and algebraic structure of the problem. (iii) Most recently we have obtained new results in the area of 2-view vision which is a foundational problem in multiview geometry. We give certificates for when two sets of planar point configurations are the images of a collection of 3D points in two cameras. The PI coauthored 10 journal articles during this grant cycle; 6 on psd rank and 4 in computer vision. In addition, along with Greg Blekherman and Pablo Parrilo, she edited a book called "Semidefinite Optimization and Convex Algebraic Geometry" published in the SIAM MOS series in 2012. Two students received their Ph.D. and an additional two students were mentored and supported by this grant. The PI was invited to give several plenary talks at national and international conferences on the work supported by this grant. The highlights were (i) an invited MAA address at the Joint Math Meetings in Boston, 2012, (ii) a semi-plenary talk at the International Symposium of Mathematical Programming in Berlin, 2012 and (iii) a plenary talk at the SIAM Conference on Optimization, San Diego, 2014. The grant also allowed the PI and students to travel to several conferences and workshops. The PI was an instructor at the " 2012 IMA PI Summer Program for Graduate Students, Algebraic Geometry for Applications" at Georgia Tech, and a full-time participant at the the 4-week program "Polynomial Optimisation" at the Isaac Newton Institute in August 2013. She has a recent article in SIAM News based on her talk at the SIAM conference, aimed at a very broad community of pure and applied mathematicians.
