论文标题
通过Fritz John条件增强的精确多项式优化的复杂性
Complexity for exact polynomial optimization strengthened with Fritz John conditions
论文作者
论文摘要
令$ f，g_1，\ dots，g_m $为$ d $的多项式，在变量的向量中具有真实系数$ x =（x_1，\ dots，x_n）$。假设$ f $是由多项式不平等所定义的基本半代数套件$ g_j（x）\ ge 0 $，对于$ j = 1，\ dots，m $。我们以前的工作[ARXIV：2205.04254（2022）]根据Fritz John条件表示了几种$ F $的表示。本文提供了一些明确的学位界限，具体取决于这些表示形式的$ n $，$ m $和$ d $。在用于多项式优化的应用中，我们基于这些表示，获得了半决赛松弛层次结构的有限收敛速率。
Let $f,g_1,\dots,g_m$ be polynomials of degree at most $d$ with real coefficients in a vector of variables $x=(x_1,\dots,x_n)$. Assume that $f$ is non-negative on a basic semi-algebraic set $S$ defined by polynomial inequalities $g_j(x)\ge 0$, for $j=1,\dots,m$. Our previous work [arXiv:2205.04254 (2022)] has stated several representations of $f$ based on the Fritz John conditions. This paper provides some explicit degree bounds depending on $n$, $m$, and $d$ for these representations. In application to polynomial optimization, we obtain explicit rates of finite convergence of the hierarchies of semidefinite relaxations based on these representations.
