Algebraic and Geometric aspects of Optimization

优化的代数和几何方面

• 批准号: 0712809
• 负责人: Leonid Faybusovich
• 金额: $ 13.97万
• 依托单位: University of Notre Dame
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0712809&HistoricalAwards=false
• 关键词: Algebraic; Geometric; aspects; Optimization

The following three topics are discussed in the project: computable self-concordant barrier functions, Jordan-algebraic aspects of optimization, and multi-dimensional trigonometric programming. The overall goal of the project is to develop new computational and theoretical tools to address complicated nonconvex optimization problems including NP-hard problems of combinatorial optimization. In particular, computable self-concordant barriers for the cone of so-called copositive matrices and more general polynomial cones are discussed. Development of interior-point algorithms based on such barriers would open a totally new venue for the numerical analysis of various complex practical optimization problems, where the (approximate) knowledge of a global optimum is desirable.Concrete approaches are proposed to the use of Jordan-algebraic techniques for constructing treatable convex relaxations for a very general class of nonconvex optimization problems and to robust optimization. Proposed ideas for the transformation of polynomial programming problems into trigonometric counterparts may lead to significantly improved numerical stability of existing algorithms based on semi-definite programming approximations.Optimization problems play a very important role in a wide spectrum of applications. But existing algorithms and software allow one to reliably analyze only a very limited class of structured convex optimization problems, if the goal is to find a global optimum. The present project aims to contribute to the problem of finding global optimal solutions (or their reasonable estimates) for a much broader and more difficult class of optimization problems which includes (but is not limited to) various types of NP-hard problems of combinatorial optimization.

以下三个主题进行了讨论的项目：可计算的自我和谐的障碍函数，约旦代数方面的优化，和多维三角规划。 该项目的总体目标是开发新的计算和理论工具，以解决复杂的非凸优化问题，包括组合优化的NP难题。 特别是，可计算的自协调障碍的所谓的共正矩阵和更一般的多项式锥进行了讨论。 发展的边界点算法的基础上，这样的障碍将开辟一个全新的场地，各种复杂的实际优化问题的数值分析，在那里的（近似）知识的全局优化是可取的。具体的方法，提出了使用约旦代数技术构建可治疗的凸松弛的一个非常一般的一类非凸优化问题和鲁棒优化。 将多项式规划问题转化为三角形规划问题的思想可以显著提高现有基于半定规划近似的算法的数值稳定性，优化问题在广泛的应用中起着非常重要的作用。 但是，现有的算法和软件只允许可靠地分析一类非常有限的结构化凸优化问题，如果目标是找到一个全局最优。 本项目旨在为更广泛和更困难的优化问题（包括但不限于各种类型的组合优化NP难题）找到全局最优解（或其合理估计）。