Algebraic and Geometric aspects of Optimization

该项目讨论了以下三个主题：可计算的自协调障碍函数，优化的乔丹-代数方面，以及多维三角规划。该项目的总体目标是开发新的计算和理论工具来解决复杂的非凸优化问题，包括组合优化的NP-Hard问题。特别地，讨论了所谓的余正矩阵和更一般的多项式锥的锥的可计算自协调障碍。基于这些障碍的内点算法的发展将为各种复杂的实际优化问题的数值分析开辟一个全新的场所，其中需要全局最优解的(近似)知识。针对一类非常一般的非凸优化问题，提出了使用Jordan代数技术来构造可处理的凸松弛和稳健优化的具体方法。提出了将多项式规划问题转化为三角规划问题的思想，可以显著提高现有基于半定规划近似的算法的数值稳定性。优化问题在广泛的应用领域中扮演着非常重要的角色。但现有的算法和软件只允许人们可靠地分析一类非常有限的结构化凸优化问题，如果目标是找到全局最优的话。本项目致力于为更广泛和更困难的优化问题寻找全局最优解(或其合理估计)，这类优化问题包括(但不限于)各种类型的组合优化的NP-Hard问题。

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.