Polynomial Optimization and Convex Algebraic Geometry

点击翻译按钮获取中文摘要

This study focuses on problems from polynomialoptimization and convex algebraic geometry. The latter is a newresearch area that concerns convex sets and convex hulls of sets thatare 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. Thefirst set of questions studies the general phenomenon of when a givenconvex body is the linear projection of a slice (by an affine plane)of a closed convex cone. This phenomena is central to alllift-and-project methods for discrete and polynomial optimization. This studyprovides a uniform view of all lift-and-projectmethods via new notions of cone factorizations of certain operatorsassociated to the convex body. The investigator and collaborators haverecently constructed a new hierarchy of convex relaxations foralgebraic sets called theta bodies. Various open questions about thesebodies are posed. The methodsfrom polynomial optimization and convex algebraic geometry can be applied to problemsfrom computer vision. Here the application is primarily to object reconstruction fromimages taken by multiple cameras.The work of the PI with her collaborators improvies our understanding of the algebraic and geometricstructures that underlie optimization problems that involvepolynomials. Such problems have a wide array of applications and admitmethods from both the algebraic and analytic sides ofmathematics. 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.