# Complexity for exact polynomial optimization strengthened with Fritz John
conditions

Ngoc Hoang Anh Mai111CNRS; LAAS; 7 avenue du Colonel Roche, F-31400 Toulouse;
France.

###### 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)\geq 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.

Keywords: sum-of-squares; Nichtnegativstellensatz; gradient ideal; Fritz John
conditions; polynomial optimization; convergence rate; finite convergence

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 First-order optimality conditions
    2. 2.2 Sets of critical points
    3. 2.3 Quadratic modules, preoderings, and ideals
    4. 2.4 Degree bound for Krivine–Stengle’s Nichtnegativstellensätze
    5. 2.5 Upper bound on the number of connected components of a basic semi-algebraic set
    6. 2.6 Sum-of-squares representations under the finite image assumption
    7. 2.7 Moment/Sum-of-squares relaxations for polynomial optimization
      1. 2.7.1 The case without denominators
      2. 2.7.2 The case with denominators
  3. 3 Explicit degree bounds for the representation based on the Fritz John conditions
    1. 3.1 The case of arbitrary multipliers
    2. 3.2 The case of nonnegative multipliers
    3. 3.3 The case with denominators
  4. 4 Convergence rate for exact polynomial optimization based on the Fritz John conditions
    1. 4.1 The case of arbitrary multipliers
    2. 4.2 The case of nonnegative multipliers
    3. 4.3 The case with denominators
  5. 5 Explicit degree bounds for the representation based on the Karush–Kuhn–Tucker conditions
    1. 5.1 The case of arbitrary multipliers
    2. 5.2 The case of nonnegative multipliers
  6. 6 Implicit degree bounds for the representations involving quadratic modules
    1. 6.1 The case without denominators
    2. 6.2 The case with denominators

##  1 Introduction

##### Nichtnegativstellensätze and their degree bounds.

Hilbert’s 17th problem concerns the representation of a non-negative
polynomial as a sum of squares of rational functions. Artin gave a positive
answer to this problem in [1]. Later Krivine [8] and Stengle [28] stated a
Nichtnegativstellensatz. It says that we can express a polynomial $f$ non-
negative on a basic semi-algebraic set $S$ as a linear combination of the
polynomials $g_{j}$ defining $S$ with weights which are sums of squares of
rational functions. Lombardi, Perrucci, and Roy have recently provided a
degree bound for Krivine–Stengle’s Nichtnegativstellensatz. It is a tower of
five exponentials depending only on the number of variables, the number of
polynomials $g_{j}$ defining $S$, and the degrees of $f,g_{j}$. Consequently,
they obtain the best-known bound degrees for the numerators and denominators
in Hilbert–Artin’s Nichtnegativstellensatz as a tower of five exponentials.

##### Positivstellensätze.

Today Positivstellensätze, representations of polynomials positive on a basic
semi-algebraic set, are of broad interest with influential applications in
polynomial optimization. Let us revisit two representations commonly used in
practice: Schmüdgen’s Positivstellensatz [25] says that we can write a
polynomial $f$ positive on a compact basic semi-algebraic set $S$ as a linear
combination of products of polynomials defining $S$ with weights which are
sums of squares of polynomials. Putinar presents in [21] a Positivstellensatz
saying that we con decompose a polynomial $f$ positive on a compact basic
semi-algebraic set $S$ satisfying the so-called Archimedean condition (stated
in [12]) as a linear combination of polynomials defining $S$ with weights
which are sums of squares of polynomials.

##### Polynomial optimization.

Let ${\mathbb{R}}[x]$ denote the ring of polynomials with real coefficients in
the vector of variables $x$. Given $r\in{\mathbb{N}}$, denote by
${\mathbb{R}}_{r}[x]$ the linear space of polynomials in ${\mathbb{R}}[x]$ of
degree at most $r$. Denote by $\Sigma^{2}[x]$ (resp. $\Sigma^{2}_{r}[x]$) the
cone of sum of squares of polynomials in ${\mathbb{R}}[x]$ (resp.
${\mathbb{R}}_{r}[x]$).

Given $f,g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$, consider polynomial
optimization problem:

$f^{\star}:=\inf\limits_{x\in S(g)}f(x)\,,$ (1)

where $S(g)$ is the basic semi-algebraic set associated with
$g=(g_{1},\dots,g_{m})$, i.e.,

$S(g):=\\{x\in{\mathbb{R}}^{n}\,:\,g_{j}(x)\geq 0\,,\,j=1,\dots,m\\}\,.$ (2)

Schmüdgen’s and Putinar’s Positivstellensatz are both applicable to polynomial
optimization. Indeed, the idea is to reformulate the original problem as
$f^{\star}=\sup\\{\lambda\in{\mathbb{R}}\,:\,f-\lambda>0\text{ on }S(g)\\}$
and then replace the constraint “$f-\lambda>0\text{ on }S(g)$” with the
representations of $f-\lambda$ associated with $g_{j}$. More explicitly, using
Putinar’s Positivstellensatz gives a sequence of reals
$(\rho_{k}^{\text{Pu}})_{k\in{\mathbb{N}}}$, where

$\begin{array}[]{rl}\rho_{k}^{\text{Pu}}:=\sup\limits_{\lambda,\sigma_{j}}&\lambda\\\
&\lambda\in{\mathbb{R}}\,,\,\sigma_{j}\in\Sigma^{2}[x]\,,\\\
&f-\lambda=\sum_{j=1}^{m}\sigma_{j}g_{j}\,,\,\deg(\sigma_{j}g_{j})\leq
2k\,,\end{array}$ (3)

where $g_{1}=1$. Here $\deg(\cdot)$ stands for the degree of a polynomial. The
sequence $(\rho_{k}^{\text{Pu}})_{k\in{\mathbb{N}}}$ converges to $f^{\star}$
under the Archimedean condition on $S$. Moreover, the program to compute each
$\rho_{k}^{\text{Pu}}$ is convex, specifically, semidefinite (see [3]). The
sequence of these programs is known as Lasserre’s hierarchy [9]. A similar
process applies to Schmüdgen’s Positivstellensatz to obtain the corresponding
sequence of reals $(\rho_{k}^{\text{Sch}})_{k\in{\mathbb{N}}}$ defined by

$\begin{array}[]{rl}\rho_{k}^{\text{Sch}}:=\sup\limits_{\lambda,\sigma_{j}}&\lambda\\\
&\lambda\in{\mathbb{R}}\,,\,\sigma_{j}\in\Sigma^{2}[x]\,,\\\
&f-\lambda=\sum_{\alpha\in\\{0,1\\}^{m}}\sigma_{\alpha}g_{1}^{\alpha_{1}}\dots
g_{m}^{\alpha_{m}}\,,\,\deg(\sigma_{\alpha}g_{\alpha})\leq 2k\,.\end{array}$
(4)

##### Convergence rates.

Schweighofer [26] (resp. Nie–Schweighofer [19]) analyzes the convergence rates
of sequence $(\rho_{k}^{\text{Sch}})_{k\in{\mathbb{N}}}$ (resp.
$(\rho_{k}^{\text{Pu}})_{k\in{\mathbb{N}}}$). Despite the polynomial time
complexity $\mathcal{O}(\varepsilon^{-c})$ of the former, the latter has
unexpected exponential time complexity $\mathcal{O}(\exp(\varepsilon^{-c}))$.
Baldi and Mourrain have recently provided in [2] an improved complexity
$\mathcal{O}(\varepsilon^{-c})$ for sequence
$(\rho_{k}^{\text{Pu}})_{k\in{\mathbb{N}}}$. It relies on the degree bound for
Schmudgen’s Positivstellensatz on the unit hypercube stated by Laurent and
Slot in [10]. In addition, Laurent and Slot obtain the optimal convergence
rate $\mathcal{O}(\varepsilon^{-1/2})$ for minimizing a polynomial on the unit
hypercube. To do this, Laurent and Slot utilize the polynomial kernel method
introduced in [6], where Fang and Fawzi provide the optimal convergence rate
$\mathcal{O}(\varepsilon^{-1/2})$ for minimizing a polynomial on the unit
sphere. Applying this method again, Slot achieves in [27] the optimal
convergence rate for $(\rho_{k}^{\text{Sch}})_{k\in{\mathbb{N}}}$ when $S$ is
the unit ball or the standard simplex.

##### Finite convergence.

The finite convergences of the two sequences
$(\rho_{k}^{\text{Sch}})_{k\in{\mathbb{N}}}$ and
$(\rho_{k}^{\text{Pu}})_{k\in{\mathbb{N}}}$ are mainly studied by Scheiderer
[22, 23, 24], Marshall [14, 15] and Nie [17]. In particular, Lasserre’s
hierarchy has finite convergence under the Archimedean condition and some
standard optimality conditions. These conditions make the original polynomial
optimization problem necessarily have finitely many global minimizers at which
the Karush–Kuhn–Tucker conditions hold for this problem. Recent efforts of
Nie–Demmel–Sturmfels [18], Demmel–Nie–Powers [5], Nie [16], and our previous
work [12] are to obtain the finite convergence of Lasserre’s hierarchy through
the information of the Jacobian of the objective and constrained polynomials.
However, rates of finite convergence for these methods have been open until
now.

##### Nichtnegativstellensätze based on Fritz John conditions.

Let $V(h_{\operatorname{FJ}})$ and $V(h_{\operatorname{FJ}}^{+})$ (defined
later in (36) and (44)) be the sets of points at which the Fritz John
conditions hold for problem (1). In our previous works [12], we use the
finiteness of the images of $S(g)\cap V(h_{\operatorname{FJ}})$ and $S(g)\cap
V(h_{\operatorname{FJ}}^{+})$ under $f$ to construct representations of
$f-f^{\star}$ without denominators involving quadratic modules and
preorderings associated with these two intersections. Here $f^{\star}$ is
defined as in (1). These non-negativity certificates allow us to tackle the
following two cases: (i) polynomial $f-f^{\star}$ is non-negative with
infinitely many zeros on basic semi-algebraic sets $S(g)$ and (ii) the
Karush–Kuhn–Tucker conditions do not hold for problem (1) at any zero of
$f-f^{\star}$ on $S(g)$.

##### Contribution.

In this paper, we aim to provide some explicit degree bounds for
Nichtnegativstellensätze in our previous work [12] and the work of Demmel,
Nie, and Powers [5]. To do this, we rely on the constructiveness of these
representations and utilize the degree bounds for Krivine–Stengle’s
Nichtnegativstellensätze analyzed by Lombardi, Perrucci, and Roy [11] as well
as the upper bound on the number of connected components of a basic semi-
algebraic set due to Coste [4].

We briefly sketch the analysis for the representation of $f-f^{\star}$ using
the set $V(h_{\operatorname{FJ}})$ as follows: We first decompose
$V(h_{\operatorname{FJ}})$ into finitely many connected components. Thanks to
Coste [4], the number of these components is bounded from above by a value
depending on the number of polynomials defining $V(h_{\operatorname{FJ}})$ and
the degrees of these polynomials. To prove that $f$ is constant on each
connected component, we rely on the Fritz John conditions generating
$V(h_{\operatorname{FJ}})$ and the assumption that the image of the set of
critical points $C(g)$ (defined later in (8)) under $f$ is finite. It turns
out that $f$ has finitely many values on $V(h_{\operatorname{FJ}})$. To obtain
the representation of $f-f^{\star}$ with explicit degree bound, we explicitly
construct a “variety version” of Lagrangian interpolation and utilize
Krivine–Stengle’s Nichtnegativstellensätze with degree bound given in [11].

We accordingly obtain the explicit convergence rate of each corresponding
hierarchy of semidefinite relaxations for a polynomial optimization problem.
The rates of these hierarchies depend on the number of variables, the number
of constraints, and the degrees of the input polynomials. In particular, they
do not depend on the coefficients of the input polynomials. Because of the
huge bounds on Krivine–Stengle’s Nichtnegativstellensätze and the number of
connected components of a basic semi-algebraic set, the rates are extremely
large.

##### Organization.

We organize the paper as follows: Section 2 is to recall some necessary tools
from real algebraic geometry. Section 3 states the explicit degree bounds for
our Nichtnegativstellensätze based on the Fritz John conditions. Section 4
presents the application of these bounds in analyzing the complexity of the
corresponding hierarchies of the exact semidefinite relaxations for a
polynomial optimization problem. Section 5 provides the explicit degree bounds
for the representation based on the Karush–Kuhn–Tucker conditions by Demmel,
Nie, and Powers in [5]. Section 6 shows the implicit degree bound for the
representations involving quadratic modules.

##  2 Preliminaries

This section presents some preliminaries from real algebraic geometry needed
to prove our main results.

###  2.1 First-order optimality conditions

Given $p\in{\mathbb{R}}[x]$, we denote by $\nabla p$ the gradient of $p$,
i.e., $\nabla p=(\frac{\partial p}{\partial x_{1}},\dots,\frac{\partial
p}{\partial x_{n}})$. We say that the Fritz John conditions hold for problem
(1) at $u\in S(g)$ if

