Complexity for exact polynomial optimization strengthened with Fritz John conditions

Abstract

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.

arXiv comment23 pages. arXiv admin note: text overlap with arXiv:2205.04254