NSF AWARD:Polynomial Optimization and Convex Algebraic Geometry

Recently, NSF funded a project lead by Rekha R. Thomas on polynomial optimization and convex algebraic geometry.

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 improves 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.