$\begin{cases}\exists(\lambda_{0},\dots,\lambda_{m})\in[0,\infty)^{m+1}\,:\\\
\lambda_{0}\nabla f(u)=\sum_{j=1}^{m}\lambda_{j}\nabla g_{j}(u)\,,\\\
\lambda_{j}g_{j}(u)=0\,,\,j=1,\dots,m\,,\\\
\sum_{j=0}^{m}\lambda_{j}^{2}=1\,,\end{cases}\Leftrightarrow\begin{cases}\exists(\lambda_{0},\dots,\lambda_{m})\in{\mathbb{R}}^{m+1}\,:\\\
\lambda_{0}^{2}\nabla f(u)=\sum_{j=1}^{m}\lambda_{j}^{2}\nabla g_{j}(u)\,,\\\
\lambda_{j}^{2}g_{j}(u)=0\,,\,j=1,\dots,m\,,\\\
\sum_{j=0}^{m}\lambda_{j}^{2}=1\,.\end{cases}$ (5)

In addition, the Karush–Kuhn–Tucker conditions hold for problem (1) at $u\in
S(g)$ if

$\begin{cases}\exists(\lambda_{1},\dots,\lambda_{m})\in[0,\infty)^{m}\,:\\\
\nabla f(u)=\sum_{j=1}^{m}\lambda_{j}\nabla g_{j}(u)\,,\\\
\lambda_{j}g_{j}(u)=0\,,\,j=1,\dots,m\,.\end{cases}\Leftrightarrow\begin{cases}\exists(\lambda_{1},\dots,\lambda_{m})\in{\mathbb{R}}^{m}\,:\\\
\nabla f(u)=\sum_{j=1}^{m}\lambda_{j}^{2}\nabla g_{j}(u)\,,\\\
\lambda_{j}^{2}g_{j}(u)=0\,,\,j=1,\dots,m\,.\end{cases}$ (6)

If $u$ is a local minimizer for problem (1), then the Fritz John conditions
hold for problem (1) at $u$. In contrast, there exist cases where the
Karush–Kuhn–Tucker conditions do not hold for problem (1) at any local
minimizer of this problem. We denote by $W(f,g)$ the set of all points at
which the Fritz John conditions hold but the Karush–Kuhn–Tucker conditions do
not hold for problem (1).

###  2.2 Sets of critical points

Given $g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$, let
$\varphi^{g}:{\mathbb{R}}^{n}\to{\mathbb{R}}^{(n+m)\times m}$ be a function
associated with $g=(g_{1},\dots,g_{m})$ defined by

$\varphi^{g}(x)=\begin{bmatrix}\nabla g(x)\\\
\operatorname{diag}(g(x))\end{bmatrix}=\begin{bmatrix}\nabla
g_{1}(x)&\dots&\nabla g_{m}(x)\\\ g_{1}(x)&\dots&0\\\ .&\dots&.\\\
0&\dots&g_{m}(x)\end{bmatrix}\,.$ (7)

Given a real matrix $A$, we denote by $\operatorname{rank}(A)$ the dimension
of the vector space generated by the columns of $A$ over ${\mathbb{R}}$. We
say that a set $\Omega$ is finite if its cardinal number is a non-negative
integer. Let $C(g)$ be the set of critical points associated with $g$ defined
by

$C(g):=\\{x\in{\mathbb{R}}^{n}\,:\,\operatorname{rank}(\varphi^{g}(x))<m\\}.$
(8)

Given a real matrix $A$, we denote by $\operatorname{rank}^{+}(A)$ the largest
number of columns of $A$ whose convex hull over ${\mathbb{R}}$ has no zero.
Let $C^{+}(g)$ be the set of critical points associated with $g$ defined by

$C^{+}(g):=\\{x\in{\mathbb{R}}^{n}\,:\,\operatorname{rank}^{+}(\varphi^{g}(x))<m\\}.$
(9)

###  2.3 Quadratic modules, preoderings, and ideals

Given $g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$, let $Q_{r}(g)[x]$ be the
truncated quadratic module of order $r\in{\mathbb{N}}$ associated with
$g=(g_{1},\dots,g_{m})$, i.e.,

$Q_{r}(g)[x]:=\\{\sigma_{0}+\sum_{j=1}^{m}g_{j}\sigma_{j}\,:\,\sigma_{j}\in\Sigma^{2}[x]\,,\,\deg(\sigma_{0})\leq
2r\,,\,\deg(g_{j}\sigma_{j})\leq 2r\\}\,.$ (10)

Let $\Pi g$ be the vector of products of $g_{1},\dots,g_{m}$ defined by

$\Pi g:=(g^{\alpha})_{\alpha\in\\{0,1\\}^{m}\backslash\\{0\\}}\,,$ (11)

where $\alpha=(\alpha_{1},\dots,\alpha_{m})$ and
$g^{\alpha}:=g_{1}^{\alpha_{1}}\dots g_{m}^{\alpha_{m}}$. We call $Q_{r}(\Pi
g)[x]$ the truncated preordering of order $r\in{\mathbb{N}}$ generated by $g$,
denoted by $P_{r}(g)[x]$. Obviously, if $m=1$, it holds that
$P_{r}(g)[x]=Q_{r}(g)[x]$.

Given $h_{1},\dots,h_{l}\in{\mathbb{R}}[x]$, let $V(h)$ be the variety
generated by $h=(h_{1},\dots,h_{l})$, i.e.,

$V(h):=\\{x\in{\mathbb{R}}^{n}\,:\,h_{j}(x)=0\,,\,j=1,\dots,l\\}\,.$ (12)

and let $I_{r}(h)[x]$ be the truncated ideal of order $r$ generated by $h$,
i.e.,

$I_{r}(h)[x]:=\\{\sum_{j=1}^{l}h_{j}\psi_{j}\,:\,\psi_{j}\in{\mathbb{R}}[x]\,,\,\deg(h_{j}\psi_{j})\leq
2r\\}\,.$ (13)

###  2.4 Degree bound for Krivine–Stengle’s Nichtnegativstellensätze

We denote by $\operatorname{bit}(d)$ the number of bits of $d\in{\mathbb{N}}$,
i.e.,

$\operatorname{bit}(d):=\begin{cases}1&\text{if }d=0\,,\\\ k&\text{if }d\neq
0\text{ and }2^{k-1}\leq d<2^{k}.\end{cases}$ (14)

Given $n,d,s\in{\mathbb{N}}$, set

$b(n,d,s):=2^{2^{\left(2^{\max\\{2,d\\}^{4^{n}}}+s^{2^{n}}\max\\{2,d\\}^{16^{n}\operatorname{bit}(d)}\right)}}\,.$
(15)

We recall the degree bound for Krivine–Stengle’s Nichtnegativstellensätze
analyzed by Lombardi, Perrucci, and Roy [11] in the following two lemmas:

######  Lemma 1.

Let $g_{1},\dots,g_{m},h_{1},\dots,h_{l}\in{\mathbb{R}}_{d}[x]$. Assume that
$S(g)\cap V(h)=\emptyset$ with $g:=(g_{1},\dots,g_{m})$ and
$h:=(h_{1},\dots,h_{l})$. Set $r=b(n,d,m+l+1)/2$. Then it holds that $-1\in
P_{r}(g)[x]+I_{r}(h)[x]$.

######  Lemma 2.

Let $p,g_{1},\dots,g_{m},h_{1},\dots,h_{l}\in{\mathbb{R}}_{d}[x]$. Assume that
$p$ vanishes on $S(g)\cap V(h)$ with $g:=(g_{1},\dots,g_{m})$ and
$h:=(h_{1},\dots,h_{l})$. Set $r:=b(n,d,m+l+1)/2$ and $s:=2\lfloor
r/d\rfloor$. Then it holds that $-p^{s}\in P_{r}(g)[x]+I_{r}(h)[x]$.

###  2.5 Upper bound on the number of connected components of a basic semi-
algebraic set

We generalize the definition of basic semi-algebraic sets as follows: A semi-
algebraic subset of ${\mathbb{R}}^{n}$ is a subset of the form

$\bigcup_{i=1}^{t}\bigcap_{j=1}^{r_{i}}\\{x\in{\mathbb{R}}^{n}\,:\,f_{ij}(x)*_{ij}0\\}\,,$
(16)

where $f_{ij}\in{\mathbb{R}}[x]$ and $*_{ij}$ is either $>$ or $=$.

Given two semi-algebraic sets $A\subset{\mathbb{R}}^{n}$ and
$B\subset{\mathbb{R}}^{m}$, we say that a mapping $f:A\to B$ is semi-algebraic
if its graph $\\{(x,f(x))\,:\,x\in A\\}$ is a semi-algebraic set in
${\mathbb{R}}^{n+m}$. A semi-algebraic subset $A\subset{\mathbb{R}}^{n}$ is
said to be semi-algebraically path connected if for every $x,y$ in $A$, there
exists a continuous semi-algebraic mapping $\phi:[0,1]\to A$ such that
$\phi(0)=x$ and $\phi(1)=y$. Note that $\phi$ is piecewise-differentiable in
this case (see, e.g., [20, Theorem 1.8.1]).

Given $n,d,s\in{\mathbb{N}}$, set

$c(n,d,s):=d(2d-1)^{n+s-1}\,.$ (17)

The upper bound on the number of connected components of a basic semi-
algebraic set is stated by Coste [4, Proposition 4.13] as follows:

######  Lemma 3.

Let $g_{1},\dots,g_{m},h_{1},\dots,h_{l}\in{\mathbb{R}}_{d}[x]$ with $d\geq
2$. The number of (semi-algebraically path) connected components of $S(g)\cap
V(h)$ is not greater than $c(n,d,m+l)$.

###  2.6 Sum-of-squares representations under the finite image assumption

Let $|\cdot|$ stand for the cardinal number of a set. Denote by $\delta_{ij}$
the Kronecker delta function at $(i,j)\in{\mathbb{N}}^{2}$.

We state in the following lemmas the representations of polynomials
nonnegative on semi-algebraic sets under the finite image assumption:

######  Lemma 4.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ and
$h_{1},\dots,h_{l}\in{\mathbb{R}}_{d+1}[x]$. Assume that $f$ is non-negative
on $S(g)$ with $g=(g_{1},\dots,g_{m})$ and $f(V(h))$ is finite with
$h=(h_{1},\dots,h_{l})$. Set $r:=|f(V(h))|$ and $u:=b(n,d+1,m+l+2)/2$. Then
there exist $q\in P_{w}(g)[x]$ with $w=dr+u$ such that $f-q$ vanishes on
$V(h)$.

###### Proof.

By assumption, we get $f(V(h))=\\{t_{1},\dots,t_{r}\\}\subset{\mathbb{R}}$,
where $t_{i}\neq t_{j}$ if $i\neq j$. For $j=1,\dots,r$, let
$W_{j}:=V(h,f-t_{j})$. Then $W_{j}$ is a real variety generated by $l+1$
polynomials in ${\mathbb{R}}_{d+1}[x]$. It is clear that
$f(W_{j})=\\{t_{j}\\}$.

Define the following polynomials:

$p_{j}(x)=\prod_{i\neq j}\frac{f(x)-t_{i}}{t_{j}-t_{i}}\,,\,j=1,\dots,r\,.$
(18)

It is easy to check that $p_{j}(W_{i})=\\{\delta_{ji}\\}$ and $\deg(p_{j})\leq
d(r-1)$. Without loss of generality, we assume that there is
$s\in\\{0,1,\dots,r-1\\}$ such that $W_{j}\cap S(g)=\emptyset$, for
$j=1,\dots,s$, and $W_{i}\cap S(g)\neq\emptyset$, for $i=s+1,\dots,r$.

Let $j\in\\{1,\dots,s\\}$. Since $W_{j}\cap S(g)=\emptyset$, Lemma 1 says that
$-1\in P_{u}(g)[x]+I_{u}(h,f-t_{j})[x]$. It implies that there exists
$v_{j}\in P_{u}(g)[x]$ such that $-1=v_{j}$ on $W_{j}$. We have
$f=s_{1}-s_{2}$ for the SOS polynomials $s_{1}=(f+\frac{1}{2})^{2}$ and
$s_{2}=f^{2}+\frac{1}{4}$. It implies that $f=s_{1}+v_{j}s_{2}$ on $W_{j}$.
Let $q_{j}=s_{1}+v_{j}s_{2}\in P_{u+d}(g)[x]$.

Since $f\geq 0$ on $S(g)$, it holds that $f=t_{i}\geq 0$ on $W_{i}$, for
$i=s+1,\dots,r$. Now letting

$q=\sum_{j=1}^{s}q_{j}p_{j}^{2}+\sum_{i=s+1}^{r}t_{i}p_{i}^{2}\,,$ (19)

