Spectrahedra and Hyperbolic Polynomials

谱面和双曲多项式

• 批准号: 421473641
• 负责人: Professor Dr. Mario Kummer
• 金额: --
• 依托单位: Institut für Geometrie
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2019
• 资助国家: 德国
• 起止时间: 2018-12-31 至 2021-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/421473641?language=en
• 关键词: Spectrahedra; Hyperbolic; Polynomials

Semidefinite programming is a branch of convex optimization that has aroused great interest both theoretically and practically. Typical applications include polynomial optimization or combinatorial optimization, such as the Max-Cut Problem. With the help of interior-point method one can solve a semidefinite program for fixed precision in a time that is polynomial in the program description size. A question of fundamental interest is that of characterizing the sets which are the feasible sets of semidefinite programming, namely the so-called spectrahedra. The content of the generalized Lax conjecture is such a presumed characterization. Different authors have worked on this assumption and proved some special cases. The aim of this project is to achieve further positive results in this direction and optimally to solve the assumption completely.

半定规划是凸优化问题的一个分支，在理论和实践上都引起了人们极大的兴趣。典型的应用包括多项式优化或组合优化，如最大割问题。用邻点法可以在程序描述长度为多项式的时间内，以固定精度求解半定程序。一个基本的兴趣问题是，这是半定规划的可行集，即所谓的谱面集的特征。广义Lax猜想的内容就是这样一个假定的刻画。不同的作者在这个假设上进行了工作，并证明了一些特殊情况。该项目的目的是在这方面取得进一步的积极成果，并以最佳方式完全解决这一假设。