Polynomial Optimization and Convex Algebraic Geometry

多项式优化和凸代数几何

• 批准号: 1115293
• 负责人: Rekha Thomas
• 金额: $ 34.28万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2014-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115293&HistoricalAwards=false
• 关键词: Polynomial; Optimization; 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.

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