we obtain $q\in P_{w}(g)[x]$ since $\deg(t_{i}p_{i}^{2})\leq 2\deg(p_{i})\leq
2d(r-1)\leq 2w$ and

$\deg(q_{j}p_{j}^{2})\leq\deg(q_{j})+2\deg(p_{j})\leq 2(d+u+d(r-1))=2w\,,$
(20)

Hence $f-q$ vanishes on $V(h)=W_{1}\cup\dots\cup W_{r}$. ∎

######  Lemma 5.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ and
$h_{1},\dots,h_{l}\in{\mathbb{R}}_{d+1}[x]$. Assume that $f$ is non-negative
on $S(g)$ with $g=(g_{1},\dots,g_{m})$ and $f(V(h)\backslash A)$ is finite
with $h=(h_{1},\dots,h_{l})$ and $A\subset{\mathbb{R}}^{n}$. Set
$r:=|f(V(h)\backslash A)|$ and $u:=b(n,d+1,m+l+2)/2$. Then there exist $q\in
P_{w}(g)[x,\bar{\lambda}]$ with $w=dr+u$ such that $f-q$ vanishes on
$V(h)\backslash A$.

###### Proof.

By assumption, we get $f(V(h)\backslash
A)=\\{t_{1},\dots,t_{r}\\}\subset{\mathbb{R}}$, where $t_{i}\neq t_{j}$ if
$i\neq j$. We now handle in much the same way as the proof of Lemma 4 to get
$q\in P_{w}(g)[x]$ in (19). Hence $f-q$ vanishes on $V(h)\backslash A\subset
W_{1}\cup\dots\cup W_{r}$. ∎

######  Lemma 6.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ and
$h_{1},\dots,h_{l}\in{\mathbb{R}}_{d+1}[x]$. Assume that $f$ is non-negative
on $S(g)$ with $g=(g_{1},\dots,g_{m})$ and $f(S(g)\cap V(h))$ is finite with
$h=(h_{1},\dots,h_{l})$. Set $r:=|f(S(g)\cap V(h))|$. Then there exist $q\in
P_{w}(g)[x,\bar{\lambda}]$ with $w=d(r-1)$ such that $f-q$ vanishes on
$S(g)\cap V(h)$.

###### Proof.

By assumption, we get $f(S(g)\cap
V(h))=\\{t_{1},\dots,t_{r}\\}\subset{\mathbb{R}}$, where $t_{i}\neq t_{j}$ if
$i\neq j$. For $j=1,\dots,r$, let $W_{j}:=V(h,f-t_{j})$. Then $W_{j}$ is a
real variety generated by $l+1$ polynomials in ${\mathbb{R}}_{d+1}[x]$. It is
clear that $f(W_{j})=\\{t_{j}\\}$. Define polynomials $p_{j}$, for
$j=1,\dots,r$, as in (18). It is easy to check that $W_{i}\cap
S(g)\neq\emptyset$, $p_{j}(W_{i})=\\{\delta_{ji}\\}$ and $\deg(p_{j})\leq
d(r-1)$. Since $f\geq 0$ on $S(g)$, it holds that $f=t_{i}\geq 0$ on $W_{i}$,
for $i=1,\dots,r$. Now letting $q=\sum_{i=1}^{r}t_{i}p_{i}^{2}$, we obtain
$q\in\Sigma_{w}^{2}[x]$ with $w=d(r-1)$, and hence $f-q$ vanishes on
$W_{1}\cup\dots\cup W_{r}\supset S(g)\cap V(h)$. ∎

###  2.7 Moment/Sum-of-squares relaxations for polynomial optimization

We recall some preliminaries of the Moment/Sum-of-squares relaxations
originally developed by Lasserre in [9].

Given $d\in{\mathbb{N}}$, let
${\mathbb{N}}^{n}_{d}:=\\{\alpha\in{\mathbb{N}}^{n}\,:\,\sum_{j=1}^{n}\alpha_{j}\leq
d\\}$. Given $d\in{\mathbb{N}}$, we denote by $v_{d}$ the vector of monomials
in $x$ of degree at most $d$, i.e.,
$v_{d}=(x^{\alpha})_{\alpha\in{\mathbb{N}}^{n}_{d}}$ with
$x^{\alpha}:=x_{1}^{\alpha_{1}}\dots x_{n}^{\alpha_{n}}$. For each
$p\in{\mathbb{R}}_{d}[x]$, we write
$p=c(p)^{\top}v_{d}=\sum_{\alpha\in{\mathbb{N}}^{n}_{d}}p_{\alpha}x^{\alpha}$,
where $c(p)$ is denoted by the vector of coefficient of $p$, i.e.,
$c(p)=(p_{\alpha})_{\alpha\in{\mathbb{N}}^{n}_{d}}$ with
$p_{\alpha}\in{\mathbb{R}}$. Given $A\in{\mathbb{R}}^{r\times r}$ being
symmetric, we say that $A$ is positive semidefinite, denoted by $A\succeq 0$,
if every eigenvalue of $A$ is non-negative.

##### Moment/Localizing matrices.

Given $y=(y_{\alpha})_{\alpha\in{\mathbb{N}}^{n}}\subset{\mathbb{R}}$, let
$L_{y}:{\mathbb{R}}[x]\to{\mathbb{R}}$ be the Riesz linear functional defined
by $L_{y}(p)=\sum_{\alpha\in{\mathbb{N}}^{n}}p_{\alpha}y_{\alpha}$ for every
$p\in{\mathbb{R}}[x]$. Given $d\in{\mathbb{N}}$, $p\in{\mathbb{R}}[x]$ and
$y=(y_{\alpha})_{\alpha\in{\mathbb{N}}^{n}}\subset{\mathbb{R}}$, let
$M_{d}(y)$ be the moment matrix of order $d$ defined by
$(y_{\alpha+\beta})_{\alpha,\beta\in{\mathbb{N}}^{n}_{d}}$ and let $M_{d}(py)$
be the localizing matrix of order $d$ associated with $p$ defined by
$(\sum_{\gamma\in{\mathbb{N}}^{n}}p_{\gamma}y_{\alpha+\beta+\gamma})_{\alpha,\beta\in{\mathbb{N}}^{n}_{d}}$.

##### Truncated quadratic modules/ideals.

Given $g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$, let $Q_{d}(g)[x]$ be the
truncated quadratic module of order $d$ associated with
$g=(g_{1},\dots,g_{m})$ defined by

$Q_{d}(g)[x]=\\{\sigma_{0}+\sum_{j=1}^{m}\sigma_{j}g_{j}\,:\,\sigma_{j}\in\Sigma^{2}[x]\,,\,\deg(\sigma_{0})\leq
2d\,,\,\deg(\sigma_{j}g_{j})\leq 2d\\}\,.$ (21)

Given $h_{1},\dots,h_{l}\in{\mathbb{R}}[x]$, let $I_{d}(h)$ be the truncated
ideal of order $d$ associated with $h=(h_{1},\dots,h_{l})$ defined by

$I_{d}(h)[x]=\\{\sum_{j=1}^{l}\psi_{j}h_{j}\,:\,\psi_{j}\in{\mathbb{R}}[x]\,,\,\deg(\psi_{j}h_{j})\leq
2d\\}\,.$ (22)

##### Problem statement.

Consider polynomial optimization problem:

$\bar{f}^{\star}:=\inf\limits_{x\in S(g)\cap V(h)}f(x)\,,$ (23)

where $g=(g_{1},\dots,g_{m})$ and $h=(h_{1},\dots,h_{l})$ with
$f,g_{i},h_{j}\in{\mathbb{R}}[x]$.

####  2.7.1 The case without denominators

Given $k\in{\mathbb{N}}$ and
$f,g_{1},\dots,g_{m},h_{1},\dots,h_{l}\in{\mathbb{R}}[x]$, consider the
following primal-dual semidefinite programs associated with $f$,
$g=(g_{1},\dots,g_{m})$ and $h=(h_{1},\dots,h_{l})$:

$\begin{array}[]{rl}\tau_{k}(f,g,h):=\inf\limits_{y}&L_{y}(f)\\\
\text{s.t}&M_{k}(y)\succeq 0\,,\,M_{k-d_{j}}(g_{j}y)\succeq
0\,,\,j=1,\dots,m\,,\\\
&M_{k-r_{t}}(h_{t}y)=0\,,\,t=1,\dots,l\,,\,y_{0}=1\,,\end{array}$ (24)
$\begin{array}[]{rl}\rho_{k}(f,g,h):=\sup\limits_{\xi,G_{j},u_{t}}&\xi\\\
\text{s.t}&G_{j}\succeq 0\,,\\\
&f-\xi=v_{k}^{\top}G_{0}v_{k}+\sum_{j=1}^{m}g_{j}v_{k-d_{j}}^{\top}G_{j}v_{k-d_{j}}\\\
&\qquad\qquad+\sum_{t=1}^{l}h_{t}u_{t}^{\top}v_{2r_{t}}\,,\\\ \end{array}$
(25)

where $d_{j}=\lceil\deg(g_{j})/2\rceil$ and $r_{t}=\lceil\deg(h_{t})/2\rceil$.
Using [12, Lemma 15], we obtain

$\rho_{k}(f,g,h)=\sup_{\xi\in{\mathbb{R}}}\\{\xi\,:\,f-\xi\in
Q_{k}(g)[x]+I_{k}(h)[x]\\}\,.$ (26)

We call primal-dual semidefinite programs (24)-(25) the Moment/Sum-of-squares
relaxations of order $k$ for problem (23).

We state in the following lemma some recent results involving the Moment/Sum-
of-squares relaxations:

######  Lemma 7.

Let $f\in{\mathbb{R}}_{d}[x]$, $g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$ and
$h_{1},\dots,h_{l}\in{\mathbb{R}}_{d+1}[x]$. Let $\bar{f}^{\star}$ be as in
(23) with $g=(g_{1},\dots,g_{m})$ and $h=(h_{1},\dots,h_{l})$. Then the
following statements hold:

  1. 1.

For every $k\in{\mathbb{N}}$, $\tau_{k}(f,g,h)\leq\tau_{k+1}(f,g,h)$ and
$\rho_{k}(f,g,h)\leq\rho_{k+1}(f,g,h)$.

  2. 2.

For every $k\in{\mathbb{N}}$,
$\rho_{k}(f,g,h)\leq\tau_{k}(f,g,h)\leq\bar{f}^{\star}$.

  3. 3.

If $S(g)\cap V(h)$ has non-empty interior, for $k\in{\mathbb{N}}$ sufficient
large, the Slater condition holds for the Moment relaxation (24) of order $k$.

  4. 4.

If $S(g)\cap V(h)$ satisfies the Archimedean condition,
$\rho_{k}(f,g,h)\to\bar{f}^{\star}$ as $k\to\infty$.

  5. 5.

If there exists $R>0$ such that $g_{m}+h_{l}=R-x_{1}^{2}-\dots-x_{n}^{2}$, for
$k\in{\mathbb{N}}$ sufficient large, the Slater condition holds for the SOS
relaxation (25) of order $k$.

  6. 6.

If there exists $q\in Q_{w}(g)[x]$ with $2w\geq d+1$ such that
$f-\bar{f}^{\star}-q$ vanishes on $V(h)$, then
$\rho_{r}(f,g,h)=\bar{f}^{\star}$ with $r=b(n,2w,l+1)/2$.

  7. 7.

If there exists $q\in\Sigma_{w}^{2}[x]$ with $2w\geq d+1$ such that
$f-\bar{f}^{\star}-q$ vanishes on $V(h)\cap S(g)$, then $\rho_{k}(f,\Pi
g,h)=\bar{f}^{\star}$ with $r=b(n,2w,m+l+1)/2$.

###### Proof.

The proofs of the first five statements can be found in [12]. Let us prove the
sixth statement. Let $u=f-\bar{f}^{\star}-q$. By assumption,we get
$u\in{\mathbb{R}}_{2w}[x]$ and $u=0$ on $V(h)$. Set $s=2\lfloor
r/(2w)\rfloor$. From this, Lemma 2 says that there exist
$\sigma\in\Sigma_{r}^{2}[x]$ such that $u^{2s}+\sigma\in I_{r}(h)[x]$. Let
$c=\frac{1}{2s}$. Then it holds that $1+t+ct^{2s}\in\Sigma^{2}_{s}[t]$. Thus
for all $\varepsilon>0$, we have

$f-\bar{f}^{\star}+\varepsilon=q+\varepsilon(1+\frac{u}{\varepsilon}+c\left(\frac{u}{\varepsilon}\right)^{2s})-c\varepsilon^{1-2s}(u^{2s}+\sigma)+c\varepsilon^{1-2s}\sigma\in
Q_{r}(g)[x]+I_{r}(h)[x]\,.$ (27)

