Polynomial Optimization and Convex Algebraic Geometry

本研究的重点是从多项式优化和凸代数几何的问题。后者是一个新的研究领域，涉及凸集和凸包的代数描述和优化中出现的集合。 关键的工具是在半定规划中使用有效的算法，半定规划是凸优化的一个分支，用于多项式优化。第一组问题研究的一般现象时，一个给定的凸体是线性投影的切片（仿射平面）的一个封闭的凸锥。这种现象是离散和多项式优化的所有提升和投影方法的核心。本文通过对凸体上某些算子的锥分解的新概念，给出了所有提升投影方法的统一观点。研究者和合作者最近构建了一个新的层次的凸松弛代数集称为theta机构。关于这些机构提出了各种开放的问题。多项式优化和凸代数几何的方法可以应用于计算机视觉问题。这里的应用主要是从多个摄像机拍摄的图像中重建物体。PI与她的合作者的工作提高了我们对涉及多项式的优化问题的代数和几何结构的理解。这类问题有着广泛的应用，并从数学的代数和分析两个方面接纳了各种方法。这项研究既考虑了我们对多项式优化理论方面的理解，又考虑了这些方法在计算机视觉问题中的应用。

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.