Then we for all $\varepsilon>0$, $\bar{f}^{\star}-\varepsilon$ is a feasible
solution of (26) of the value $\rho_{r}(f,g,h)$. It gives
$\rho_{r}(f,g,h)\geq\bar{f}^{\star}-\varepsilon$, for all $\varepsilon>0$,
and, in consequence, we get $\rho_{r}(f,g,h)\geq\bar{f}^{\star}$. Using the
second statement, we obtain that $\rho_{r}(f,g,h)=\bar{f}^{\star}$, yielding
the sixth statement.

We prove the final statement. Let $u=f-\bar{f}^{\star}-q$. By assumption,we
get $u=0$ on $S(g)\cap V(h)$. Set $s=2\lfloor r/(2w)\rfloor$. From this, Lemma
2 says that there exist $\eta\in P_{r}(g)[x]$ such that $u^{2s}+\eta\in
I_{r}(h)[x]$. Let $c=\frac{1}{2s}$. Then it holds that
$1+t+ct^{2s}\in\Sigma_{s}^{2}[t]$. Thus for all $\varepsilon>0$, we have

$f-\bar{f}^{\star}+\varepsilon=q+\varepsilon(1+\frac{u}{\varepsilon}+c\left(\frac{u}{\varepsilon}\right)^{2s})-c\varepsilon^{1-2s}(u^{2s}+\eta)+c\varepsilon^{1-2s}\eta\in
P_{r}(g)[x]+I_{r}(h)[x]\,.$ (28)

Analysis similar to that in the proof of the third statement shows
$\rho_{r}(f,\Pi g,h)=\bar{f}^{\star}$, yielding the final statement. ∎

####  2.7.2 The case with denominators

Given $k\in{\mathbb{N}}$ and
$f,g_{1},\dots,g_{m},h_{1},\dots,h_{l},\theta\in{\mathbb{R}}[x]\backslash\\{0\\}$,
consider the following primal-dual semidefinite programs associated with $f$,
$g=(g_{1},\dots,g_{m})$ and $h=(h_{1},\dots,h_{l})$:

$\begin{array}[]{rl}\tau_{k}(f,g,h,\theta):=\inf\limits_{y}&L_{y}(\theta^{\eta(k,f,\theta)}f)\\\
\text{s.t}&M_{k}(y)\succeq 0\,,\,M_{k-d_{j}}(g_{j}y)\succeq
0\,,\,j=1,\dots,m\,,\\\
&M_{k-r_{t}}(h_{t}y)=0\,,\,t=1,\dots,l\,,\,L_{y}(\theta^{\eta(k,f,\theta)})=1\,,\end{array}$
(29)
$\begin{array}[]{rl}\rho_{k}(f,g,h,\theta):=\sup\limits_{\xi,G_{j},u_{t}}&\xi\\\
\text{s.t}&G_{j}\succeq 0\,,\\\
&\theta^{\eta(k,f,\theta)}(f-\xi)=v_{k}^{\top}G_{0}v_{k}+\sum_{j=1}^{m}g_{j}v_{k-d_{j}}^{\top}G_{j}v_{k-d_{j}}\\\
&\qquad\qquad+\sum_{t=1}^{l}h_{t}u_{t}^{\top}v_{2r_{t}}\,,\\\ \end{array}$
(30)

where $d_{j}=\lceil\deg(g_{j})/2\rceil$, $r_{t}=\lceil\deg(h_{t})/2\rceil$,
and

$\eta(k,f,\theta):=2\lfloor\frac{2k-\deg(f)}{2\deg(\theta)}\rfloor\,.$ (31)

Using [12, Lemma 15], we obtain

$\rho_{k}(f,g,h,\theta):=\sup_{\xi\in{\mathbb{R}}}\\{\xi\,:\,\theta^{\eta(k,f,\theta)}(f-\xi)\in
Q_{k}(g)[x]+I_{k}(h)[x]\\}\,.$ (32)

Developed in [13], primal-dual semidefinite programs (29)-(30) are another
type of the Moment/Sum-of-squares relaxations of order $k$ for problem (23).

We state in the following lemma some recent results involving this type of
Moment/Sum-of-squares relaxations:

######  Lemma 8.

Let $f\in{\mathbb{R}}_{d}[x]$, $g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$,
$h_{1},\dots,h_{l}\in{\mathbb{R}}_{d+1}[x]$, and
$\theta\in{\mathbb{R}}_{2u}[x]\backslash\\{0\\}$. Let $\bar{f}^{\star}$ be as
in (23) with $g=(g_{1},\dots,g_{m})$ and $h=(h_{1},\dots,h_{l})$. Then the
following statements hold:

  1. 1.

For every $k\in{\mathbb{N}}$,
$\tau_{k}(f,g,h,\theta)\leq\tau_{k+1}(f,g,h,\theta)$,
$\rho_{k}(f,g,h,\theta)\leq\rho_{k+1}(f,g,h,\theta)$, and
$\rho_{k}(f,g,h,\theta)\leq\tau_{k}(f,g,h,\theta)$.

  2. 2.

If $S(g)\cap V(h)$ has non-empty interior, for $k\in{\mathbb{N}}$ sufficient
large, the Slater condition holds for the Moment relaxation (24) of order $k$.

  3. 3.

If one of the following two conditions holds:

    1. (a)

problem (23) has an optimal solution $x^{\star}$ such that
$\theta(x^{\star})>0$;

    2. (b)

there exists a sequence of feasible solutions $(x^{(t)})_{t\in{\mathbb{N}}}$
for problem (23) such that $(f(x^{(t)}))_{t\in{\mathbb{N}}}$ converges to
$\bar{f}^{\star}$ and $\theta(x^{(t)})>0$,

then for every $k\in{\mathbb{N}}$,
$\rho_{k}(f,g,h,\theta)\leq\bar{f}^{\star}$.

  4. 4.

If $\rho_{k}(f,g,h,\theta)\leq\bar{f}^{\star}$, for every $k\in{\mathbb{N}}$,
and there exists $q\in Q_{w}(g)[x]$ with $2(w+u)\geq d+1$ such that
$\theta(f-\bar{f}^{\star}-q)$ vanishes on $V(h)$, then
$\rho_{r}(f,g,h,\theta)=\bar{f}^{\star}$ with $r=b(n,2(w+u),l+1)/2$.

###### Proof.

The proofs of the first two statements are similar to the ones of Lemma 7 (see
also in [13]). Let us prove the third statement. Let $\varepsilon>0$. By (32),
we get

$\theta^{\eta(k,f,\theta)}(f-\rho_{k}(f,g,h,\theta)+\varepsilon)\in
Q_{k}(g)[x]+I_{k}(h)[x]\,.$ (33)

Consider the following two cases:

  * •

Assume that the condition (a) holds. By (33), it implies that
$\theta(x^{\star})^{\eta(k,f,\theta)}(\bar{f}^{\star}-\rho_{k}(f,g,h,\theta)+\varepsilon)\geq
0$. Since $\theta(x^{\star})>0$,
$\bar{f}^{\star}\geq\rho_{k}(f,g,h,\theta)-\varepsilon$. The result follows
since $\varepsilon$ is arbitrary.

  * •

Assume that the condition (b) holds. By (33), it implies that
$\theta(x^{(t)})^{\eta(k,f,\theta)}(f(x^{(t)})-\rho_{k}(f,g,h,\theta)+\varepsilon)\geq
0$. Since $\theta(x^{(t)})>0$,
$f(x^{(t)})\geq\rho_{k}(f,g,h,\theta)-\varepsilon$. As $t$ goes to infinity,
$\bar{f}^{\star}\geq\rho_{k}(f,g,h,\theta)-\varepsilon$. The result follows
since $\varepsilon$ is arbitrary.

Let us prove the fourth statement. Let $p=f-\bar{f}^{\star}-q$. By
assumption,we get $\theta p\in{\mathbb{R}}_{2(w+u)}[x]$ and $\theta p=0$ on
$V(h)$. Set $s=2\lfloor r/(2w)\rfloor$. From this, Lemma 2 says that there
exist $\sigma\in\Sigma_{r}^{2}[x]$ such that $(\theta p)^{2s}+\sigma\in
I_{r}(h)[x]$. Let $c=\frac{1}{2s}$. Then it holds that
$1+t+ct^{2s}\in\Sigma^{2}_{s}[t]$. Thus for all $\varepsilon>0$, we have

$\theta(f-\bar{f}^{\star}+\varepsilon)=\theta
q+\varepsilon\theta(1+\frac{p}{\varepsilon}+c\left(\frac{p}{\varepsilon}\right)^{2s})-c(\varepsilon\theta)^{1-2s}((\theta
p)^{2s}+\sigma)+c(\varepsilon\theta)^{1-2s}\sigma\,.$ (34)

It implies that $\theta^{2s}(f-\bar{f}^{\star}+\varepsilon)\in
Q_{r}(g)[x]+I_{r}(h)[x]$. Then we for all $\varepsilon>0$,
$\bar{f}^{\star}-\varepsilon$ is a feasible solution of (26) of the value
$\rho_{r}(f,g,h,\theta)$. It gives
$\rho_{r}(f,g,h,\theta)\geq\bar{f}^{\star}-\varepsilon$, for all
$\varepsilon>0$, and, in consequence, we get
$\rho_{r}(f,g,h,\theta)\geq\bar{f}^{\star}$. By assumption, we obtain that
$\rho_{r}(f,g,h,\theta)=\bar{f}^{\star}$, yielding the final statement. ∎

##  3 Explicit degree bounds for the representation based on the Fritz John
conditions

This section provides the degree bounds for our five Nichtnegativstellensätze
based on the Fritz John conditions.

Let $\bar{\lambda}=(\lambda_{0},\lambda_{1},\dots,\lambda_{m})$ be a vector of
$m$ variables. Set $\lambda:=(\lambda_{1},\dots,\lambda_{m})$.

###  3.1 The case of arbitrary multipliers

We state the first main result in the following theorem:

######  Theorem 1.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\geq 1$. Assume that
$f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$ and $f(C(g))$ is
finite. Set

$w:=\frac{1}{2}\times b(n+m+1,d+1,2m+n+3)+d\times{c(n+m+1,d+1,n+m+1)}\,.$ (35)

Then there exists $q\in P_{w}(g)[x,\bar{\lambda}]$ such that $f-q$ vanishes on
$V(h_{\operatorname{FJ}})$, where
$\bar{\lambda}:=(\lambda_{0},\dots,\lambda_{m})$ and

$h_{\operatorname{FJ}}:=(\lambda_{0}\nabla f-\sum_{j=1}^{m}\lambda_{j}\nabla
g_{j},\lambda_{1}g_{1},\dots,\lambda_{m}g_{m},1-\sum_{j=0}^{m}\lambda_{j}^{2})\,.$
(36)

###### Proof.

Using Lemma 3, we decompose $V(h_{\operatorname{FJ}})$ into semi-algebraically
path connected components: $Z_{1},\dots,Z_{s}$ with

$s\leq c(n+m+1,d+1,n+m+1)\,,$ (37)

since each entry of $h_{\operatorname{FJ}}$ has degree at most $d+1\geq 2$.
Accordingly [12, Lemma 13] shows that $f$ is constant on each $Z_{i}$. Thus
$f(V(h_{\operatorname{FJ}}))$ is finite. Set
$r=|f(V(h_{\operatorname{FJ}}))|$. From (37), we get

$r\leq s\leq c(n+m+1,d+1,n+m+1)\,.$ (38)

Set

$u:=b(n+m+1,d+1,2m+n+3)/2\,.$ (39)

By using Lemma 4, there exist $q\in P_{\xi}(g)[x,\bar{\lambda}]$ with
$\xi=dr+u$ such that $f-q$ vanishes on $V(h_{\operatorname{FJ}})$. By (38) and
(35), we obtain $\xi\leq w$, and hence $q\in P_{w}(g)[x,\bar{\lambda}]$. ∎

######  Remark 1.

Here $h_{\operatorname{FJ}}$ includes polynomials from the Fritz John
conditions (5). In Theorem 1, if we assume further that the ideal generated by
$h_{\operatorname{FJ}}$ is real radical (see in [12]), then $f-q\in
I_{r}(h_{\operatorname{FJ}})$ for some $r\in{\mathbb{N}}$. However, this
further assumption does not play any role in this paper when we apply the
representation in Theorem 1 for polynomial optimization.

Our second main result is as follows:

######  Theorem 2.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\geq 1$. Assume that
$f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$ and $f(C(g)\cap
S(g))$ is finite. Set

$w:=d\times(c(n+m+1,d+1,n+2m+1)-1)\,.$ (40)

Then there exists $q\in\Sigma_{w}^{2}[x,\bar{\lambda}]$ such that $f-q$
vanishes on $(S(g)\times{\mathbb{R}}^{m+1})\cap V(h_{\operatorname{FJ}})$,
where $\bar{\lambda}:=(\lambda_{0},\dots,\lambda_{m})$ and
$h_{\operatorname{FJ}}$ is defined as in (36).

###### Proof.

Using Lemma 3, we decompose $(S(g)\times{\mathbb{R}}^{m+1})\cap
V(h_{\operatorname{FJ}})$ into semi-algebraically path connected components:
$Z_{1},\dots,Z_{s}$ with

$s\leq c(n+m+1,d+1,n+2m+1)\,,$ (41)

since each entry of $h_{\operatorname{FJ}}$ (resp. $g$) has degree at most
$d+1\geq 2$ (resp. $d$). Accordingly [12, Lemma 19] shows that $f$ is constant
on $Z_{i}$. Thus the set $f((S(g)\times{\mathbb{R}}^{m+1})\cap
V(h_{\operatorname{FJ}}))$ has $r$ elements and we get

$r\leq s\leq c(n+m+1,d+1,n+2m+1)\,.$ (42)

By using Lemma 6, there exist $q\in\Sigma^{2}_{\xi}[x,\bar{\lambda}]$ with
$\xi=d(r-1)$ such that $f-q$ vanishes on $(S(g)\times{\mathbb{R}}^{m+1})\cap
V(h_{\operatorname{FJ}})$. By (42) and (40), we obtain $\xi\leq w$, and hence
$q\in\Sigma^{2}_{w}[x,\bar{\lambda}]$. ∎

###  3.2 The case of nonnegative multipliers

We state the third main result in the following theorem:

######  Theorem 3.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\in{\mathbb{N}}$.
Assume that $f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$ and
$f(C^{+}(g))$ is finite. Set

$w:=\frac{1}{2}\times b(n+m+1,d+2,2m+n+3)+d\times{c(n+m+1,d+2,n+m+1)}\,.$ (43)

Then there exists $q\in P_{w}(g)[x,\bar{\lambda}]$ such that $f-q$ vanishes on
$V(h_{\operatorname{FJ}}^{+})$, where
$\bar{\lambda}:=(\lambda_{0},\dots,\lambda_{m})$ and

$h_{\operatorname{FJ}}^{+}:=(\lambda_{0}^{2}\nabla
f-\sum_{j=1}^{m}\lambda_{j}^{2}\nabla
g_{j},\lambda_{1}^{2}g_{1},\dots,\lambda_{m}^{2}g_{m},1-\sum_{j=0}^{m}\lambda_{j}^{2})\,.$
(44)

Here $h_{\operatorname{FJ}}^{+}$ includes polynomials in the right hand side
of the Fritz John conditions (5). The fourth main result is stated as follows:

######  Theorem 4.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\in{\mathbb{N}}$.
Assume that $f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$ and
$f(C^{+}(g)\cap S(g))$ is finite. Set

$w:=d\times(c(n+m+1,d+2,n+2m+1)-1)\,.$ (45)

Then there exists $q\in\Sigma_{w}[x,\bar{\lambda}]$ such that $f-q$ vanishes
on $S(g)\cap V(h_{\operatorname{FJ}}^{+})$, where
$\bar{\lambda}:=(\lambda_{0},\dots,\lambda_{m})$ and
$h_{\operatorname{FJ}}^{+}$ is defined as in (44).

To prove Theorem 3 (resp. Theorem 4), we do similarly to the proof of Theorem
1 (resp. Theorem 2) by replacing $C(g)$ and $h_{\operatorname{FJ}}$ with
$C^{+}(g)$ and $h_{\operatorname{FJ}}^{+}$, respectively. Note that each entry
of $h_{\operatorname{FJ}}^{+}$ has degree at most $d+2$.

######  Remark 2.

The two sets of critical points $C(g)$ and $C^{+}(g)$ include the set of
points $W(f,g)$ at which the Fritz John conditions hold but the
Karush–Kuhn–Tucker conditions do not hold for problem (1). The assumptions
that the images of $C(g)$ and $C^{+}(g)$ under $f$ are finite allow us to
obtain the representations of $f$ in the case of $W(f,g)\neq\emptyset$.

###  3.3 The case with denominators

We state the fifth main result in the following theorem, which does not
require any assumption on the set of critical points:

######  Theorem 5.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\geq 1$. Assume that
$f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$. Set

$w:=\frac{1}{2}\times b(n+m+1,d+1,2m+n+3)+2d\times{c(n+m+1,d+1,n+m+1)}\,.$
(46)

Then there exists $q\in P_{w}(g)[x,\bar{\lambda}]$ such that
$\lambda_{0}(f-q)$ vanishes on $V(h_{\operatorname{FJ}})$, where
$\bar{\lambda}:=(\lambda_{0},\dots,\lambda_{m})$ and $h_{\operatorname{FJ}}$
is defined as in (36).

###### Proof.

Using Lemma 3, we decompose
$V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\}$ into semi-
algebraically path connected components: $Z_{1},\dots,Z_{s}$ with

$s\leq 2\times c(n+m+1,d+1,n+m+1)\,.$ (47)

It is because each entry of $h_{\operatorname{FJ}}$ has degree at most
$d+1\geq 2$ and

$V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\}=(V(h_{\operatorname{FJ}})\cap\\{\lambda_{0}>0\\})\cup(V(h_{\operatorname{FJ}})\cap\\{\lambda_{0}<0\\})\,.$
(48)

Accordingly [12, Lemma 24] shows that $f$ is constant on each $Z_{i}$. Thus
$f(V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\})$ is finite. Set
$r=|f(V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\})|$. From (37), we
get

$r\leq s\leq 2\times c(n+m+1,d+1,n+m+1)\,.$ (49)

Set

$u:=b(n+m+1,d+1,2m+n+3)/2\,.$ (50)

By using Lemma 5, there exist $q\in P_{\xi}(g)[x,\bar{\lambda}]$ with
$\xi=dr+u$ such that $f-q$ vanishes on
$V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\}$. It implies that
$\lambda_{0}(f-q)$ vanishes on $V(h_{\operatorname{FJ}})$. By (49) and (46),
we obtain $\xi\leq w$, and hence $q\in P_{w}(g)[x,\bar{\lambda}]$. ∎

######  Remark 3.

We have provided the degree bounds for the representations involving
preorderings in Theorems 1, 2, 3, 4, and 5. Our bounds are extremely large
because of the exponential bounds for Krivine–Stengle’s
Nichtnegativstellensatz and the number of connected components of a basic
semi-algebraic set. Fortunately, our bounds only depend on the number of
variables, the number of polynomials defining the basic semi-algebraic set,
and the degrees of the input polynomials.

In contrast, our degree bound for the representations involving quadratic
modules in Theorems 15 and 17 stated below is implicit and depends on all
information (including the coefficients) of the input polynomials. To achieve
it, we apply the degree bound of Putinar’s Positivestellensatz analyzed by
Baldi–Mourrain [2] under the finiteness assumption for the image of the set of
critical points $C(g)$ under $f$.

##  4 Convergence rate for exact polynomial optimization based on the Fritz
John conditions

This section presents the main application of the degree bounds in Theorems 1,
2, 3, 4, and 5 to analyze the convergence rate of the corresponding
hierarchies of semidefinite relaxations for a polynomial optimization problem.

###  4.1 The case of arbitrary multipliers

######  Theorem 6.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$. Let $f^{\star}$ be as in
problem (1) with $g=(g_{1},\dots,g_{m})$. Assume that problem (1) has a global
minimizer and $f(C(g))$ is finite. Let $h_{\operatorname{FJ}}$ be as in (36)
and let $w$ be as in (46). Set

$r=b(n+m+1,2w,m+n+2)/2\,.$ (51)

Then $\rho_{r}(f,\Pi g,h_{\operatorname{FJ}})=f^{\star}$, where $\Pi g$ is
defined as in (11).

###### Proof.

Since $S(g)=S(\Pi g)$, [12, Lemma 17] implies that

$\begin{array}[]{rl}f^{\star}:=\min\limits_{x,\bar{\lambda}}&f(x)\\\
\text{s.t.}&x\in S(\Pi g)\,,\,(x,\bar{\lambda})\in
V(h_{\operatorname{FJ}})\,,\end{array}$ (52)

By assumption, Theorem 1 yields that there exists $q\in
P_{w}(g)[x,\bar{\lambda}]=Q_{w}(\Pi g)[x,\bar{\lambda}]$ such that
$f-f^{\star}-q$ vanishes on $V(h_{\operatorname{FJ}})$. Applying the sixth
statement of Lemma 7 (by replacing $g$ with $\Pi g$), we obtain the
conclusion. ∎

######  Theorem 7.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$. Let $f^{\star}$ be as in
problem (1) with $g=(g_{1},\dots,g_{m})$. Assume that problem (1) has a global
minimizer and $f(C(g)\cap S(g))$ is finite. Let $h_{\operatorname{FJ}}$ be as
in (36) and let $w$ be as in (40). Set $r$ as in (51). Then $\rho_{r}(f,\Pi
g,h_{\operatorname{FJ}})=f^{\star}$, where $\Pi g$ is defined as in (11).

###### Proof.

Note that [12, Lemma 17] implies that

$\begin{array}[]{rl}f^{\star}:=\min\limits_{x,\bar{\lambda}}&f(x)\\\
\text{s.t.}&x\in S(g)\,,\,(x,\bar{\lambda})\in
V(h_{\operatorname{FJ}})\,,\end{array}$ (53)

By assumption, Theorem 2 yields that there exists
$q\in\Sigma^{2}_{w}[x,\bar{\lambda}]$ such that $f-f^{\star}-q$ vanishes on
$(S(g)\cap{\mathbb{R}}^{m+1})\times V(h_{\operatorname{FJ}})$. Applying the
final statement of Lemma 7, we obtain the conclusion. ∎

###  4.2 The case of nonnegative multipliers

######  Theorem 8.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$. Let $f^{\star}$ be as in
problem (1) with $g=(g_{1},\dots,g_{m})$. Assume that problem (1) has a global
minimizer and $f(C^{+}(g))$ is finite. Let $h_{\operatorname{FJ}}^{+}$ be as
in (36) and let $w$ be as in (43). Set $r$ as in (51). Then $\rho_{r}(f,\Pi
g,h_{\operatorname{FJ}})=f^{\star}$, where $\Pi g$ is defined as in (11).

The proof of Theorem 8, which is based on Theorem 3, is similar to the one of
Theorem 6.

######  Theorem 9.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$. Let $f^{\star}$ be as in
problem (1) with $g=(g_{1},\dots,g_{m})$. Assume that problem (1) has a global
minimizer and $f(C^{+}(g)\cap S(g))$ is finite. Let
$h_{\operatorname{FJ}}^{+}$ be as in (36) and let $w$ be as in (45). Set $r$
as in (51). Then $\rho_{r}(f,\Pi g,h_{\operatorname{FJ}})=f^{\star}$, where
$\Pi g$ is defined as in (11).

The proof of Theorem 9 based on Theorem 4 is similar to the one of Theorem 7.

######  Remark 4.

It is worth pointing out in Theorems 6, 7, 8, and 9 that the order
$r\in{\mathbb{N}}$ satisfying $\rho_{r}(f,\Pi
g,h_{\operatorname{FJ}})=f^{\star}$ depends on $n$ (the number of variables),
$m$ (the number of inequality constraints $g_{j}$), and $d$ (the upper bound
on the degrees of $f,g_{j}$) but does not depend on the coefficients of
$f,g_{j}$.

######  Remark 5.

Under the Archimedean condition (resp. the compactness assumption) for $S(g)$,
the sequence $(\rho_{k}(f,g,h_{\operatorname{FJ}}))_{k\in{\mathbb{N}}}$ (resp.
$(\rho_{k}(f,\Pi g,h_{\operatorname{FJ}}))_{k\in{\mathbb{N}}}$) converges to
$f^{\star}$ faster than the sequence $(\rho_{k}(f,g,0))_{k\in{\mathbb{N}}}$
(resp. $(\rho_{k}(f,\Pi g,0))_{k\in{\mathbb{N}}}$). It is because of the
following inequalities:

$\rho_{k}(f,g,0)\leq\rho_{k}(f,g,h_{\operatorname{FJ}})\leq
f^{\star}\quad\quad(\text{resp. }\rho_{k}(f,\Pi g,0)\leq\rho_{k}(f,\Pi
g,h_{\operatorname{FJ}})\leq f^{\star})\,.$ (54)

Thus we can obtain the convergence rate for
$(\rho_{k}(f,g,h_{\operatorname{FJ}}))_{k\in{\mathbb{N}}}$ (resp.
$(\rho_{k}(f,\Pi g,h_{\operatorname{FJ}}))_{k\in{\mathbb{N}}}$) from the
available convergence rate of $(\rho_{k}(f,g,0))_{k\in{\mathbb{N}}}$ (resp.
$(\rho_{k}(f,\Pi g,0))_{k\in{\mathbb{N}}}$) in [6, 10, 27, 2]. However, these
rates do not give the finite convergence for the sequence
$(\rho_{k}(f,g,h_{\operatorname{FJ}}))_{k\in{\mathbb{N}}}$ (resp.
$(\rho_{k}(f,\Pi g,h_{\operatorname{FJ}}))_{k\in{\mathbb{N}}}$). Moreover, the
computational complexity for the semidefinite relaxation of each value
$\rho_{k}(f,g,h_{\operatorname{FJ}})$ (resp. $\rho_{k}(f,\Pi
g,h_{\operatorname{FJ}})$) grows more quickly than the one of the value
$\rho_{k}(f,g,0)$ (resp. $\rho_{k}(f,\Pi g,0)$) as $k$ increases. It is
because to obtain the relaxation of the value
$\rho_{k}(f,g,h_{\operatorname{FJ}})$ (resp. $\rho_{k}(f,\Pi
g,h_{\operatorname{FJ}})$), we utilize $m+1$ additional variables and $n+m+1$
additional equality constraints to the original polynomial optimization
problem (1).

###  4.3 The case with denominators

######  Theorem 10.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$. Let $f^{\star}$ be as in
problem (1) with $g=(g_{1},\dots,g_{m})$. Let $h_{\operatorname{FJ}}$ be as in
(36) and let $w$ be as in (46). Assume that problem (1) has global minimizer
and one of the following two conditions holds:

  1. 1.

the Karush–Kuhn–Tucker conditions hold for problem (1) at $x^{\star}$;

  2. 2.

there exists a sequence of points
$(x^{(t)},\bar{\lambda}^{(t)})_{t\in{\mathbb{N}}}$ in
$(S(g)\times{\mathbb{R}}^{m+1})\cap V(h_{\operatorname{FJ}})$ such that
$(f(x^{(t)}))_{t\in{\mathbb{N}}}$ converges to $\bar{f}^{\star}$ and
$\lambda_{0}^{(t)}>0$,

Set

$r=b(n+m+1,2(w+1),m+n+2)/2\,.$ (55)

Then $\rho_{r}(f,\Pi g,h_{\operatorname{FJ}},\lambda_{0})=f^{\star}$, where
$\Pi g$ is defined as in (11).

###### Proof.

Since $S(g)=S(\Pi g)$, [12, Lemma 17] implies (52). Note that the first
condition implies that the Fritz John conditions hold for problem (1) at
$x^{\star}$ with multipliers $\bar{\lambda}^{\star}$ such that
$\lambda_{0}^{\star}>0$, so that $(x^{\star},\bar{\lambda}^{\star})$ is a
global minimizer for problem (52) with $\lambda_{0}^{\star}>0$. The second
condition implies that each $(x^{(t)},\bar{\lambda}^{(t)})$ is a feasible
solution for problem (52) such that $(f(x^{(t)}))_{t\in{\mathbb{N}}}$
converges to $\bar{f}^{\star}$ and $\lambda_{0}^{(t)}>0$. The third statement
of Lemma 8 says that $\rho_{k}(f,\Pi g,h_{\operatorname{FJ}},\lambda_{0})\leq
f^{\star}$, for every $k\in{\mathbb{N}}$. In addition, Theorem 5 yields that
there exists $q\in P_{w}(g)[x,\bar{\lambda}]=Q_{w}(\Pi g)[x,\bar{\lambda}]$
such that $\lambda_{0}(f-f^{\star}-q)$ vanishes on $V(h_{\operatorname{FJ}})$.
Applying the final statement of Lemma 8 (by replacing $g,h,\theta$ with $\Pi
g,h_{\operatorname{FJ}},\lambda_{0}$), we obtain the conclusion. ∎

######  Remark 6.

As shown by Freund in [7], the Karush–Kuhn–Tucker conditions hold for problem
(1) at its global minimizers if one of the following conditions holds:

  1. 1.

$g$ can be decomposed as $g=(g^{(1)},g^{(2)},-g^{(2)})$, $S(g^{(1)})$ has non-
empty interior, and $g_{j}$, $j=1,\dots,m$, are concave;

  2. 2.

$g_{j}$, $j=1,\dots,m$, are linear;

  3. 3.

$f$ is a pseudoconvex and $g_{j}$, $j=1,\dots,m$, are quasiconcave (see the
definitions of pseudoconvexity and quasiconcavity in [7]).

Thanks to Theorem 10 (as well as Theorems 12, 14, and 18 stated below), we can
compute the exact optimal value $f^{\star}$ for problem (1) by using
semidefinite programming under one of the above three conditions.

##  5 Explicit degree bounds for the representation based on the
Karush–Kuhn–Tucker conditions

###  5.1 The case of arbitrary multipliers

We prove the following lemma similar to [5, Lemma 3.3] by using the tools from
real algebraic geometry (instead of the ones from complex algebraic geometry):

######  Lemma 9.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$. Set

$h_{\operatorname{KKT}}:=(\nabla f-\sum_{j=1}^{m}\lambda_{j}\nabla
g_{j},\lambda_{1}g_{1},\dots,\lambda_{m}g_{m})\,.$ (56)

Let $W$ be a semi-algebraically path connected component of
$V(h_{\operatorname{KKT}})$. Then $f$ is constant on $W$.

###### Proof.

Recall $\lambda:=(\lambda_{1},\dots,\lambda_{m})$. Choose two arbitrary points
$(x^{(0)},\lambda^{(0)})$, $(x^{(1)},\lambda^{(1)})$ in $W$. We claim that
$f(x^{(0)})=f(x^{(1)})$.

It is sufficient to assume that both $(x^{(0)},\lambda^{(0)})$ and
$(x^{(1)},\lambda^{(1)})$ are non-singular points. If at least one of
$(x^{(0)},\lambda^{(0)})$ and $(x^{(1)},\lambda^{(1)})$ is singular, we choose
arbitrarily close non-singular points to approximate $(x^{(0)},\lambda^{(0)})$
and $(x^{(1)},\lambda^{(1)})$ then we apply the continuity of $f$ to obtain
$f(x^{(0)})=f(x^{(1)})$. It is because the set of non-singular points of $W$
is dense and open in $W$.

If a manifold is path-connected, the set of its non-singular points is a
manifold that is also path-connected. By assumption, there exists a continuous
piecewise-differentiable path $\phi(\tau)=(x(\tau),\lambda(\tau))$, for
$\tau\in[0,1]$, lying inside $W$ such that $\phi(0)=(x^{(0)},\lambda^{(0)})$
and $\phi(1)=(x^{(1)},\lambda^{(1)})$. We claim that $\tau\mapsto f(x(\tau))$
is constant on $[0,1]$. The Lagrangian function

$L(x,\lambda)=f(x)+\sum_{j=1}^{m}\lambda_{j}g_{j}(x)\,.$ (57)

is equal to $f(x)$ on $V(h_{\operatorname{KKT}})$, which contains
$\phi([0,1])$. Let $\mu_{j}(\tau)$ be the principal square root of
$\lambda_{j}(\tau)$ for $\tau\in[0,1]$, $j=1,\dots,m$. By the mean value
theorem, it follows that $f(x(0))=f(x(1))$. We now obtain $f(x^{(0)})$ =
$f(x^{(1)})$ and hence $f$ is constant on $W$. ∎

We state in the following theorem the explicit degree bound for the
representation based on the Karush–Kuhn–Tucker conditions:

######  Theorem 11.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\geq 1$. Assume that
$f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$. Set

$w:=\frac{1}{2}\times b(n+m,d+1,2m+n+1)+d\times{c(n+m,d+1,n+m)}\,.$ (58)

Then there exists $q\in P_{w}(g)[x,\lambda]$ such that $f-q$ vanishes on
$V(h_{\operatorname{KKT}})$, where $\lambda:=(\lambda_{1},\dots,\lambda_{m})$
and $h_{\operatorname{KKT}}$ is defined as in (56).

###### Proof.

Using Lemma 3, we decompose $V(h_{\operatorname{KKT}})$ into semi-
algebraically path connected components: $Z_{1},\dots,Z_{s}$ with

$s\leq c(n+m,d+1,n+m)\,,$ (59)

since each entry of $h_{\operatorname{KKT}}$ has degree at most $d+1\geq 2$.
Accordingly Lemma 9 shows that $f$ is constant on each $Z_{i}$. Thus
$f(V(h_{\operatorname{KKT}}))$ is finite. Set
$r=|f(V(h_{\operatorname{KKT}}))|$. From (59), we get

$r\leq s\leq c(n+m,d+1,n+m)\,.$ (60)

Set

$u:=b(n+m,d+1,2m+n+1)/2\,.$ (61)

By using Lemma 4, there exists $q\in P_{\xi}(g)[x,\lambda]$ with $\xi=dr+u$
such that $f-q$ vanishes on $V(h_{\operatorname{KKT}})$. By (60) and (58),
$\xi\leq w$, and hence $q\in P_{w}(g)[x,\lambda]$. ∎

We apply Theorem 11 for polynomial optimization as follows:

######  Theorem 12.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$. Let $f^{\star}$ be as in
problem (1) with $g=(g_{1},\dots,g_{m})$. Assume that problem (1) has a global
minimizer at which the Karush–Kuhn–Tucker conditions hold for this problem.
Let $h_{\operatorname{KKT}}$ be as in (56) and let $w$ be as in (58). Set

$r=b(n+m,2w,m+n+1)/2\,.$ (62)

Then $\rho_{r}(f,\Pi g,h_{\operatorname{KKT}})=f^{\star}$, where $\Pi g$ is
defined as in (11).

###### Proof.

By assumption, there exists $(x^{\star},\lambda^{\star})\in
V(h_{\operatorname{KKT}})$ such that $x^{\star}$ is a global minimizer of (1).
Since $S(g)=S(\Pi g)$, it implies that

$\begin{array}[]{rl}f^{\star}:=\min\limits_{x,\lambda}&f(x)\\\
\text{s.t.}&x\in S(\Pi g)\,,\,(x,\lambda)\in
V(h_{\operatorname{KKT}})\,,\end{array}$ (63)

By assumption, Theorem 11 yields that there exists $q\in
P_{w}(g)[x,\lambda]=Q_{w}(\Pi g)[x,\lambda]$ such that $f-f^{\star}-q$
vanishes on $V(h_{\operatorname{KKT}})$. Applying the sixth statement of Lemma
7 (by replacing $g$ with $\Pi g$), we obtain the conclusion. ∎

###  5.2 The case of nonnegative multipliers

A similar proof to one of Lemma 9 applies to the following lemma:

######  Lemma 10.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$. Set

$h_{\operatorname{KKT}}^{+}:=(\nabla f-\sum_{j=1}^{m}\lambda_{j}^{2}\nabla
g_{j},\lambda_{1}^{2}g_{1},\dots,\lambda_{m}^{2}g_{m})\,.$ (64)

Let $W$ be a semi-algebraically path connected component of
$V(h_{\operatorname{KKT}}^{+})$. Then $f$ is constant on $W$.

We state in the following theorem the explicit degree bound for the
representation based on the Karush–Kuhn–Tucker conditions:

######  Theorem 13.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\in{\mathbb{N}}$.
Assume that $f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$. Set

$w:=\frac{1}{2}\times b(n+m,d+1,2m+n+1)+d\times{c(n+m,d+2,n+m)}\,.$ (65)

Then there exists $q\in P_{w}(g)[x,\lambda]$ such that $f-q$ vanishes on
$V(h_{\operatorname{KKT}}^{+})$, where
$\lambda:=(\lambda_{1},\dots,\lambda_{m})$ and $h_{\operatorname{KKT}}$ is
defined as in (64).

###### Proof.

Using Lemma 3, we decompose $V(h_{\operatorname{KKT}}^{+})$ into semi-
algebraically path connected components: $Z_{1},\dots,Z_{s}$ with

$s\leq c(n+m,d+2,n+m)\,,$ (66)

since each entry of $h_{\operatorname{KKT}}^{+}$ has degree at most $d+2\geq
2$. Accordingly Lemma 10 shows that $f$ is constant on each $Z_{i}$. Thus
$f(V(h_{\operatorname{KKT}}^{+}))$ is finite. Set
$r=|f(V(h_{\operatorname{KKT}}^{+}))|$. From (59), we get

$r\leq s\leq c(n+m,d+2,n+m)\,.$ (67)

Set

$u:=b(n+m,d+1,2m+n+1)/2\,.$ (68)

By using Lemma 4, there exists $q\in P_{\xi}(g)[x,\lambda]$ with $\xi=dr+u$
such that $f-q$ vanishes on $V(h_{\operatorname{KKT}}^{+})$. By (67) and (65),
$\xi\leq w$, and hence $q\in P_{w}(g)[x,\lambda]$. ∎

We apply Theorem 13 for polynomial optimization as follows:

######  Theorem 14.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$. Let $f^{\star}$ be as in
problem (1) with $g=(g_{1},\dots,g_{m})$. Assume that problem (1) has a global
minimizer at which the Karush–Kuhn–Tucker conditions hold for this problem.
Let $h_{\operatorname{KKT}}^{+}$ be as in (64) and let $w$ be as in (65). Set

$r=b(n+m+1,2w,m+n+2)/2\,.$ (69)

Then $\rho_{r}(f,\Pi g,h_{\operatorname{KKT}}^{+})=f^{\star}$, where $\Pi g$
is defined as in (11).

###### Proof.

By assumption, there exists $(x^{\star},\lambda^{\star})\in
V(h_{\operatorname{KKT}}^{+})$ such that $x^{\star}$ is a global minimizer of
(1). Since $S(g)=S(\Pi g)$, it implies that

$\begin{array}[]{rl}f^{\star}:=\min\limits_{x,\bar{\lambda}}&f(x)\\\
\text{s.t.}&x\in S(\Pi g)\,,\,(x,\lambda)\in
V(h_{\operatorname{KKT}}^{+})\,,\end{array}$ (70)

By assumption, Theorem 13 yields that there exists $q\in
P_{w}(g)[x,\lambda]=Q_{w}(\Pi g)[x,\lambda]$ such that $f-f^{\star}-q$
vanishes on $V(h_{\operatorname{KKT}}^{+})$. Applying the sixth statement of
Lemma 7 (by replacing $g$ with $\Pi g$), we obtain the conclusion. ∎

##  6 Implicit degree bounds for the representations involving quadratic
modules

Let $\|\cdot\|$ denote the max norm of a polynomial on $[-1,1]^{n}$. We recall
in the following lemma the degree bound for Putinar’s Positivstellensatz by
Baldi and Mourain in [2]:

######  Lemma 11.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$. Assume that $f$ is positive on
$S(g)$ with $g:=(g_{1},\dots,g_{m})$ and the following conditions:

  1. 1.

$1-x_{1}^{2}-\dots-x_{n}^{2}\in Q_{d}(g)[x]$ for some $d\in{\mathbb{N}}$;

  2. 2.

$\|g_{i}\|\leq\frac{1}{2}\,,\,i=1,\dots,m$.

Let $f^{\star}$ be as in (1). Then there exist positive reals $\gamma(n,g)$
and $L(n,g)$ depending only on $n$ and $g$ such that $f\in Q_{r}(g)[x]$ if

$r\geq\gamma(n,g)\deg(f)^{3.5nL(n,g)}\left(\frac{\|f\|}{f^{\star}}\right)^{2.5nL(n,g)}\,.$
(71)

We denote by $v(n,f,g)$ the ceiling of the right hand side of (71). Given
$p\in{\mathbb{R}}[x]$ with $\xi=\lceil\deg(p)/2\rceil$, let
$\tilde{p}:=x_{0}^{2\xi}p(\frac{x}{x_{0}\sqrt{2}})\in{\mathbb{R}}[\bar{x}]$,
where $\bar{x}:=(x_{0},x)$. The following lemma is a consequence of Lemmas 1
and 11:

######  Lemma 12.

Let $g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$. Assume that the following
conditions hold:

  1. 1.

$\|\tilde{g}_{i}\|\leq\frac{1}{2}\,,\,i=1,\dots,m$,
$g_{m}:=\frac{1}{2}-x_{1}^{2}-\dots-x_{n}^{2}$;

  2. 2.

$S(g)=\emptyset$ with $g:=(g_{1},\dots,g_{m})$.

Then there exists a positive real $u$ depending on $n$ and $g$ such that
$-1\in Q_{u}(g)[x]$.

Denote by $u(n,d,g)$ the parameter $u$ in Lemma 12.

###### Proof.

Set $\eta=b(n,d,m+1)/2$. Since $S(g)=\emptyset$, Lemma 1 yields that there
exists $\sigma_{\alpha}\in\Sigma^{2}[x]$ such that
$\deg(\sigma_{\alpha}g^{\alpha})\leq 2\eta$ and

$-1=\sum_{\alpha\in\\{0,1\\}^{n}}\sigma_{\alpha}g^{\alpha}\,.$ (72)

We have $\tilde{g}_{m}=\frac{1}{2}x_{0}^{2}-x_{1}^{2}-\dots-x_{n}^{2}$. Let
$\eta_{j}=\lceil\deg(g_{j})/2\rceil$. From (72), we get

$-x_{0}^{2\eta}=\sum_{\alpha\in\\{0,1\\}^{n}}\psi_{\alpha}\tilde{g}^{\alpha}\,,$
(73)

where
$\psi_{\alpha}=x_{0}^{2(\eta-\eta_{j})}\sigma_{\alpha}(\frac{x}{x_{0}\sqrt{2}})\in\Sigma^{2}[\bar{x}]$
and $\tilde{g}=(\tilde{g}_{1},\dots,\tilde{g}_{m})$. Denote by
$w\in{\mathbb{R}}[\bar{x}]$ the polynomial on the right hand side of (73).
Then $w$ is non-negative on $S(\tilde{g},\frac{1}{2}-x_{0}^{2})$. Since $0\in
S(\tilde{g},\frac{1}{2}-x_{0}^{2})$, we get
$S(\tilde{g},\frac{1}{2}-x_{0}^{2})\neq\emptyset$. On the other hand we have

$1-x_{0}^{2}-\dots-x_{n}^{2}=(\frac{1}{2}-x_{0}^{2})+\tilde{g}_{m}\in
Q(\tilde{g},\frac{1}{2}-x_{0}^{2})[\bar{x}]\,.$ (74)

Applying Lemma 11, we obtain
$u=v(n,w+\frac{1}{2^{\eta+1}},(\tilde{g},\frac{1}{2}-x_{0}^{2}))$ such that

$-x_{0}^{2\eta}+\frac{1}{2^{\eta+1}}=w+\frac{1}{2^{\eta+1}}\in
Q_{u}(\tilde{g},\frac{1}{2}-x_{0}^{2})[\bar{x}]\,.$ (75)

Letting $x_{0}=\frac{1}{\sqrt{2}}$ implies that $-\frac{1}{2^{\eta+1}}\in
Q_{u}(g)[x]$, yielding the result. ∎

The following lemma is a direct consequence of Lemma 12:

######  Lemma 13.

Let $g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ and
$h_{1},\dots,h_{l}\in{\mathbb{R}}_{d+1}[x]$. Assume that the following
conditions hold:

  1. 1.

$\|\tilde{g}_{i}\|\leq\frac{1}{2}\,,\,i=1,\dots,m$,
$g_{m}:=\frac{1}{2}-x_{1}^{2}-\dots-x_{n}^{2}$;

  2. 2.

$S(g)\cap V(h)=\emptyset$ with $g:=(g_{1},\dots,g_{m})$ and
$h:=(h_{1},\dots,h_{l})$.

Set $h_{\max}:=\max\limits_{j=1,\dots,l}\|\tilde{h}_{j}\|$. Then there exists
a positive real

$w=u(n,d+1,(g,\frac{h}{2h_{\max}},-\frac{h}{2h_{\max}}))$ (76)

depending on $n$ and $g$ such that $-1\in Q_{w}(g)[x]$.

Denote by $w(n,d,g,h)$ the parameter $w$ in Lemma 13.

###  6.1 The case without denominators

######  Lemma 14.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ and
$h_{1},\dots,h_{l}\in{\mathbb{R}}_{d+1}[x]$. Assume that the following
conditions hold:

  1. 1.

$\|\tilde{g}_{i}\|\leq\frac{1}{2}$, $i=1,\dots,m$,
$g_{m}:=\frac{1}{2}-x_{1}^{2}-\dots-x_{n}^{2}$;

  2. 2.

$f$ is non-negative on $S(g)$ with $g=(g_{1},\dots,g_{m})$;

  3. 3.

$f(V(h))$ is finite with $h=(h_{1},\dots,h_{l})$.

Set $r:=|f(V(h))|$ and

$u:=\max_{t\in f(V(h))}w(n,d,g,(h,f-t))\,.$ (77)

Then there exist $q\in Q_{t}(g)[x,\bar{\lambda}]$ with $t=dr+u$ such that
$f-q$ vanishes on $V(h)$.

Denote by $t(n,d,r,f,g,h)$ the parameter $t$ in Lemma 14. Note that it holds
that

$t(n,d,r,f,g,h)\leq t(n,d,r^{\prime},f,g,h)\text{ if }r\leq r^{\prime}\,.$
(78)

###### Proof.

By assumption, we get $f(V(h))=\\{t_{1},\dots,t_{r}\\}\subset{\mathbb{R}}$,
where $t_{i}\neq t_{j}$ if $i\neq j$. For $j=1,\dots,r$, let
$W_{j}:=V(h,f-t_{j})$. Then $W_{j}$ is a real variety generated by $l+1$
polynomials in ${\mathbb{R}}_{d+1}[x]$. It is clear that
$f(W_{j})=\\{t_{j}\\}$.

Let $p_{j}\in{\mathbb{R}}[x]$, $j=1,\dots,r$, as in (18). It is easy to check
that $p_{j}(W_{i})=\\{\delta_{ji}\\}$ and $\deg(p_{j})\leq d(r-1)$. Without
loss of generality, we assume that there is $s\in\\{0,1,\dots,r-1\\}$ such
that $W_{j}\cap S(g)=\emptyset$, for $j=1,\dots,s$, and $W_{i}\cap
S(g)\neq\emptyset$, for $i=s+1,\dots,r$.

Let $j\in\\{1,\dots,s\\}$. Since $W_{j}\cap S(g)=\emptyset$, Theorem 12 says
that $-1\in Q_{u}(g)[x]+I_{u}(h,f-t_{j})[x]$. It implies that there exists
$v_{j}\in Q_{u}(g)[x]$ such that $-1=v_{j}$ on $W_{j}$. We have
$f=s_{1}-s_{2}$ for the SOS polynomials $s_{1}=(f+\frac{1}{2})^{2}$ and
$s_{2}=f^{2}+\frac{1}{4}$. It implies that $f=s_{1}+v_{j}s_{2}$ on $W_{j}$.
Let $q_{j}=s_{1}+v_{j}s_{2}\in Q_{u+d}(g)[x,\bar{\lambda}]$.

Since $f\geq 0$ on $S(g)$, it holds that $f=t_{i}\geq 0$ on $W_{i}$, for
$i=s+1,\dots,r$. Now letting $q$ as in (19), we obtain $q\in Q_{t}(g)[x]$, and
hence $f-q$ vanishes on $V(h)=W_{1}\cup\dots\cup W_{r}$. ∎

The implicit degree bound for the representation without denominators
associated with quadratic module in [12, Theorem 1] is stated in the following
theorem:

######  Theorem 15.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\geq 1$. Assume that
the following conditions hold:

  1. 1.

$\|\tilde{g}_{i}\|\leq\frac{1}{2}$, $i=1,\dots,m$ and
$g_{m}:=\frac{1}{2}-x_{1}^{2}-\dots-x_{n}^{2}$;

  2. 2.

$f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$ and $f(C(g))$ is
finite.

Set

$\omega:=t(n,d,c(n+m+1,d+1,n+m+1),f,g,h_{\operatorname{FJ}})\,.$ (79)

Then there exists $q\in Q_{\omega}(g)[x,\bar{\lambda}]$ such that $f-q$
vanishes on $V(h_{\operatorname{FJ}})$, where
$\bar{\lambda}:=(\lambda_{0},\dots,\lambda_{m})$ and $h_{\operatorname{FJ}}$
is defined as in (36).

###### Proof.

Using Lemma 3, we decompose $V(h_{\operatorname{FJ}})$ into semi-algebraically
path connected components: $Z_{1},\dots,Z_{s}$ with $s$ satisfying (37) (since
each entry of $h_{\operatorname{FJ}}$ has degree at most $d+1\geq 2$).
Accordingly, [12, Lemma 13] says that $f$ is constant on each $Z_{i}$. Thus
$f(V(h_{\operatorname{FJ}}))$ is finite. Set
$r=|f(V(h_{\operatorname{FJ}}))|$. Then we get the inequality (38). By using
Lemma 14, there exist $q\in Q_{\xi}(g)[x,\bar{\lambda}]$ with
$\xi=t(n,d,r,f,g,h_{\operatorname{FJ}})$ such that $f-q$ vanishes on
$V(h_{\operatorname{FJ}})$. By (38), (78) and (79), $\xi\leq\omega$, and hence
$q\in Q_{\omega}(g)[x,\bar{\lambda}]$. This completes the proof. ∎

We apply Theorem 15 for polynomial optimization as follows:

######  Theorem 16.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\geq 1$. Let
$f^{\star}$ be as in problem (1) with $g=(g_{1},\dots,g_{m})$. Assume that the
following conditions hold:

  1. 1.

$\|\tilde{g}_{i}\|\leq\frac{1}{2}$, $i=1,\dots,m$ and
$g_{m}:=\frac{1}{2}-x_{1}^{2}-\dots-x_{n}^{2}$;

  2. 2.

problem (1) has a global minimizer and $f(C(g))$ is finite.

Let $h_{\operatorname{FJ}}$ be as in (36) and let $\omega$ be as in (79). Set

$r=b(n+m+1,2\omega,m+n+2)/2\,.$ (80)

Then $\rho_{r}(f,g,h_{\operatorname{FJ}})=f^{\star}$.

###### Proof.

Note that [12, Lemma 17] implies (53). By assumption, Theorem 15 yields that
there exists $q\in Q_{\omega}(g)[x,\bar{\lambda}]$ such that $f-f^{\star}-q$
vanishes on $V(h_{\operatorname{FJ}})$. Applying the sixth statement of Lemma
7, we obtain the conclusion. ∎

######  Remark 7.

The degree bound $\omega$ in Theorem 15 is not very interesting, and so is the
rate $r$ in Theorem 16. It is because the bound $\omega$ in Theorem 15 depends
on all information of $f,g_{j}$. Contrary to this, the degree bound $w$ in
Theorem 1 only depends on $n$ (the number of variables), $m$ (the number of
polynomial inequalities $g_{j}$), and $d$ (the upper bound on the degree of
$f,g_{j}$). We conclude similarly to other representations without
denominators involving quadratic modules in [12].

###  6.2 The case with denominators

######  Lemma 15.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ and
$h_{1},\dots,h_{l}\in{\mathbb{R}}_{d+1}[x]$. Assume that the following
conditions hold:

  1. 1.

$\|\tilde{g}_{i}\|\leq\frac{1}{2}$, $i=1,\dots,m$,
$g_{m}:=\frac{1}{2}-x_{1}^{2}-\dots-x_{n}^{2}$;

  2. 2.

$f$ is non-negative on $S(g)$ with $g=(g_{1},\dots,g_{m})$;

  3. 3.

$f(V(h)\backslash A)$ is finite with $h=(h_{1},\dots,h_{l})$ and
$A\subset{\mathbb{R}}^{n}$.

Set $r:=|f(V(h)\backslash A)|$ and

$u:=\max_{t\in f(V(h)\backslash A)}w(n,d,g,(h,f-t))\,.$ (81)

Then there exist $q\in Q_{t}(g)[x,\bar{\lambda}]$ with $t=dr+u$ such that
$f-q$ vanishes on $V(h)\backslash A$.

Denote by $t^{\prime}(n,d,r,f,g,h)$ the parameter $t$ in Lemma 15. Note that
it holds that

$t^{\prime}(n,d,r,f,g,h)\leq t^{\prime}(n,d,r^{\prime},f,g,h)\text{ if }r\leq
r^{\prime}\,.$ (82)

###### Proof.

By assumption, we get $f(V(h)\backslash
A)=\\{t_{1},\dots,t_{r}\\}\subset{\mathbb{R}}$, where $t_{i}\neq t_{j}$ if
$i\neq j$. We now handle in much the same way as the proof of Lemma 14 to get
$q\in Q_{t}(g)[x]$, and hence $f-q$ vanishes on $V(h)\backslash A\subset
W_{1}\cup\dots\cup W_{r}$. ∎

In the following theorem, we state the implicit degree bound for the
representation with denominators associated with quadratic modules in [12,
Theorem 9]:

######  Theorem 17.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\geq 1$. Assume that
the following conditions hold:

  1. 1.

$\|\tilde{g}_{i}\|\leq\frac{1}{2}$, $i=1,\dots,m$ and
$g_{m}:=\frac{1}{2}-x_{1}^{2}-\dots-x_{n}^{2}$;

  2. 2.

$f$ is non-negative on $S(g)$ with $g:=(g_{1},\dots,g_{m})$.

Set

$\omega:=t^{\prime}(n,d,2\times
c(n+m+1,d+1,n+m+1),f,g,h_{\operatorname{FJ}})\,.$ (83)

Then there exists $q\in Q_{\omega}(g)[x,\bar{\lambda}]$ such that
$\lambda_{0}(f-q)$ vanishes on $V(h_{\operatorname{FJ}})$, where
$\bar{\lambda}:=(\lambda_{0},\dots,\lambda_{m})$ and $h_{\operatorname{FJ}}$
is defined as in (36).

###### Proof.

Using Lemma 3, we decompose
$V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\}$ into semi-
algebraically path connected components: $Z_{1},\dots,Z_{s}$ with $s$
satisfying (47) (since each entry of $h_{\operatorname{FJ}}$ has degree at
most $d+1\geq 2$). Accordingly, [12, Lemma 24] says that $f$ is constant on
each $Z_{i}$. Thus $f(V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\})$
is finite. Set $r=|f(V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\})|$.
Then we get the inequality (49). By using Lemma 15, there exist $q\in
Q_{\xi}(g)[x,\bar{\lambda}]$ with
$\xi=t^{\prime}(n,d,r,f,g,h_{\operatorname{FJ}})$ such that $f-q$ vanishes on
$V(h_{\operatorname{FJ}})\backslash\\{\lambda_{0}=0\\}$. It implies that
$\lambda_{0}(f-q)$ vanishes on $V(h_{\operatorname{FJ}})$. By (49), (82) and
(83), $\xi\leq\omega$, and hence $q\in Q_{\omega}(g)[x,\bar{\lambda}]$. This
completes the proof. ∎

We apply Theorem 17 for polynomial optimization as follows:

######  Theorem 18.

Let $f,g_{1},\dots,g_{m}\in{\mathbb{R}}_{d}[x]$ with $d\geq 1$. Let
$f^{\star}$ be as in problem (1) with $g=(g_{1},\dots,g_{m})$. Assume that the
following conditions hold:

  1. 1.

$\|\tilde{g}_{i}\|\leq\frac{1}{2}$, $i=1,\dots,m$ and
$g_{m}:=\frac{1}{2}-x_{1}^{2}-\dots-x_{n}^{2}$;

  2. 2.

problem (1) has a global minimizer $x^{\star}$.

Let $h_{\operatorname{FJ}}$ be as in (36) and let $\omega$ be as in (83).
Assume that one of the following two conditions holds:

  1. 1.

the Karush–Kuhn–Tucker conditions hold for problem (1) at $x^{\star}$;

  2. 2.

there exists a sequence of points
$(x^{(t)},\bar{\lambda}^{(t)})_{t\in{\mathbb{N}}}$ in
$(S(g)\times{\mathbb{R}}^{m+1})\cap V(h_{\operatorname{FJ}})$ such that
$(f(x^{(t)}))_{t\in{\mathbb{N}}}$ converges to $\bar{f}^{\star}$ and
$\lambda_{0}^{(t)}>0$,

Set

$r=b(n+m+1,2(\omega+1),m+n+2)/2\,.$ (84)

Then $\rho_{r}(f,g,h_{\operatorname{FJ}},\lambda_{0})=f^{\star}$.

###### Proof.

Note that [12, Lemma 17] implies (53). Note that the first condition implies
that the Fritz John conditions hold for problem (1) at $x^{\star}$ with
multipliers $\bar{\lambda}^{\star}$ such that $\lambda_{0}^{\star}>0$, so that
$(x^{\star},\bar{\lambda}^{\star})$ is a global minimizer for problem (53)
with $\lambda_{0}^{\star}>0$. The second condition implies that each
$(x^{(t)},\bar{\lambda}^{(t)})$ is a feasible solution for problem (53) such
that $(f(x^{(t)}))_{t\in{\mathbb{N}}}$ converges to $\bar{f}^{\star}$ and
$\lambda_{0}^{(t)}>0$. The third statement of Lemma 8 says that
$\rho_{k}(f,g,h_{\operatorname{FJ}},\lambda_{0})\leq f^{\star}$, for every
$k\in{\mathbb{N}}$. In addition, Theorem 17 yields that there exists $q\in
Q_{\omega}(\Pi g)[x,\bar{\lambda}]$ such that $\lambda_{0}(f-f^{\star}-q)$
vanishes on $V(h_{\operatorname{FJ}})$. Applying the final statement of Lemma
8 (by replacing $h,\theta$ with $h_{\operatorname{FJ}},\lambda_{0}$), we
obtain the conclusion. ∎

######  Remark 8.

Although they need the same assumption that the Karush–Kuhn–Tucker conditions
hold at some global minimizer, the semidefinite relaxations in Theorem 18 have
better complexity than the ones in Theorem 14. It is because it does not
require an exponential number of matrix variables in each semidefinite
relaxation.

##### Acknowledgements.

The author was supported by the funding from ANITI.

## References

  * [1] E. Artin.  Über die zerlegung definiter funktionen in quadrate.  Abhandlungen aus dem mathematischen Seminar der Universität Hamburg, 5(1):100–115, 1927.
  * [2] L. Baldi and B. Mourrain.  On Moment Approximation and the Effective Putinar’s Positivstellensatz.
  * [3] S. Boyd and L. Vandenberghe.  Convex optimization.  Cambridge university press, 2004.
  * [4] M. Coste.  An introduction to semialgebraic geometry, 2000.
  * [5] J. Demmel, J. Nie, and V. Powers.  Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals.  Journal of pure and applied algebra, 209(1):189–200, 2007.
  * [6] K. Fang and H. Fawzi.  The sum-of-squares hierarchy on the sphere and applications in quantum information theory.  Mathematical Programming, pages 1–30, 2020.
  * [7] R. M. Freund.  Optimality conditions for constrained optimization problems.  Massachusetts Institute of Technology (available at: http://s3.amazonaws.com/mitsloan-php/wp-faculty/sites/30/2016/12/15031343/Optimality-Conditions-for-Constrained.pdf), 2016\.
  * [8] J.-L. Krivine.  Anneaux préordonnés.  Journal d’analyse mathématique, 12(1):307–326, 1964.
  * [9] J. B. Lasserre.  Global optimization with polynomials and the problem of moments.  SIAM Journal on optimization, 11(3):796–817, 2001.
  * [10] M. Laurent and L. Slot.  An effective version of Schmüdgen’s Positivstellensatz for the hypercube.  arXiv preprint arXiv:2109.09528, 2021.
  * [11] H. Lombardi, D. Perrucci, and M.-F. Roy.  An elementary recursive bound for effective Positivstellensatz and Hilbert’s 17th problem, volume 263.  American mathematical society, 2020.
  * [12] N. H. A. Mai.  Exact polynomial optimization strengthened with Fritz John conditions.  arXiv preprint arXiv:2205.04254, 2022.
  * [13] N. H. A. Mai, J.-B. Lasserre, and V. Magron.  Positivity certificates and polynomial optimization on non-compact semialgebraic sets.  Mathematical Programming, pages 1–43, 2021.
  * [14] M. Marshall.  Representations of non-negative polynomials having finitely many zeros.  In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 15, pages 599–609, 2006.
  * [15] M. Marshall.  Representations of non-negative polynomials, degree bounds and applications to optimization.  Canadian Journal of Mathematics, 61(1):205–221, 2009.
  * [16] J. Nie.  An exact Jacobian SDP relaxation for polynomial optimization.  Mathematical Programming, 137(1):225–255, 2013.
  * [17] J. Nie.  Optimality conditions and finite convergence of Lasserre’s hierarchy.  Mathematical programming, 146(1-2):97–121, 2014.
  * [18] J. Nie, J. Demmel, and B. Sturmfels.  Minimizing polynomials via sum of squares over the gradient ideal.  Mathematical programming, 106(3):587–606, 2006.
  * [19] J. Nie and M. Schweighofer.  On the complexity of Putinar’s Positivstellensatz.  Journal of Complexity, 23(1):135–150, 2007.
  * [20] T. S. Pham and H. H. Vui.  Genericity in polynomial optimization, volume 3.  World Scientific, 2016.
  * [21] M. Putinar.  Positive polynomials on compact semi-algebraic sets.  Indiana University Mathematics Journal, 42(3):969–984, 1993.
  * [22] C. Scheiderer.  Sums of squares of regular functions on real algebraic varieties.  Transactions of the American Mathematical Society, 352(3):1039–1069, 2000.
  * [23] C. Scheiderer.  Sums of squares on real algebraic curves.  Mathematische zeitschrift, 245(4):725–760, 2003.
  * [24] C. Scheiderer.  Sums of squares on real algebraic surfaces.  manuscripta mathematica, 119(4):395–410, 2006.
  * [25] K. Schmüdgen.  The K-moment problem for compact semi-algebraic sets.  Mathematische Annalen, 289(1):203–206, 1991.
  * [26] M. Schweighofer.  On the complexity of Schmüdgen’s Positivstellensatz.  Journal of Complexity, 20(4):529–543, 2004.
  * [27] L. Slot.  Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel.  arXiv preprint arXiv:2111.04610, 2021.
  * [28] G. Stengle.  A Nullstellensatz and a Positivstellensatz in semialgebraic geometry.  Mathematische Annalen, 207(2):87–97, 1974.