# Sums of squares representations on singular loci

Ngoc Hoang Anh Mai111University of Konstanz; D-78464 Konstanz, Germany. Victor
Magron††footnotemark:  222Université de Toulouse; LAAS; F-31400 Toulouse,
France.

###### Abstract

The problem of characterizing a real polynomial $f$ as a sum of squares of
polynomials on a real algebraic variety $V$ dates back to the pioneering work
of Hilbert in [20]. In this paper, we investigate this problem with a focus on
cases where the real zeros of $f$ on $V$ are singular points of $V$. By using
optimality conditions and irreducible decomposition, we provide a positive
answer to the following essential question of polynomial optimization: _Are
there always exact semidefinite programs to compute the minimum value attained
by a given polynomial over a given real algebraic variety?_ Our answer implies
that Lasserre’s hierarchy, which is known as a bridge between convex and non-
convex programs with algebraic structures, has finite convergence not only in
the generic case but also in the general case. As a result, we constructively
prove that _each hyperbolic program is equivalent to a semidefinite program_.

Keywords: sum of squares; Nichtnegativstellensatz; gradient ideal; singular
locus; polynomial optimization; Karush–Kuhn–Tucker conditions; semidefinite
programming

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Real algebraic varieties
    2. 2.2 Regular and singular loci
    3. 2.3 First-order optimality conditions
    4. 2.4 Semi-algebraic set
    5. 2.5 Sums of squares
    6. 2.6 Nichtnegativstellensätze on regular loci
    7. 2.7 Exact polynomial optimization in the generic case
  3. 3 Decomposition of singular loci
  4. 4 Nichtnegativstellensätze on singular loci
  5. 5 Higher-order optimality conditions
  6. 6 Exact polynomial optimization in the general case
  7. 7 Equivalence of hyperpolic programs and semidefinite programs

##  1 Introduction

#### Semidefinite programs, Positivstellensätze, and Polynomial optimization.

Semidefinite programming, a subfield of convex optimization, was developed in
the early 1960s by Bellman and Fan [6]. Its goal is to minimize a linear
objective function over the intersection of the cone of positive semidefinite
matrices with an affine space. One of the significant applications of
semidefinite programming is to relax a class of non-convex programs with
algebraic structures, which are known as polynomial optimization problems.
These problems have objective and constraint functions that are all
polynomials.

In 2001, Lasserre introduced an appropriate hierarchy of semidefinite programs
in [28] that returns a sequence of values approximately converging to the
optimal value of a given polynomial optimization problem. To do this, he
utilized Positivstellensätze, which are representations of polynomials
positive on a basic semi-algebraic set, a set defined by a system of finitely
many polynomial inequalities. For instance, Putinar’s Positivstellensatz [48],
which guarantees the convergence of Lasserre’s hierarchy, says that each
polynomial positive on a compact basic semi-algebraic set $S$, satisfying the
so-called Archimedean condition, can be decomposed as a linear combination of
polynomials defining $S$, with weights that are sums of squares of
polynomials.

#### Exact semidefinite programs and Nichtnegativstellensätze.

We aim to develop exact semidefinite programs for determining the optimal
value of a given polynomial optimization problem. In this context, the term
“exact semidefinite program” means that, given the objective and constraint
polynomials of a polynomial optimization problem, we can algorithmically
construct a semidefinite program whose optimal value is precisely equal to
that of the original problem. Obtaining such programs is highly significant
since it enables us to use convex optimization to solve non-convex problems.
Moreover, it is typically challenging to bound the gap between the convex
relaxation and the original problem, as is the case with Goemans-Williamson’s
algorithm for Max-Cut [15].

To provide such exact semidefinite programs, we need to build
Nichtnegativstellensätze that are the representations of polynomials non-
negative on a basic semi-algebraic set. Marshall showed in [37, 38] a
Nichtnegativstellensatz having the same form as Putinar’s under the so-called
_boundary Hessian conditions_. Based on this, Nie proves in [45] that
Lasserre’s hierarchy has finite convergence under generic assumptions related
to second-order optimality conditions. The works of Marshall and Nie rely on
the local-global principle stated by Scheiderer in [49, 50, 51]. There
Scheiderer proved the non-strict extension of Schmüdgen’s Positivstellensatz
[52]. The former says that every polynomial $f$ positive on a compact basic
semi-algebraic set $S$ is a linear combination of products of polynomials
defining $S$ with weights that are sums of squares of polynomials. In his
proof, Scheiderer needs a finiteness assumption on the real zeros of $f$ on
$S$. We refer the readers to [8] for some extensions by Burgdorf, Scheiderer,
and Schweighofer that allow us to remove the finiteness assumption on the real
zeros of $f$ on $S$ but still maintain the compactness of $S$. Under strong
regularity assumption, Nie obtains in his work[43] exact semidefinite programs
when using the Jacobian of the input polynomials.

#### Nichtnegativstellensätze based on optimality conditions.

We consider a semi-algebraic set $S$ as a real manifold. A point $a$ in $S$ is
called a singular (resp. regular) point of $S$ if the tangent space of $S$ at
$a$ has smaller (resp. the same) dimension than $S$. The singular (resp.
regular) locus of $S$ is the set of all singular (resp. regular) points of
$S$.

Given a polynomial $f$ non-negative on a basic semi-algebraic set $S$, Demmel,
Nie, and Powers provide in [11] a way to obtain a Nichtnegativstellensatz on
the intersection $S\cap V^{\operatorname{KKT}}$. Here $V^{\operatorname{KKT}}$
represents for the variety defined by the Karush–Kuhn–Tucker conditions for
the minimization of $f$ on $S$. Using the Fritz-John conditions, the first
author extends this approach in [33] to the case where the image of the
singular locus $S^{\operatorname{sing}}$ of $S$ under $f$, denoted by
$f(S^{\operatorname{sing}})$, is finite. He also indicates in [33] several
examples where the previous Nichtnegativstellensätze are inapplicable since
the real zeros of $f$ on $S$ are in $S^{\operatorname{sing}}$. In [32] the
first author provides the degree bounds for these Nichtnegativstellensätze and
analyzes the convergence rate for their application to polynomial
optimization. We emphasize that the Karush–Kuhn–Tucker conditions and the
finiteness assumption on $f(S^{\operatorname{sing}})$ belong to the _generic_
case. By generic, we mean that the properties hold in a Zariski open set in
the space of the coefficients of the input polynomials with given degrees. The
remaining case, corresponding to a set $f(S^{\operatorname{sing}})$ of
infinite cardinality, has not been tackled so far.

Regarding the above two types of first-order optimality conditions, the
Karush–Kuhn–Tucker conditions and the Fritz-John conditions play roles in
characterizing the real zeros of polynomial $f$ on a semi-algebraic set $S$.
Moreover, it is not hard to constructively prove the sums of squares-based
representations of $f$ on the intersection of $S$ with the varieties defined
by these optimality conditions. To do so, we use the fact that $f$ is constant
on each connected component of $V^{\operatorname{KKT}}$, the variety defined
by the Karush–Kuhn–Tucker conditions associated to the minimization of $f$ on
$S$. This property also holds for $V^{\operatorname{FJ}}$, the variety defined
by the Fritz-John conditions, under the finiteness assumption on
$f(S^{\operatorname{sing}})$. The difference here is that
$V^{\operatorname{KKT}}$ contains the real zeros of $f$ that are regular
points of $S$ while $V^{\operatorname{FJ}}$ includes all real zeros of $f$ on
$S$ even if they are singular points of $S$.

#### Contribution.

In the paper, we aim to provide some representations (with degree bounds) of a
polynomial $f$ non-negative on a basic semi-algebraic set $S$ in the general
case.

On one hand, we convert $S$ to a real algebraic variety $V$ (the common real
zeros of a system of polynomials) in higher-dimensional real space and
consider the representations of $f$ on $V$. Set $U:=V$. We then decompose $U$
into finitely many irreducible components $U_{j}$. If $U_{j}$ has zero
dimension, then $f$ is identical to a sum of squares of polynomials on
$U_{j}$. Otherwise, $f$ is identical to a sum of squares of polynomials on
$U_{j}^{\operatorname{KKT}}$, the subvariety of $U_{j}$ defined by the
Karush–Kuhn–Tucker conditions associated to the minimization of $f$ on
$U_{j}$. In this case, we update $U:=U_{j}^{\operatorname{sing}}$ with
$U_{j}^{\operatorname{sing}}$ being the singular locus of $U_{j}$ and repeat
the above process. It will terminate after a finite number of steps because
the singular locus $U_{j}^{\operatorname{sing}}$ has lower dimension than
$U_{j}$.

On the other hand, we provide the degree bounds of our sums of squares-based
representations for $f$ on $U_{j}^{\operatorname{KKT}}$ (or zero-dimensional
$U_{j}$). Consequently, we analyze the convergence rate of Lasserre’s
hierarchy applied to minimizing a polynomial $p$ on each
$U_{j}^{\operatorname{KKT}}$ (or zero-dimensional $U_{j}$). We prove that
Lasserre’s hierarchy on some $U_{j}^{\operatorname{KKT}}$ (or zero-dimensional
$U_{j}$) has finite convergence to the minimum value $p^{\star}$ attained by
$p$ on $V$. Based on this and the algebraic structure of hyperbolic cones, we
demonstrate that each hyperbolic program can be written as a semidefinite
program.

#### Hyperbolic polynomials and hyperbolic programming.

For interested readers, hyperbolic programming, introduced by Güler in [16],
is concerned with optimizing a linear objective function over the intersection
of an affine space with the so-called hyperbolic cone constrained by a
hyperbolic polynomial. Here a real polynomial $p$ is hyperbolic with respect
to a given vector $e$ if the univariate polynomial $t\mapsto p(te-a)$ has only
real roots for all vectors $a$. We refer the readers to [18, 41, 40, 25, 24,
26, 53, 39] for some recent works on hyperbolic polynomials and hyperbolic
programming. Their studies have focused on attacking the generalized Lax
conjecture, whose direct consequence is that every hyperbolic program is
equivalent to a semidefinite program (see, e.g., [2, Remark 1.7]). In our
paper, we prove the latter. Readers might wonder if the equivalence of the two
programs indicates the coincidence of their feasible sets, leading to a
solution for the generalized Lax conjecture. From our point of view, the
generalized Lax conjecture is about fixed cones used in different optimization
problems. It is much different from saying that a hyperbolic optimization
problem with a given objective function $f$ can be solved by a specific
semidefinite program depending on the hyperbolic program associated with $f$.

#### Previous works.

In [34], the first author provides a sum of squares-based representation of a
polynomial $f$ nonnegative on a real algebraic variety $V$ in the case where
the regular locus $V^{\operatorname{reg}}$ of $V$ is dense in $V$. The key
idea is to consider $V$ as the image of a regular variety $W$ under a morphism
$\varphi$, defined by a vector of polynomials. This is done thanks to
Hironaka’s resolution of singularities [21, 22]. Then we use
Demmel–Nie–Powers’ Nichtnegativstellensatz to get the representation of
$f\circ\varphi$ on $W_{\operatorname{KKT}}$, the variety defined by the
Karush–Kuhn–Tucker conditions for minimizing $f\circ\varphi$ on $W$. However,
this method is not always applicable to cases where $V^{\operatorname{reg}}$
is not dense in $V$ (e.g., $V$ is the Whitney or Cartan umbrella). Compared to
this, there is no matter with our method in such challenging cases.

Bucero and Mourrain present in [7] a technique to obtain exact semidefinite
programs for minimizing a polynomial $p$ over a semi-algebraic set $S$ in the
generic case. Firstly, they consider the equivalent minimization of $p$ on a
new semi-algebraic set $S_{\operatorname{FJ}}$, the intersection of $S$ with
the projection of the variety defined by the Fritz-John conditions for
minimizing $p$ on $S$. Secondly, they decompose $S_{\operatorname{FJ}}$ into
two semi-algebraic sets $S_{\operatorname{KKT}}$ and
$S_{\operatorname{sing}}$, then consider the minimization of $p$ on each of
these two sets. Here $S_{\operatorname{KKT}}$ is the intersection of $S$ with
the projection of the variety defined by the Karush–Kuhn–Tucker conditions for
minimizing $p$ on $S$. The set $S_{\operatorname{sing}}$ contains the singular
locus of $S$. They obtain exact semidefinite relaxations for minimizing $p$ on
$S_{\operatorname{KKT}}$ thanks to the work of Demmel, Nie, and Powers [11].
The minimization of $p$ on $S_{\operatorname{sing}}$ is solved recursively. If
$S_{\operatorname{sing}}$ is zero-dimensional, they obtain exact semidefinite
programs for minimizing $p$ on the finite set $S_{\operatorname{sing}}$. The
case of positive-dimensional $S_{\operatorname{sing}}$ has not been handled
entirely in their paper.

Regarding the exactness property, we emphasize that our representations in
this paper are sum-of-squares exactness. In his work [3] with Baldi, the third
author considers moment exactness. It is stronger than sum-of-squares
exactness in practice since it yields the minimizers and tests exactness for
polynomial optimization. Moreover, it is shown in [3, Theorem 4.14] that if
the polar variety defined by the product of minors (and related to the
projection of the Karush–Kuhn–Tucker variety) is finite, then moment exactness
also holds.

#### Motivation.

Our method described in this paper has potential applications to mathematical
programs with complementarity constraints (see, e.g., [1, 31]). These
optimization problems are challenging because the complementarity constraints
typically violate all standard constraint qualifications, making it difficult
to find a solution. Constraint qualifications are known to be sufficient
conditions for the Karush–Kuhn–Tucker conditions in nonlinear programming.
Therefore, classical methods that rely on the Karush–Kuhn–Tucker conditions to
solve mathematical programs with complementarity constraints are limited. In
contrast, our method does not require any constraint qualifications

#### Organization.

We organize the paper as follows: Section 2 presents some preliminaries from
real algebraic geometry needed to prove our main results. Section 3 is to
provide an algorithm that allows us to obtain zero-dimensional and positive-
dimensional subvarieties containing singular points of a real algebraic
variety. Section 4 is to state some Nichtnegativstellensätze on these
subvarieties. Section 5 is to build higher-order optimality conditions that
characterize global minimizers for a polynomial optimization problem. Section
6 is to present the main algorithm that enables us to obtain exact
semidefinite programs for polynomial optimization problems with global
minimizers. Section 7 shows how to convert a hyperbolic program into a
semidefinite program.

We give some interesting examples to illustrate our results. We perform some
calculations on these examples in Julia 1.7.1 with the software Oscar [46].
The codes for them are available in the link:
https://github.com/maihoanganh/SingularSOS.

##  2 Preliminaries

###  2.1 Real algebraic varieties

Let ${\mathbb{R}}[x]$ denote the ring of polynomials with real coefficients in
the vector of variables $x=(x_{1},\dots,x_{n})$. Let ${\mathbb{R}}_{r}[x]$
denote the linear space of polynomials in ${\mathbb{R}}[x]$ of degree at most
$r$.

Given $h_{1},\dots,h_{l}$ in ${\mathbb{R}}[x]$, we denote by $V(h)$ the (real)
algebraic variety in ${\mathbb{R}}^{n}$ defined by the vector
$h=(h_{1},\dots,h_{l})$, i.e.,

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

In this case, $h_{1},\dots,h_{l}$ are called the polynomials defining $V(h)$.

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

$I(h)[x]:=\sum_{j=1}^{l}h_{j}{\mathbb{R}}[x]\,.$ (2)

The real radical of an ideal $I(h)[x]$, denoted by
$\sqrt[{\mathbb{R}}]{I(h)[x]}$, is defined as

${\sqrt[{\mathbb{R}}]{I(h)[x]}}:=\\{f\in{\mathbb{R}}[x]\,:\,\exists
m\in{\mathbb{N}}\,:\,-f^{2m}\in\Sigma^{2}[x]+I(h)[x]\\}\,.$ (3)

Krivine–Stengle’s Nichtnegativstellensatz [23] imply that

$\sqrt[{\mathbb{R}}]{I(h)[x]}:=\\{p\in{\mathbb{R}}[x]\,:\,p=0\text{ on
}V(h)\\}\,.$ (4)

We say that $I(h)[x]$ is real radical if
$I(h)[x]=\sqrt[{\mathbb{R}}]{I(h)[x]}$.

Given an algebraic variety $V$ in ${\mathbb{R}}^{n}$, we denote by $I(V)$ the
vanishing ideal of $V$, i.e.,

$I(V):=\\{p\in{\mathbb{R}}[x]\,:\,p(x)=0\,,\,\forall x\in V\\}\,.$ (5)

Note that $I(V)$ is a real radical ideal. If $V$ is defined by
$h=(h_{1},\dots,h_{l})$ with $h_{j}\in{\mathbb{R}}[x]$, then
$I(V)=\sqrt[{\mathbb{R}}]{I(h)[x]}$. To compute the generators of $I(V)$ with
given polynomials $h_{1},\dots,h_{l}$ defining $V$, we can use, e.g.,
Becker–Neuhaus’ method in [5, 42]. Thereby the degrees of the generators of
$I(V)$ are bounded from above by $d^{2^{\mathcal{O}(n^{2})}}$ if the degrees
of $h_{j}$s are at most $d$. In addition, computing the generators of $I(V)$
can be done via the kernel of the moment matrices (or annihilator of moment
sequences) as in, e.g., Baldi–Mourrain’s method [4]. Then it could be
interesting to get bounds on the degree of the generators returned by this
method.

Given an algebraic variety $V$ in ${\mathbb{R}}^{n}$, we say that $V$ is
irreducible if there do not exist two proper subvarieties $V_{1}$, $V_{2}$ in
${\mathbb{R}}^{n}$ such that $V=V_{1}\cup V_{2}$.

We recall the following result stated in [10, Section 4.6, Theorem 4] and [54,
Lemma 4.9] about the structure of algebraic varieties:

######  Lemma 1.

Let $V$ be an algebraic variety in ${\mathbb{R}}^{n}$. Then $V$ can be written
as a finite union

$V=V_{1}\cup\dots\cup V_{r}\,,$ (6)

where each $V_{j}$ is an irreducible algebraic variety in ${\mathbb{R}}^{n}$
such that $V_{j}\not\subset V_{t}$ if $j\neq t$. Moreover, if $V$ is defined
by polynomials in ${\mathbb{R}}_{d}[x]$, then $r$ is bounded by a constant
depending solely on $n$ and $d$.

We call $V_{1},\dots,V_{r}$ in Lemma 1 irreducible components of $V$. There
are several algorithms for finding the polynomials defining $V_{j}$,
$j=1,\dots,r$, with given polynomials defining $V$. For instance, Gianni,
Trager, and Zacharias suggest an irreducible decomposition (also called
primary decomposition) in [14].

###  2.2 Regular and singular loci

Given $h=(h_{1},\dots,h_{l})$ with $h_{j}\in{\mathbb{R}}[x]$, we denote by
$J(h)$ the Jacobian matrix associated with $h$, i.e.,

$J(h)(x):=\left(\frac{\partial h_{j}}{\partial x_{t}}(x)\right)_{1\leq t\leq
n,1\leq j\leq l}\,.$ (7)

We define the dimension of an algebraic variety $V$ in ${\mathbb{R}}^{n}$,
denoted by $\dim(V)$, to be the highest dimension at points at which $V$ is a
real submanifold. For convenience we assume $\dim(\emptyset)=0$ in this paper.

Let $V$ be a algebraic variety in ${\mathbb{R}}^{n}$ of dimension $d$. Let
$h_{1},\dots,h_{l}\in{\mathbb{R}}[x]$ be the generators of $I(V)$. Set
$h=(h_{1},\dots,h_{l})$. We say that $a\in V$ is a regular point of $V$ if the
Jacobian matrix $J(h)(a)$ has rank $n-d$. Here the rank of a matrix $M$ with
real coefficients is the largest integer $r$ such that all $(r+1)\times(r+1)$
minors of $M$ vanish. The set $V^{\operatorname{reg}}$ of all regular point of
$V$ is called the regular locus of $V$. Let
$V^{\operatorname{sing}}=V\backslash V^{\operatorname{reg}}$. We say that
$a\in V$ is a singular point of $V$ if $a\in V^{\operatorname{sing}}$, i.e.,
the Jacobian matrix $J(h)(a)$ has rank smaller than $n-d$. The set
$V^{\operatorname{sing}}$ is called the singular locus of $V$. The tangent
space of $V$ at $a\in V$, denoted by $T_{a}(V)$, is the linear subspace of
${\mathbb{R}}^{n}$ given by

$T_{a}(V):=\\{u\in{\mathbb{R}}^{n}\,:\,J(h)(a)^{\top}u=0\\}\,.$ (8)

It is not hard to prove that $a\in V$ is a regular point of $V$ iff
$\dim(T_{a}(V))=d=\dim(V)$.

Given $h=(h_{1},\dots,h_{l})$ with $h_{j}\in{\mathbb{R}}[x]$, denote by
$m_{t}(h)(x)$ the vector of $t\times t$ minors of the Jacobian matrix
$J(h)(x)$. Then $m_{t}(h)$ has length $\binom{n}{t}\times\binom{l}{t}$. Each
entry of $m_{t}(h)$ is in ${\mathbb{R}}[x]$ and has degree at most
$t\times\max_{j}\deg(h_{j})$.

The following lemma states some basic properties of singular loci:

######  Lemma 2.

Let $V$ be an algebraic variety in ${\mathbb{R}}^{n}$ of dimension $d$. Let
$h_{1},\dots,h_{l}\in{\mathbb{R}}[x]$ be the generators of $I(V)$. Set
$h=(h_{1},\dots,h_{l})$. Then the following conditions hold:

  1. 1.

The singular locus of $V$ is an algebraic variety in ${\mathbb{R}}^{n}$
defined by $(h,m_{n-d}(h))$.

  2. 2.

The singular locus of $V$ has lower dimension than $V$.

###### Proof.

The first statement is proved similarly to [56, Section 6.2]. The proof of the
second one can be found in [54, Theorem 4.8] (see also [55, Section 12.4.2]).
∎

###  2.3 First-order optimality conditions

Given $h_{0},h_{1},\dots,h_{l}$ in ${\mathbb{R}}[x]$, consider the following
polynomial optimization problem:

$h^{\star}:=\inf\limits_{x\in V(h)}h_{0}(x)\,,$ (9)

where $V(h)$ is the algebraic variety in ${\mathbb{R}}^{n}$ defined by
$h=(h_{1},\dots,h_{l})$.

######  Remark 1.

The more general form

$\begin{array}[]{rl}\inf\limits_{y\in{\mathbb{R}}^{r}}&f(y)\\\
\text{s.t.}&g_{j}(y)\geq 0\,,\,j=1,\dots,l\,,\end{array}$ (10)

can be written as an instance of (9) by setting $x=(y,z)$, $h_{0}(x)=f(y)$,
$h_{j}(x)=g_{j}(y)-z_{j}^{2}$.

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 recall the Karush–Kuhn–Tucker conditions in the
following lemma:

######  Lemma 3.

Let $h_{0}$ in ${\mathbb{R}}[x]$. Let $V$ be an algebraic variety in
${\mathbb{R}}^{n}$ of dimension $d>0$. Let
$h_{1},\dots,h_{l}\in{\mathbb{R}}[x]$ be the generators of $I(V)$. Let
$x^{\star}$ be a local minimizer for problem (9) with $h=(h_{1},\dots,h_{l})$.
Assume that $J(h)(x^{\star})$ has rank $n-d$. Then the Karush–Kuhn–Tucker
conditions hold for problem (9) at $x^{\star}$, i.e.,

$\begin{cases}\exists(\lambda_{1}^{\star},\dots,\lambda_{l}^{\star})\in{\mathbb{R}}^{l}\,:\\\
h_{j}(x^{\star})=0\,,\,j=1,\dots,l\,,\\\ \nabla
h_{0}(x^{\star})=\sum_{j=1}^{l}\lambda_{j}^{\star}\nabla
h_{j}(x^{\star})\,.\end{cases}$ (11)

###### Proof.

By assumption, $x^{\star}$ is a regular point of the manifold
$V\subset{\mathbb{R}}^{n}$. Then there exists a diffeomorphism $\Phi:U\to V$
for some open set $U\subset{\mathbb{R}}^{d}$ such that
$x^{\star}=\Phi(t^{\star})$ for some $t^{\star}\in U$. The differential of
$\Phi$ at $t\in U$ is defined by the linear mapping
$D\Phi_{t}:{\mathbb{R}}^{d}\to T_{\Phi(t)}V$, $u\mapsto J(\Phi)(t)^{\top}u$,
where $T_{a}V$ is the tangent space of $V$ at $a\in V$ (defined as in (8)).
Since $x^{\star}$ is a regular points of $V$, $D\Phi_{t^{\star}}$ is
bijective. From this, we get $\operatorname{rank}(J(\Phi)(t^{\star}))=d$,
which gives the null space of $J(\Phi)(t^{\star})$, denoted by
$J(\Phi)(t^{\star})^{\perp}$, has dimension $n-d$ thanks to the rank–nullity
theorem. By assumption, $t^{\star}$ is a local minimizer of $h_{0}\circ\Phi$
on $U$. It implies that
$0=\nabla(h_{0}\circ\Phi)(t^{\star})=J(\Phi)(t^{\star})\times\nabla
h_{0}(x^{\star})$, which gives $\nabla h_{0}(x^{\star})$ is in
$J(\Phi)(t^{\star})^{\perp}$. In addition, for $j=1,\dots,l$,
$(h_{j}\circ\Phi)(t)=0$ for all $t\in U$. Take the gradient in $t$, we obtain
$J(\Phi)(t)\times\nabla h_{j}(\Phi(t))=0$, for all $t\in U$, for
$j=1,\dots,l$. It implies that $\nabla h_{j}(\Phi(t))$, $j=1,\dots,l$, are in
the null space of $J(\Phi)(t)$, for all $t\in U$. By assumption, the linear
span of $\nabla h_{j}(x^{\star})$, $j=1,\dots,l$, has dimension $n-d$. Since
$J(\Phi)(t^{\star})^{\perp}$ has dimension $n-d$, $J(\Phi)(t^{\star})^{\perp}$
is the linear span of $\nabla h_{j}(x^{\star})$, $j=1,\dots,l$. Hence the
result follows since $\nabla h_{0}(x^{\star})$ is in
$J(\Phi)(t^{\star})^{\perp}$. ∎

######  Remark 2.

As shown in Freund’s lecture note [12, Theorem 11], the Karush–Kuhn–Tucker
conditions (11) hold for problem (9) at $x^{\star}$ when the linear
independence constraint qualification is satisfied, i.e., the gradients
$\nabla h_{j}(x^{\star})$, $j=1,\dots,l$, are linearly independent in
${\mathbb{R}}^{n}$, which is equivalent to that $J(h)(x^{\star})$ has rank
$l$. For comparison purposes, we make a weaker assumption in Lemma 3 that
$J(h)(x^{\star})$ has rank $n-\dim(V)$. Similarly to [10, Exercise 17 b, page
495], we obtain $l\geq n-\dim(V)$ in general. Note that the twisted cubic
$V=\\{(t,t^{2},t^{3})\in{\mathbb{R}}^{3}\,:\,t\in{\mathbb{R}}\\}$ is a one-
dimensional variety defined by $x_{2}-x_{1}^{2}$ and $x_{3}-x_{1}^{3}$, but
the ideal $I(V)$ is generated by the vector of three polynomials
$h=(x_{1}x_{3}-x_{2}^{2},x_{2}-x^{2}_{1},x_{3}-x_{1}x_{2})$. Thus it holds
that $l=3>2=n-\dim(V)$ in this example.

To prove that the largest rank assumption of $J(h)(x^{\star})$ in Lemma 3
cannot be removed, consider the following example:

######  Example 1.

Let $n=2$, $h_{0}=x_{1}$, and $h=x_{1}^{3}-x_{2}^{2}$. Then $x^{\star}=(0,0)$
is the unique global minimizer for problem (9). Moreover, the
Karush–Kuhn–Tucker conditions do not hold for problem (9) at $x^{\star}$.
Indeed, for any $\lambda\in{\mathbb{R}}$, we get

$\nabla h_{0}(x^{\star})-\lambda\nabla h(x^{\star})=\begin{bmatrix}1\\\
0\end{bmatrix}-\lambda\begin{bmatrix}3x_{1}^{*2}\\\
-2x_{2}^{\star}\end{bmatrix}=\begin{bmatrix}1\\\ 0\end{bmatrix}\neq 0\,.$ (12)

Note that $V(h)$ has dimension $d=1$, and $J(h)=\nabla
h=\begin{bmatrix}3x_{1}^{2}\\\ -2x_{2}\end{bmatrix}$. It is not hard to check
that $J(h)(x^{\star})$ has rank $0<1=n-d$.

Given $\bar{h}:=(h_{0},h)$ with $h:=(h_{1},\dots,h_{l})$ and
$h_{j}\in{\mathbb{R}}[x]$, we denote by $\bar{h}_{\operatorname{KKT}}$ the
vector of polynomials in ${\mathbb{R}}[x,\lambda]$ associated with the
Karush–Kuhn–Tucker conditions defined by

$\bar{h}_{\operatorname{KKT}}:=(h,\nabla h_{0}-\sum_{j=1}^{l}\lambda_{j}\nabla
h_{j})\,,$ (13)

where $\lambda=(\lambda_{1},\dots,\lambda_{l})$. The condition (11) can be
written as $(x^{\star},\lambda^{\star})\in V(\bar{h}_{\operatorname{KKT}})$
for some $\lambda^{\star}\in{\mathbb{R}}^{l}$.

###  2.4 Semi-algebraic set

Given $g=(g_{1},\dots,g_{m})$ with $g_{j}\in{\mathbb{R}}[x]$, we denote by
$S(g)$ the basic semi-algebraic set associated with $g$, i.e.,

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

A semi-algebraic subset of ${\mathbb{R}}^{n}$ is a subset of the following
form

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

where $f_{ij}\in{\mathbb{R}}[x]$ and $*_{ij}\in\\{>,=\\}$. Note that (15) is
the union of finitely many basic semi-algebraic sets.

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$.

The following lemma can be found in [47, Proposition 1.6.2 (ii)]:

######  Lemma 4.

Compositions of semi-algebraic maps are semi-algebraic.

The following lemma is given in [47, Theorem 1.8.1]:

######  Lemma 5.

Let $f:(a,b)\to{\mathbb{R}}$ be a semi-algebraic function. Then there are
$a=a_{0}<a_{1}<\dots<a_{s}<a_{s+1}=b$ such that, for each $i=0,\dots,s$, the
restriction $f|_{(a_{i},a_{i+1})}$ is analytic.

The following lemma follows from the mean value theorem:

######  Lemma 6.

Let $f:[0,1]\to{\mathbb{R}}$ be a continuous piecewise-differentiable
function, i.e., there exist $0=a_{1}<\dots<a_{r}=1$ such that $f$ is
continuous and $f$ is differentiable on each open interval $(a_{i},a_{i+1})$.
Assume that $f$ has zero subgradient. Then $f(0)=f(1)$.

###### Proof.

By using the mean value theorem on each open interval $(a_{i},a_{i+1})$, we
get $f(a_{i})=f(a_{i+1})$. Hence $f(0)=f(a_{1})=\dots=f(a_{r})=f(1)$ yields
the result. ∎

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

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

We recall in the following lemma the upper bound on the number of connected
components of a basic semi-algebraic set is stated by Coste in [9, Proposition
4.13]:

######  Lemma 7.

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.5 Sums of squares

Denote by $\Sigma^{2}[x]$ (resp. $\Sigma^{2}_{r}[x]$) the cone of sums of
squares of polynomials in ${\mathbb{R}}[x]$ (resp. ${\mathbb{R}}_{r}[x]$).
Given $g_{1},\dots,g_{m}\in{\mathbb{R}}[x]$, let $P_{r}(g)[x]$ be the
truncated preordering of order $r\in{\mathbb{N}}$ associated with
$g=(g_{1},\dots,g_{m})$, i.e.,

$P_{r}(g)[x]:=\\{\sum_{\alpha\in\\{0,1\\}^{m}}\sigma_{\alpha}g^{\alpha}\,:\,\sigma_{\alpha}\in\Sigma^{2}[x]\,,\,\deg(\sigma_{\alpha}g^{\alpha})\leq
2r\\}\,,$ (17)

where $\alpha=(\alpha_{1},\dots,\alpha_{m})$ and
$g^{\alpha}:=g_{1}^{\alpha_{1}}\dots g_{m}^{\alpha_{m}}$. If $m=0$, it holds
that $P_{r}(g)[x]=\Sigma^{2}_{r}[x]$.

Given $h_{1},\dots,h_{l}\in{\mathbb{R}}[x]$, let $I_{r}(h)[x]$ be the
truncated ideal of order $r$ defined 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\\}\,.$ (18)

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}$ (19)

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

$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)}}\,.$
(20)

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

######  Lemma 8.

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=\frac{1}{2}\times b(n,d,m+l+1)$. Then it
holds that $-1\in P_{r}(g)[x]+I_{r}(h)[x]$.

######  Lemma 9.

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:=\frac{1}{2}\times b(n,d,m+l+1)$ and
$s:=2\lfloor r/d\rfloor$. Then it holds that $-p^{s}\in
P_{r}(g)[x]+I_{r}(h)[x]$.

###  2.6 Nichtnegativstellensätze on regular loci

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

We state in the following lemma a sums of squares-based representation with
degree bound for a polynomial which has finitely many non-negative values on a
real algebraic variety:

######  Lemma 10.

Let $h_{0},h_{1},\dots,h_{l}$ in ${\mathbb{R}}_{d}[x]$. Assume that $h_{0}$ is
non-negative on $V(h)$ and $h_{0}(V(h))$ is finite with
$h=(h_{1},\dots,h_{l})$. Set $r:=|h_{0}(V(h))|$ and $u:=\frac{1}{2}\times
b(n,d,l+1)$. Then there exists $\sigma\in\Sigma^{2}_{w}[x]$ with
$w=\max\\{d(r-1),u+d\\}$ such that $h_{0}-\sigma$ vanishes on $V(h)$.

###### Proof.

Consider the following two cases:

  * •

Case 1: $r=0$. It is obvious that $V(h)=\emptyset$. Lemma 8 says that
$-1\in\Sigma^{2}_{u}[x]+I_{u}(h)[x]$. It implies that there exists $q\in
P_{u}(g)[x]$ such that $-1=q$ on $V(h)$. We write $h_{0}=s_{1}-s_{2}$, where
$s_{1}=(h_{0}+\frac{1}{2})^{2}$ and $s_{2}=h_{0}^{2}+\frac{1}{4}$ are in
$\Sigma^{2}[x]$. From this we get $h_{0}=s_{1}+qs_{2}$ on $V(h)$. Letting
$\sigma=s_{1}+qs_{2}$ gives
$\sigma\in\Sigma^{2}_{u+d}[x]\subset\Sigma^{2}_{w}[x]$ since $w\geq u+d$. Thus
$h_{0}-\sigma$ vanishes on $V(h)$.

  * •

Case 2: $r>0$. By assumption, we can assume that
$h_{0}(V(h))=\\{t_{1},\dots,t_{r}\\}\subset[0,\infty)$, where $t_{i}\neq
t_{j}$ if $i\neq j$. For $j=1,\dots,r$, let $W_{j}:=V(h,h_{0}-t_{j})$. Then
$W_{j}$ is a real variety defined by $l+1$ polynomials in
${\mathbb{R}}_{d}[x]$. It is clear that $h_{0}(W_{j})=\\{t_{j}\\}$. Define the
following polynomials:

$p_{j}(x):=\prod_{i\neq
j}\frac{h_{0}(x)-t_{i}}{t_{j}-t_{i}}\,,\,j=1,\dots,r\,.$ (21)

It is easy to check that $p_{j}(W_{i})=\\{\delta_{ji}\\}$ and $\deg(p_{j})\leq
d(r-1)$. Note that $h_{0}=t_{i}\geq 0$ on $W_{i}$, for $i=1,\dots,r$. Now
letting $\sigma=\sum_{i=1}^{r}t_{i}p_{i}^{2}$, we obtain
$\sigma\in\Sigma^{2}_{w}[x]$ since $\deg(t_{i}p_{i}^{2})\leq 2\deg(p_{i})\leq
2d(r-1)\leq 2w$. Hence $h_{0}-\sigma$ vanishes on $V(h)=W_{1}\cup\dots\cup
W_{r}$, yielding the result.

∎

The following lemma is similar to [11, Lemma 3.3] but is proved by using the
tools from real algebraic geometry (instead of the ones from complex algebraic
geometry):

######  Lemma 11.

Let $h_{1},\dots,h_{l}$ in ${\mathbb{R}}[x]$. Let $h_{0}$ be a polynomial in
${\mathbb{R}}[x]$. Let $W$ be a semi-algebraically path connected component of
$V(\bar{h}_{\operatorname{KKT}})$, where $\bar{h}:=(h_{0},\dots,h_{l})$. Then
$h_{0}$ 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
$h_{0}(x^{(0)})=h_{0}(x^{(1)})$. By assumption, there exists a continuous
semi-algebraic mapping $\phi:[0,1]\to W$ defined by
$\phi(\tau)=(x(\tau),\lambda(\tau))$ such that
$\phi(0)=(x^{(0)},\lambda^{(0)})$ and $\phi(1)=(x^{(1)},\lambda^{(1)})$. We
claim that $\tau\mapsto h_{0}(x(\tau))$ is constant on $[0,1]$. The Lagrangian
function

$L(x,\lambda):=h_{0}(x)-\sum_{j=1}^{m}\lambda_{j}h_{j}(x)\,$ (22)

is equal to $h_{0}(x)$ on $V(\bar{h}_{\operatorname{KKT}})$, which contains
$\phi([0,1])$. By Lemma 4, the function $L\circ\phi$ is semi-algebraic.
Moreover, the function $L\circ\phi$ is continuous since $L$ and $\phi$ are
continuous. It implies that $L\circ\phi$ is a continuous piecewise-
differentiable function thanks to Lemma 5. Note that the function $L\circ\phi$
has zero subgradient on $[0,1]$. From Lemma 6, it follows that
$h_{0}(x(0))=(L\circ\phi)(0)=(L\circ\phi)(1)=h_{0}(x(1))$. We now obtain
$h_{0}(x^{(0)})$ = $h_{0}(x^{(1)})$ and hence $h_{0}$ is constant on $W$. ∎

Based on the Karush–Kuhn–Tucker conditions, we state in the following theorem
the sums of squares-based representation with degree bound for a polynomial
non-negative on algebraic varieties:

######  Theorem 1.

Let $h_{0},h_{1},\dots,h_{l}$ be polynomial in ${\mathbb{R}}_{d}[x]$ with
$d\geq 2$. Assume that $h_{0}$ is non-negative on $V(h)$ with
$h=(h_{1},\dots,h_{l})$. Set $\bar{h}:=(h_{0},h)$,
$\lambda:=(\lambda_{1},\dots,\lambda_{l})$ and

$w:=\max\\{d\times(c(n+l,d,n+l)-1),\frac{1}{2}\times b(n+l,d,l+n+1)+d\\}\,,$
(23)

where $c(\cdot)$ and $b(\cdot)$ are defined as in (16) and (20), respectively.
Then the following statements hold:

  1. 1.

The cardinality of $h_{0}(V(\bar{h}_{\operatorname{KKT}}))$ is at most
$c(n+l,d+1,n+l)$.

  2. 2.

There exists $\sigma\in\Sigma^{2}_{w}[x,\lambda]$ such that $h_{0}-\sigma$
vanishes on $V(\bar{h}_{\operatorname{KKT}})$.

###### Proof.

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

$s\leq c(n+l,d,n+l)\,,$ (24)

since each entry of $\bar{h}_{\operatorname{KKT}}$ has degree at most $d\geq
2$. Accordingly Lemma 11 shows that $h_{0}$ is constant on each $Z_{i}$. Thus
$h_{0}(V(\bar{h}_{\operatorname{KKT}}))$ is finite. Set
$r=|h_{0}(V(\bar{h}_{\operatorname{KKT}}))|$. From (24), we get

$r\leq s\leq c(n+l,d,n+l)\,.$ (25)

Set

$u:=\frac{1}{2}\times b(n+l,d,l+n+1)\,.$ (26)

By using Lemma 10, there exists $\sigma\in\Sigma^{2}_{\xi}[x,\lambda]$ with
$\xi=\max\\{d(r-1),u+d\\}$ such that $h_{0}-\sigma$ vanishes on
$V(\bar{h}_{\operatorname{KKT}})$. By (25) and (23), we get $\xi\leq w$, and
hence $\sigma\in\Sigma^{2}_{w}[x,\lambda]$. ∎

######  Remark 3.

Regarding the representation in Theorem 1, it could also be interesting to
stay in the $x$-space instead of lifting to the $(x,\lambda)$-space. To do
this, we need the projections of the Karush–Kuhn–Tucker varieties onto the
$x$-space and handle the representations similar to the ones of Bucero and
Murrain in [7]. Another open/difficult question is to get better (e.g., double
exponential) bounds for the representation of polynomials.

We state in the following theorem the degree bound for Nie’s
Nichtnegativstellensatz [44], which is the sums of squares-based
representation for a polynomial non-negative on zero-dimensional algebraic
varieties:

######  Theorem 2.

Let $h_{0},h_{1},\dots,h_{l}$ be polynomial in ${\mathbb{R}}_{d}[x]$ with
$d\geq 2$. Assume that $V(h)$ with $h=(h_{1},\dots,h_{l})$ has zero dimension
and $h_{0}$ is non-negative on $V(h)$. Set

$w:=\max\\{d\times(c(n,d,l)-1),\frac{1}{2}\times b(n,d,l+1)+d\\}\,,$ (27)

where $c(\cdot)$ and $b(\cdot)$ are defined as in (16) and (20), respectively.
Then the following statements hold:

  1. 1.

The cardinality of $h_{0}(V(h))$ is at most $c(n,d,l)$.

  2. 2.

There exists $\sigma\in\Sigma^{2}_{w}[x]$ such that $h_{0}-\sigma$ vanishes on
$V(h)$.

###### Proof.

Since $V(h)$ has zero-dimension, $V(h)$ has a finite number $s$ of distinct
points. By Lemma 7, we get $s\leq c(n,d,l)$ since each entry of $h$ has degree
at most $d\geq 2$. Then $h_{0}$ is constant on each $Z_{i}$ which yields
$h_{0}(V(\bar{h}_{\operatorname{KKT}}))$ is finite. Set $r=|h_{0}(V(h))|$. It
implies that $r\leq s\leq c(n,d,l)$. Set $u:=\frac{1}{2}\times b(n,d,l+1)$. By
using Lemma 10, there exists $\sigma\in\Sigma^{2}_{\xi}[x]$ with
$\xi=\max\\{d(r-1),u+d\\}$ such that $h_{0}-\sigma$ vanishes on $V(h)$. It is
not hard to prove that $\xi\leq w$, and hence $\sigma\in\Sigma^{2}_{w}[x]$. ∎

###  2.7 Exact polynomial optimization in the generic case

We recall some preliminaries of the Moment-SOS relaxations originally
developed by Lasserre in [28]. 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.

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}}$.

The following lemma shows the connection between sums of squares and
semidefinite programming (see, e.g., [29, Proposition 2.1]):

######  Lemma 12.

Let $\sigma\in{\mathbb{R}}[x]$ and $d\in{\mathbb{N}}$ such that
$2d\geq\deg(\sigma)$. Then $\sigma\in\Sigma^{2}[x]$ iff there exists $G\succeq
0$ such that $\sigma=v_{d}^{\top}Gv_{d}$.

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

$\begin{array}[]{rl}\tau_{k}(\bar{h}):=\inf\limits_{y}&L_{y}(h_{0})\\\
\text{s.t}&M_{k}(y)\succeq 0\,,\\\
&M_{k-r_{t}}(h_{t}y)=0\,,\,t=1,\dots,l\,,\,y_{0}=1\,,\end{array}$ (28)
$\begin{array}[]{rl}\rho_{k}(\bar{h}):=\sup\limits_{\xi,G,u_{t}}&\xi\\\
\text{s.t}&G\succeq 0\,,\\\
&h_{0}-\xi=v_{k}^{\top}Gv_{k}+\sum_{t=1}^{l}h_{t}u_{t}^{\top}v_{2(k-r_{t})}\,,\\\
\end{array}$ (29)

where $r_{t}=\lceil\deg(h_{t})/2\rceil$. Using Lemma 12, we obtain

$\rho_{k}(\bar{h})=\sup_{\xi\in{\mathbb{R}}}\\{\xi\,:\,h_{0}-\xi\in\Sigma_{k}[x]+I_{k}(h)[x]\\}\,.$
(30)

Primal-dual semidefinite programs (28)-(29) is known as the Moment-SOS
relaxations of order $k$ for problem (9).

We state in the following lemma some recent results involving the Moment-SOS
relaxations:

######  Lemma 13.

Let $h_{0},h_{1},\dots,h_{l}\in{\mathbb{R}}_{d}[x]$. Let $h^{\star}$ be as in
(9) with $h=(h_{1},\dots,h_{l})$. Set $\bar{h}=(h_{0},h)$. Assume that
$h^{\star}>-\infty$. Then the following statements hold:

  1. 1.

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

  2. 2.

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

  3. 3.

If there exists $q\in\Sigma_{w}[x]$ with $2w\geq d$ such that
$h_{0}-h^{\star}-q$ vanishes on $V(h)$, then $\rho_{r}(\bar{h})=h^{\star}$
with $r=\frac{1}{2}\times b(n,2w,l+1)+d$, where $b(\cdot)$ is defined as in
(20).

###### Proof.

The proofs of the first two statements are trivial. Let us use Nie’s technique
in [45, Proof of Theorem 1.1] to prove the third statement. (It allows us to
avoid using real radical but still obtain exact semidefinite programs thanks
to Krivine–Stengle’s Nichtnegativstellensätze.) Consider the following two
cases:

  * •

Case 1: $V(h)=\emptyset$. Then we get $h^{\star}=\infty$. Set
$s=\frac{1}{2}\times b(n,d,l+1)$. Then Lemma 9 says that
$-1\in\Sigma^{2}_{s}[x]+I_{s}(h)[x]$. For all $\xi\geq 0$, it holds that

$h_{0}-\xi=(1+\frac{h_{0}}{4})^{2}-(\xi+(1-\frac{h_{0}}{4})^{2})\in\Sigma_{s+d}[x]+I_{s+d}(h)[x]\,.$
(31)

Since $r\geq s+d$, it implies that for all $\xi\geq 0$,
$h_{0}-\xi\in\Sigma_{r}[x]+I_{r}(h)[x]$, which yields that $\xi$ is a feasible
solution for (30) of the value $\rho_{r}(\bar{h})$. Thus we obtain that
$\rho_{r}(\bar{h})=\infty=h^{\star}$.

  * •

Case 2: $V(h)\neq\emptyset$. Then we get $h^{\star}<\infty$. Set
$u=h_{0}-h^{\star}-q$. By assumption,we get $u\in{\mathbb{R}}_{2w}[x]$ and
$u=0$ on $V(h)$. Set $s=2\lfloor(r-d)/(2w)\rfloor$. From this, Lemma 9 says
that there exist $\sigma\in\Sigma_{r-d}^{2}[x]$ such that $u^{2s}+\sigma\in
I_{r-d}(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

$\begin{array}[]{rl}h_{0}-h^{\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\Sigma^{2}_{r-d}[x]+I_{r-d}(h)[x]\subset\Sigma^{2}_{r}[x]+I_{r}(h)[x]\,.\end{array}$
(32)

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

∎

We apply Theorem 1 for polynomial optimization as follows:

######  Theorem 3.

Let $h_{0},h_{1},\dots,h_{l}\in{\mathbb{R}}_{d}[x]$. Let $h^{\star}$ be as in
problem (9) with $h=(h_{1},\dots,h_{l})$. Assume that problem (9) has a global
minimizer at which the Karush–Kuhn–Tucker conditions hold for this problem.
Let $w$ be as in (23). Set

$r:=\frac{1}{2}\times b(n+l,2w,l+n+1)+d\,.$ (33)

Then $\rho_{r}(h_{0},\bar{h}_{\operatorname{KKT}})=h^{\star}$, where
$\bar{h}:=(h_{0},h)$ and $b(\cdot)$ is defined as in (20).

###### Proof.

By assumption, there exists $(x^{\star},\lambda^{\star})\in
V(\bar{h}_{\operatorname{KKT}})$ such that $x^{\star}$ is a global minimizer
of (9). It implies that

$\begin{array}[]{rl}h^{\star}:=\min\limits_{x,\lambda}&h_{0}(x)\\\
\text{s.t.}&(x,\lambda)\in V(\bar{h}_{\operatorname{KKT}})\,,\end{array}$ (34)

By assumption, Theorem 1 yields that there exists
$q\in\Sigma^{2}_{w}(g)[x,\lambda]$ such that $h_{0}-h^{\star}-q$ vanishes on
$V(\bar{h}_{\operatorname{KKT}})$. Applying the third statement of Lemma 13,
we obtain the conclusion. ∎

######  Remark 4.

Let $h=(h_{1},\dots,h_{l})$ with $h_{j}\in{\mathbb{R}}[x]$ and let $h^{\star}$
be as in (9). Assume that $h^{\star}$ is finite but is not attained i.e.,
$h_{0}(x)-h^{\star}>0$ for all $x\in V(h)$. (For instance, we can take (i)
$h_{0}=x_{1}$ and $h=(x_{1}x_{2}^{2}-1)$ or (ii)
$h_{0}=(x_{1}x_{2}-1)^{2}+x_{1}^{2}$ and $h=(0)$.) By Theorem 1, the set
$h_{0}(V(\bar{h}_{\operatorname{KKT}}))-h^{\star}$ (with $\bar{h}:=(h_{0},h)$)
has a finite number of values but does not have zero value. It is because of

$0\notin h_{0}(V(h))-h^{\star}\supset
h_{0}(V(\bar{h}_{\operatorname{KKT}}))-h^{\star}\,.$ (35)

It implies that
$\inf(h_{0}(V(\bar{h}_{\operatorname{KKT}}))-h^{\star})=\delta>0$, so that
$\inf h_{0}(V(\bar{h}_{\operatorname{KKT}}))=h^{\star}+\delta$. Note that
$\delta=\infty$ iff $h_{0}(V(\bar{h}_{\operatorname{KKT}}))=\emptyset$. Thus
we obtain
$\rho_{r}(h_{0},\bar{h}_{\operatorname{KKT}})=h^{\star}+\delta>h^{\star}$,
where $w$ is as in (23) and $r$ is as in (33). To address this attainability
issue, see Remark 12.

We present the application of Theorem 2 to polynomial optimization:

######  Theorem 4.

Let $h_{0},h_{1},\dots,h_{l}\in{\mathbb{R}}_{d}[x]$. Let $h^{\star}$ be as in
problem (9) with $h=(h_{1},\dots,h_{l})$. Assume that $V(h)$ has zero-
dimension. Let $w$ be as in (27). Set

$r:=\frac{1}{2}\times b(n,2w,l+1)+d\,.$ (36)

Then $\rho_{r}(h_{0},h)=h^{\star}$, where $b(\cdot)$ is defined as in (20).

###### Proof.

By assumption, Theorem 2 yields that there exists $q\in\Sigma^{2}_{w}[x]$ such
that $h_{0}-h^{\star}-q$ vanishes on $V(h)$. Applying the third statement of
Lemma 13, we obtain the conclusion. ∎

##  3 Decomposition of singular loci

The following algorithm allows us to obtain the zero-dimensional and positive-
dimensional subvarieties containing singular points of a real algebraic
variety:

######  Algorithm 1.

Decomposition of singular loci.

  * •

Input: Algebraic variety $V$ in ${\mathbb{R}}^{n}$ defined by polynomials in
${\mathbb{R}}[x]$.

  * •

Output: Sets $A$ and $B$ of subvarieties of $V$.

  1. 1.

Set $U:=V$, $A:=\emptyset$ and $B:=\emptyset$.

  2. 2.

Let $U_{1},\dots,U_{r}$ be the irreducible components of $U$.

  3. 3.

Set $A:=A\cup\\{U_{1},\dots,U_{r}\\}$.

  4. 4.

For $j=1,\dots,r$, do:

    1. (a)

If $U_{j}$ is zero-dimensional, then set $A:=A\backslash\\{U_{j}\\}$ and
$B:=B\cup\\{U_{j}\\}$.

    2. (b)

Otherwise, let $U_{j}^{\operatorname{sing}}$ be the singular locus of $U_{j}$,
set $U:=U_{j}^{\operatorname{sing}}$ and run again Steps 2, 3, 4.

######  Remark 5.

In order to verify if $U_{j}$ is zero-dimensional as in Step 4 (a) of
Algorithm 1, we refer the readers to the work of Lairez and Safey El Din in
[27]. Moreover, their method also allows us to compute the dimension of a
general real algebraic variety.

######  Remark 6.

In Step 4 (b) of Algorithm 1, we implicitly compute generators $h$ of the real
radical $I(U_{j})$ to get the singular locus $U_{j}^{\operatorname{sing}}$ as
defined by $(h,m_{n-d}(h))$ (see the first statement of Lemma 2). In
particular, if $U_{j}^{\operatorname{sing}}$ is defined by $(h,m_{n-d}(h))$
for some vector of polynomials $h$ defining $U_{j}$ and having multiplicities
(e.g., $h=(q^{2})$ for some $q\in{\mathbb{R}}[x]$), then we have
$U_{j}^{\operatorname{sing}}=U_{j}$, and Algorithm 1 loops forever. Other
approaches based on deflation techniques and the so-called Thom–Boardman
stratification could avoid this issue. They allow us to apply directly to the
equations and derivatives (see, e.g., the work of Hauenstein and Wampler
[17]). These methods are probably not very efficient but might give better
bounds for polynomials defining singular loci than relying on the computation
of real radical based on Becker–Neuhaus’ method in [5, 42].

The following lemma provides some properties of the output of Algorithm 1.

######  Lemma 14.

Let $A$ and $B$ be the output of Algorithm 1. The following statements hold:

  1. 1.

$A$ and $B$ are the sets of finite numbers of algebraic varieties in
${\mathbb{R}}^{n}$ defined by polynomials in ${\mathbb{R}}[x]$.

  2. 2.

Each variety in $A$ is irreducible and positive-dimensional.

  3. 3.

Each variety in $B$ is irreducible and zero-dimensional.

  4. 4.

$V=\bigcup\limits_{W\in A\cup B}W$.

###### Proof.

Let us prove the first statement. By Lemma 1 and the first statement of Lemma
2, $U_{j}$ and $U_{j}^{\operatorname{sing}}$ in Step 4 (b) of Algorithm 1 are
algebraic varieties in ${\mathbb{R}}^{n}$ defined by polynomials in
${\mathbb{R}}[x]$, then so are the elements of $A$ and $B$. To prove that $A$
and $B$ are finite, we only need to show that Algorithm 1 terminates after a
finite number of steps. Assume by contradiction that Algorithm 1 never
terminates. Lemma 1 says that the number $r$ in Step 2 of Algorithm 1 is
finite. From this, Step 4 (b) produces an infinite sequence of irreducible
varieties $(W_{t})_{t\in{\mathbb{N}}}$ such that $W_{0}$ is an irreducible
component of $V$ and $W_{t+1}$ is an irreducible component of the singular
locus of $W_{t}$. It is impossible since the second statement of Lemma 2 gives
$\dim(V)\geq\dim(W_{t})>\dim(W_{t+1})\geq 0$ for all $t\in{\mathbb{N}}$. The
last three statements are due to Step 1 and Step 4 (a) of Algorithm 1. ∎

We now give the following example, which is based on [33, Example 18]:

######  Example 2.

Let $n=5$ and $V=V(h)$ with
$h=(x_{1}^{3}-x_{4}^{2},(x_{2}-x_{3})^{3}-x_{5}^{2},x_{1}(x_{2}-x_{3}))$ be as
the input of Algorithm 1. In Step 2 of Algorithm 1, we decompose $V$ into
irreducible components: $U_{j}=V(h^{(j)})$, $j=1,2$, where
$h^{(1)}=(x_{5},x_{2}-x_{3},x_{1}^{3}-x_{4}^{2})$ and
$h^{(2)}=(x_{4},(x_{2}-x_{3})^{3}-x_{5}^{2},x_{1})$. (Both $U_{1}$ and $U_{2}$
have dimension two.) Let $U_{j}^{\operatorname{sing}}$ be the singular locus
of $U_{j}$, $j=1,2$. Using the first statement of Lemma 2, we obtain the
vector of polynomials
$h^{(1)}_{\operatorname{sing}}=(x_{1},x_{5},x_{4},x_{2}-x_{3})$ defining
$U_{1}^{\operatorname{sing}}$. It is clear that $U_{1}^{\operatorname{sing}}$
is an irreducible variety of dimension one and the singular locus of
$U_{1}^{\operatorname{sing}}$ is empty. Similarly, we obtain the same vector
of polynomials $h^{(2)}_{\operatorname{sing}}=(x_{1},x_{5},x_{4},x_{2}-x_{3})$
defining $U_{2}^{\operatorname{sing}}$, so we get
$U_{2}^{\operatorname{sing}}=U_{1}^{\operatorname{sing}}$. Step 4 (a) of
Algorithm 1 yields $A=\\{U_{1},U_{2},U_{1}^{\operatorname{sing}}\\}$ and
$B=\\{\emptyset\\}$.

##  4 Nichtnegativstellensätze on singular loci

We provide in the following theorem the sums of squares-based representations
on subvarieties returned by Algorithm 1:

######  Theorem 5.

Let $q_{0},h_{1},\dots,h_{l}$ in ${\mathbb{R}}[x]$. Assume that $q_{0}$ is
non-negative on $V(h)$ with $h:=(h_{1},\dots,h_{l})$. Let $A$ and $B$ be the
output of Algorithm 1 with input $V=V(h)$. Let $c(\cdot)$ and $b(\cdot)$ be as
in (16) and (20), respectively. Then the following statements hold:

  1. 1.

For each variety $U$ in $A$ defined by $q=(q_{1},\dots,q_{r})$ with
$q_{j}\in{\mathbb{R}}[x]$, then

    1. (a)

the cardinality of $q_{0}(V(\bar{q}_{\operatorname{KKT}}))$ with
$\bar{q}=(q_{0},q)$ is at most

$c(n+r,d+1,n+r)\,,$ (37)

where $d:=\max\\{\deg(q_{j})\,:\,j=0,\dots,r\\}$;

    2. (b)

there exists $\sigma\in\Sigma_{w}[x,\lambda]$ with
$\lambda=(\lambda_{1},\dots,\lambda_{l})$ and

$w:=\max\\{d\times(c(n+r,d,n+r)-1),\frac{1}{2}\times b(n+r,d,r+n+1)+d\\}$ (38)

such that $q_{0}-\sigma$ vanishes on $V(\bar{q}_{\operatorname{KKT}})$.

  2. 2.

For each variety $U$ in $B$ defined by $q=(q_{1},\dots,q_{r})$ with
$q_{j}\in{\mathbb{R}}[x]$, then

    1. (a)

the cardinality of $q_{0}(V(q))$ is at most $c(n,d,r)$, where
$d:=\max\\{\deg(q_{j})\,:\,j=0,\dots,r\\}$;

    2. (b)

there exists $\sigma\in\Sigma_{w}[x]$ with

$w:=\max\\{d\times(c(n,d,r)-1),\frac{1}{2}\times b(n,d,r+1)+d\\}$ (39)

such that $q_{0}-\sigma$ vanishes on $V(q)$.

###### Proof.

To prove the first and second statements, we apply Theorems 1 and 2,
respectively. Note that for each $U$ in $A$, $p_{0}$ is non-negative on
$U\cap{\mathbb{R}}^{n}$ since $q_{0}$ is non-negative on
$V\cap{\mathbb{R}}^{n}\supset U\cap{\mathbb{R}}^{n}$. Moreover, the second
statement of Lemma 14 yields that each $U$ in $B$ has zero-dimension. ∎

######  Example 3.

We use the same notation as in Example 2. Let $q_{0}=x_{1}+x_{2}-x_{3}$. Then
$q_{0}$ is non-negative on $V(h)$. Assume by contradiction that the non-strict
extension of Schmüdgen’s Positivstellensatz is applicable to $q_{0}$ on
$V(h)$, i.e., $q_{0}\in\Sigma^{2}_{d}[x]+I_{d}(h)[x]$ for some
$d\in{\mathbb{N}}$. Letting $x_{2}=x_{3}=x_{4}=x_{5}=0$, we get
$x_{1}=\sigma+x_{1}^{3}\psi$ for some $\sigma\in\Sigma^{2}[x_{1}]$ and
$\psi\in{\mathbb{R}}[x_{1}]$. It implies that $x_{1}$ divides $\sigma$ so that
$\sigma=x_{1}^{2}\sigma_{1}$ for some $\sigma_{1}\in\Sigma^{2}[x_{1}]$. From
this, $x_{1}=x_{1}^{2}\sigma_{1}+x_{1}^{3}\psi$ implies that
$1=x_{1}(\sigma_{1}+x_{1}\psi)$, which is impossible when we set $x_{1}=0$. It
is not hard to check that Theorem 5.2 (b) is applicable to this example.
Indeed, letting $\lambda:=(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4})$
and $\sigma:=0$ implies that $\sigma\in\Sigma[x,\lambda]$ and $q_{0}-\sigma$
vanishes on $U_{1}^{\operatorname{sing}}=V(h^{(1)}_{\operatorname{sing}})\in
A$. Thus $q_{0}-\sigma$ vanishes on $V(\bar{q}_{\operatorname{KKT}})\subset
V(h^{(1)}_{\operatorname{sing}})\times{\mathbb{R}}^{4}$ with
$\bar{q}=(q_{0},h^{(1)}_{\operatorname{sing}})$.

##  5 Higher-order optimality conditions

We characterize a local minimizer for problem (9) with first-order optimality
conditions in the following lemma:

######  Lemma 15.

Let $V$ be an algebraic variety in ${\mathbb{R}}^{n}$. Let
$h_{1},\dots,h_{l}\in{\mathbb{R}}[x]$ be the generators of $I(V)$. Let $h_{0}$
be a polynomial in ${\mathbb{R}}[x]$ such that problem (9) with
$h=(h_{1},\dots,h_{l})$ has a local minimizer $x^{\star}$. Then one of the
following two cases occurs:

  1. 1.

The Karush–Kuhn–Tucker conditions hold for problem (9) at $x^{\star}$.

  2. 2.

The point $x^{\star}$ is in the singular locus of $V$.

###### Proof.

If the Jacobian matrix $J(h)(x^{\star})$ has rank $n-\dim(V)$, Lemma 3 yields
that the Karush–Kuhn–Tucker conditions hold for problem (9) at $x^{\star}$.
Otherwise, we get $m_{n-d}(h)(x^{\star})=0$, and hence $x^{\star}$ is in the
singular locus of $V$. Here $m_{r}(h)(x)$ is the vector of the $r\times r$
minors of the Jacobian matrix $J(h)(x)$ associated with $h$. ∎

The following theorem shows in which varieties returned by Algorithm 1 the
local minimizers for problem (9) belong, and which types of optimality
conditions hold for problem (9) at these points:

######  Theorem 6.

Let $h_{0},h_{1},\dots,h_{l}$ be polynomials in ${\mathbb{R}}[x]$ such that
problem (9) with $h=(h_{1},\dots,h_{l})$ has a global minimizer $x^{\star}$.
Let $A$ and $B$ be as the output of Algorithm 1 with input $V=V(h)$. Then one
of the following two cases occurs:

  1. 1.

There exists a variety $U$ in $A$ with $q_{1},\dots,q_{r}\in{\mathbb{R}}[x]$
being the generators of $I(U)$ such that with $q=(q_{1},\dots,q_{r})$,
$x^{\star}$ is a global minimizer for problem

$\min_{x\in V(q)}h_{0}(x)$ (40)

and the Karush–Kuhn–Tucker conditions hold for problem (40) at $x^{\star}$.

  2. 2.

There exists a variety $U$ in $B$ defined by $q=(q_{1},\dots,q_{r})$ with
$q_{j}\in{\mathbb{R}}[x]$ such that $x^{\star}$ is a global minimizer for
problem (40).

###### Proof.

By the final statement of Lemma 14, $x^{\star}$ belongs to some variety $U$ in
$A\cup B$. By the first statement of Lemma 14, $U$ is an irreducible variety.
Let $q_{1},\dots,q_{r}\in{\mathbb{R}}[x]$ be the generators of the vanishing
ideal $I(U)$. Then $x^{\star}$ is also the global minimizer for problem (40)
with $q=(q_{1},\dots,q_{r})$. Assume that Karush–Kuhn–Tucker conditions do not
hold for problem (40) at $x^{\star}$. By Lemma 15, $x^{\star}$ is in the
singular locus $U^{\operatorname{sing}}$ of $U$. If $U$ has zero dimension
then $U$ is in $B$. Otherwise, we decompose $U^{\operatorname{sing}}$ into
irreducible components (Step 4 (b) of Algorithm 1). In this case, $x^{\star}$
belongs to some irreducible component of $U^{\operatorname{sing}}$. We repeat
the above process until obtaining only the zero-dimensional components. Hence
the result follows. ∎

######  Remark 7.

By Step 4 (b) of Algorithm 1 and the first statement of Lemma 2, each $U$ in
$A\cup B$ is an irreducible variety defined by polynomials built from the
higher-order partial derivatives of $h_{1},\dots,h_{l}$.

##  6 Exact polynomial optimization in the general case

The following algorithm enables us to obtain exact semidefinite programs to
compute the minimum value $h^{\star}$ of problem (9).

######  Algorithm 2.

Computing the minimum value $h^{\star}$ of problem (9).

  * •

Input: $h_{0},h_{1},\dots,h_{l}$ in ${\mathbb{R}}[x]$.

  * •

Output: $\bar{h}^{\star}$

  1. 1.

Let $A$ and $B$ be as the output of Algorithm 1 with input $V=V(h)$, where
$h=(h_{1},\dots,h_{l})$.

  2. 2.

Set $T:=\emptyset$.

  3. 3.

For each variety $U$ in $A$ with $q_{1},\dots,q_{r}\in{\mathbb{R}}[x]$ being
the generators of $I(U)$, do:

    1. (a)

Compute $t:=\rho_{\xi}(h_{0},\bar{q}_{\operatorname{KKT}})$ with
$q:=(q_{1},\dots,q_{r})$, $\bar{q}=(h_{0},q)$,
$d:=\max\\{\deg(h_{0})\,,\,\deg(q_{j})\,:\,j=1,\dots,r\\}$, $w$ being as in
(37) and

$\xi:=\frac{1}{2}\times b(n+r,2w,r+n+1)+d\,.$ (41)

    2. (b)

Set $T:=T\cup\\{t\\}$.

  4. 4.

For each variety $U$ in $B$ defined by $q:=(q_{1},\dots,q_{r})$ with
$q_{j}\in{\mathbb{R}}[x]$, do:

    1. (a)

Compute $t:=\rho_{\xi}(h_{0},q)$ with
$d:=\max\\{\deg(h_{0})\,,\,\deg(q_{j})\,:\,j=1,\dots,r\\}$, $w$ being as in
(38) and

$\xi:=\frac{1}{2}\times b(n,2w,r+1)+d\,.$ (42)

    2. (b)

Set $T:=T\cup\\{t\\}$.

  5. 5.

Set $\bar{h}^{\star}:=\min T$.

######  Remark 8.

Step 3 (a) and Step 4 (a) of Algorithm 2 are equivalent to solving exactly
semidefinite programs (of the form (29)). We refer the readers to the exact
algorithm of Henrion, Naldi, and Safey El Din in [19] to solve semidefinite
programs. In addition, the set $T$ in Algorithm 2 might contain $\infty$ if
the polynomial optimization problem associated with some semidefinite program
in Step 3 (a) and Step 4 (a) has empty feasible set.

We state our main result in the following theorem:

######  Theorem 7.

Let $h_{0},h_{1},\dots,h_{l}\in{\mathbb{R}}_{d}[x]$. Let $h^{\star}$ be as in
problem (9) with $h=(h_{1},\dots,h_{l})$. Assume that problem (9) has a global
minimizer. Let $\bar{h}^{\star}$ be as the output of Algorithm 2 with input
$h_{0},h_{1},\dots,h_{l}$. Then $\bar{h}^{\star}=h^{\star}$.

###### Proof.

Let $x^{\star}$ be a global minimizer for problem (9). By Theorem 6, one of
the following two cases occurs:

  * •

Case 1: There exists a variety $U$ in $A$ with
$q_{1},\dots,q_{r}\in{\mathbb{R}}[x]$ being the generators of $I(U)$ such that
$x^{\star}$ is a global minimizer for problem (40) with
$q=(q_{1},\dots,q_{r})$ and the Karush–Kuhn–Tucker conditions hold for problem
(40) at $x^{\star}$. By Theorem 3, we get
$\rho_{\xi}(h_{0},\bar{q}_{\operatorname{KKT}})=h^{\star}$ with
$\bar{q}=(h_{0},q)$,
$d:=\max\\{\deg(h_{0})\,,\,\deg(q_{j})\,:\,j=0,\dots,r\\}$, $w$ being as in
(37) and $\xi$ being as in (41).

  * •

Case 2: There exists a variety $U$ in $B$ defined by $q=(q_{1},\dots,q_{r})$
with $q_{j}\in{\mathbb{R}}[x]$ such that $x^{\star}$ is a global minimizer for
problem (40). By Theorem 4, we get $\rho_{\xi}(h_{0},q)=h^{\star}$ with
$d:=\max\\{\deg(h_{0})\,,\,\deg(q_{j})\,:\,j=0,\dots,r\\}$, $w$ being as in
(38) and $\xi$ being as in (42).

Hence the result follows due to steps 3, 4 and 5 of Algorithm 2 (as well as
Remark 4). ∎

Let $\|\cdot\|_{2}$ denote the $l_{2}$-norm of a real vector. Then
$\|x\|_{2}^{2}=x_{1}^{2}+\dots+x_{n}^{2}$ is a polynomial in $x$.

######  Remark 9.

To find a global minimizer for problem (9), we apply Algorithm 2 and the
adding-spherical-constraints method in [36, Section 4.3] as follows: Compute
the minimum value $h^{\star}$ for problem (9) by using Algorithm 2. Setting
$\bar{h}=(h,h_{0}-h^{\star})$ implies that $V(\bar{h})$ is the set of global
minimizers for problem (9). We assume that $V(\bar{h})$ is non-empty and find
a point $x^{\star}$ in $V(\bar{h})$. Let $(a^{(t)})_{t=0}^{n}$ be a finite
sequence of points in ${\mathbb{R}}^{n}$ such that
$a^{(t)}-a^{(0)},\,t=1,\dots,n$ are linearly independent in
${\mathbb{R}}^{n}$. We use Algorithm 2 to compute the following values:

$\begin{array}[]{l}\xi_{0}:=\min\\{\|x-a^{(0)}\|_{2}^{2}\,:\,x\in
V(\bar{h})\\}\,,\\\ \xi_{t}:=\min\\{\|x-a^{(t)}\|_{2}^{2}\,:\,x\in
V(\bar{h},b_{0},\dots,b_{t-1})\\}\,,\,t=1,\dots,n\,.\end{array}$ (43)

where $b_{r}=\xi_{r}-\|x-a^{(r)}\|_{2}^{2}$. Then there exists a unique real
point $x^{\star}$ in $V(\bar{h},b_{0},\dots,b_{n})$ which satisfies the non-
singular linear system of equations

$(a^{(t)}-a^{(0)})^{\top}x^{\star}=-\frac{1}{2}(\xi_{t}-\xi_{0}+\|a^{(0)}\|_{2}^{2}-\|a^{(t)}\|_{2}^{2}),\
t=1,\dots,n\,.$ (44)

We illustrate Algorithm 2 in the following example, which is based on [33,
Example 18]:

######  Example 4.

Let $n=5$, $h_{0}=x_{1}+x_{2}$, $h_{1}=x_{1}^{5}-x_{3}^{2}$,
$h_{2}=x_{2}^{5}-x_{4}^{2}$, and $h_{3}=-x_{1}x_{2}-x_{5}^{2}$ be as the input
of Algorithm 2. Let $h^{\star}$ be as in problem (9) with
$h=(h_{1},\dots,h_{l})$. Then it is not hard to prove that $h^{\star}=0$. In
Step 1 of Algorithm 2, we obtain

$A=\\{V(q^{(1)}),V(q^{(2)})\\}\quad\text{ and }\quad B=\\{V(q^{(3)})\\}\,,$
(45)

where $q^{(1)}:=(x_{5},x_{4},x_{2},x_{1}^{5}-x_{3}^{2})$,
$q^{(2)}:=(x_{5},x_{3},x_{2}^{5}-x_{4}^{2},x_{1})$ and
$q^{(3)}:=(x_{1},x_{2},x_{3},x_{4},x_{5})$. For $j=1,2$, letting
$\bar{q}^{(j)}:=(h_{0},q^{(j)})$ gives
$V(\bar{q}^{(j)}_{\operatorname{KKT}})=\emptyset$. Indeed, for any
$\lambda\in{\mathbb{R}}^{4}$, we get

$\begin{array}[]{rl}&\nabla h_{0}(x)-\sum_{i=1}^{4}\lambda_{j}\nabla
q^{(1)}_{i}(x)=\begin{bmatrix}1-5\lambda_{4}x_{1}^{4}\\\ 1-\lambda_{3}\\\
2\lambda_{4}x_{3}\\\ -\lambda_{2}\\\ -\lambda_{1}\end{bmatrix}\,,\\\ \\\
&\nabla h_{0}(x)-\sum_{i=1}^{4}\lambda_{j}\nabla
q^{(2)}_{i}(x)=\begin{bmatrix}1-\lambda_{4}\\\ 1-5\lambda_{3}x_{2}^{4}\\\
-\lambda_{2}\\\ 2\lambda_{3}x_{4}\\\ -\lambda_{1}\end{bmatrix}\,.\end{array}$
(46)

Then $\bar{q}^{(1)}_{\operatorname{KKT}}(x)=0$ implies that
$x_{1}^{5}=x_{3}^{2}$, $1-5\lambda_{4}x_{1}^{4}=2\lambda_{4}x_{3}=0$, which is
impossible. In addition, $\bar{q}^{(2)}_{\operatorname{KKT}}(x)=0$ implies
that $x_{2}^{5}=x_{4}^{2}$, $1-5\lambda_{3}x_{2}^{4}=2\lambda_{3}x_{4}=0$,
which is impossible. For $j=1,2$, since
$V(\bar{q}^{(j)}_{\operatorname{KKT}})=\emptyset$, it holds that
$\rho_{\xi}(h_{0},\bar{q}^{(j)}_{\operatorname{KKT}})=\infty$ for sufficient
large $\xi\in{\mathbb{N}}$. Since $V(q^{(3)})=\\{0\\}$, we get
$\rho_{\xi}(h_{0},q^{(3)})=0$ for sufficient large $\xi\in{\mathbb{N}}$. Thus
we eventually obtain $T=\\{\infty,0\\}$, yielding $\bar{h}^{\star}=\min
T=0=h^{\star}$.

######  Remark 10.

Instead of using semidefinite programming, we can rely entirely on symbolic
computations [31] to find the minimum value $h^{\star}$ of problem (9) when
this problem has a global minimizer $x^{\star}$. (Developed by the first
author, the method in [31] depends on the computations of real radical
generators and Groebner bases. It allows us to obtain univariate polynomials
defining the Zariski closure of the image of a basic semi-algebraic set $S$
under a polynomial $f$.) To do this, let $A$ and $B$ be as the output of
Algorithm 1 with input $V=V(h)$. By Theorem 5, for each $U$ in $A$ with
$q_{1}^{U},\dots,q_{r_{U}}^{U}\in{\mathbb{R}}[x]$ being the generators of
$I(U)$, $h_{0}(V(\bar{q}_{\operatorname{KKT}}^{U}))$ has finitely many values,
where $\bar{q}^{U}=(h_{0},q_{1}^{U},\dots,q_{r_{U}}^{U})$. Moreover, for each
$U$ in $B$, $h_{0}(U)$ has finitely many values. By using [31, Algorithm 1],
we can compute all values of $h_{0}(V(\bar{q}_{\operatorname{KKT}}^{U}))$
(resp. $h_{0}(U)$), for each $U$ in $A$ (resp. $B$). Let $h^{\star}_{U}$ be
the smallest value in $h_{0}(V(\bar{q}_{\operatorname{KKT}}^{U}))$ (resp.
$h_{0}(U)$), for each $U$ in $A$ (resp. $B$). Note that for each $U$ in $A$
(resp. $B$), we have $V(\bar{q}_{\operatorname{KKT}}^{U})\subset
V(h)\times{\mathbb{R}}^{r_{U}}$ (resp. $U\subset V(h)$), so that
$h^{\star}_{U}\geq h^{\star}$. Theorem 6 says that $x^{\star}$ belongs to the
projection of some $V(\bar{q}_{\operatorname{KKT}}^{U})$ with $U$ in $A$ or
$x^{\star}$ belongs to some $U$ in $B$, which implies that
$h^{\star}=\min\\{h^{\star}_{U}\,:\,U\in A\cup B\\}$.

######  Remark 11.

If we replace Step 2 of Algorithm 1 with “Set $r:=1$ and $U_{1}:=U$.”, then
all results so far still hold. However, the polynomials defining $U_{1}$
possibly have very high degrees in this case (as shown in Examples 2, 3 and
4).

######  Remark 12.

The result of Theorem 7 requires the attainability of the infimum value
$h^{\star}$. In [35], the first author proves that every polynomial
optimization problem of the form (9) with finite infimum value $h^{\star}$ can
be symbolically transformed to an equivalent problem in one-dimensional space
with attained optimal value $h^{\star}$. To do this, he uses quantifier
elimination, and algebraic algorithms that rely on the fundamental theorem of
algebra and the greatest common divisor. Let $d$ be the upper bound on the
degrees of $h_{j}$. His symbolic algorithm has complexity $O(d^{O(n)})$ to
produce the objective and constraint polynomials of degree at most $d^{O(n)}$
for the equivalent problem.

The following corollary states the equivalence of polynomial optimization
problems and semidefinite programs:

######  Corollary 1.

Let $h_{0},h_{1},\dots,h_{l}\in{\mathbb{R}}_{d}[x]$. Let $h^{\star}$ be as in
problem (9) with $h=(h_{1},\dots,h_{l})$. Then there is a symbolic algorithm
with input $h_{0},\dots,h_{l}$ which produces a finite sequence of
semidefinite programs with minimum values $(\zeta_{r})_{r=1}^{s}$ such that
(9) is equivalent to the semidefinite program with smallest minimum value
$\zeta_{\bar{r}}=\min\limits_{r=1,\dots,s}\zeta_{r}$.

###### Proof.

If $h^{\star}\in\\{-\infty,\infty\\}$, it is not hard to construct a
semidefinite program with infimum value $h^{\star}$. If $h^{\star}$ is finite
but not attained, we can transform problem (9) to an equivalent polynomial
optimization problem with attained minimum value $h^{\star}$ thanks to Remark
12. Let us consider the remaining case. Assume that (9) has a global
minimizer. Theorem 7 implies that Algorithm 2 produces finitely many
semidefinite programs whose smallest minimum value is exactly $h^{\star}$.
Hence the result follows. ∎

######  Remark 13.

The paper (particularly Corollary 1) provides a theoretical overview of why
every general polynomial optimization problem can be solved with a sequence of
semidefinite programs obtained recursively. However, our method should be far
from efficient in practice because of the vast bounds (41) and (42) in
Algorithm 2. This is unavoidable since we use symbolic computation to obtain
the result. Thus our method cannot be expected to be as efficient as
approximation methods.

##  7 Equivalence of hyperpolic programs and semidefinite programs

A polynomial $f$ in ${\mathbb{R}}[x]$ is called _hyperbolic_ w.r.t.
$e=(e_{1},\dots,e_{n})\in{\mathbb{R}}^{n}$ if $f(e)\neq 0$ and for all
$a\in{\mathbb{R}}^{n}$, the univariate polynomial $t\mapsto f(te-a)$ has only
real roots.

Given a polynomial $f$ hyperbolic w.r.t. $e\in{\mathbb{R}}^{n}$, we define the
set

$\Lambda_{+}(f,e):=\\{a\in{\mathbb{R}}^{n}\,:\,f(te-a)=0\Rightarrow t\geq
0\\}\,,$ (47)

which is called the hyperbolic cone of $f$ in direction $e$.

As shown by Gårding in [13], $\Lambda_{+}(f,e)$ is a basic semi-algebraic set.
We state in the following lemma a weaker result than this statement:

######  Lemma 16.

Let $f$ be a hyperbolic polynomial in ${\mathbb{R}}[x]$ w.r.t.
$e\in{\mathbb{R}}^{n}$. Then $\Lambda_{+}(f,e)$ is the projection of a basic
semi-algebraic set defined by polynomials built from $e$ and the coefficients
of $f$.

###### Proof.

Let $t$ be a single variable. Set $d:=\deg(f)$ and $\varphi_{a}(t)=f(te-a)$.
Then $\varphi_{a}$ is a polynomial in $t$ of degree at most $d$. Denote by
$\varphi_{a}^{(j)}$, $j=0,\dots,d$, the coefficient of $\varphi_{a}$
associated with monomial $t^{j}$, $j=0,\dots,d$, respectively. Then each
mapping $a\mapsto\varphi_{a}^{(j)}$ is a polynomial in $a$. Let
$a\in\Lambda_{+}(f,e)$. Then identity polynomial $t$ is non-negative on the
zero-dimensional algebraic variety $V(\varphi_{a})$. Assume
$V(\varphi_{a})=\\{t_{1},\dots,t_{r}\\}$ for some $r\in{\mathbb{N}}$. Then it
holds that $t_{j}\geq 0$, $j=1,\dots,r$. Since $\varphi_{a}$ has degree at
most $d$, we get $r\leq d$. Letting

$p_{j}(t):=\prod\limits_{\begin{array}[]{cc}\scriptstyle i=1\\\ \scriptstyle
i\neq j\end{array}}^{r}\frac{t-t_{i}}{t_{j}-t_{i}}\,,\,j=1,\dots,r\,,$ (48)

we obtain $p_{j}(t_{i})=\delta_{ij}$. Setting
$\sigma=\sum_{j=1}^{r}t_{j}p_{j}^{2}$ gives $\sigma\in\Sigma^{2}_{r-1}[t]$.
Moreover, $t-\sigma$ vanishes on $V(\varphi_{a})$. Since $r\leq d$, $\sigma$
has degree at most $2(d-1)$. It implies that both $\varphi_{a}$ and $\sigma$
have degrees at most $2d$. Set $\xi:=\frac{1}{2}\times b(1,2d,2)$ and
$s:=2\lfloor\xi/(2d)\rfloor$, where $b(\cdot)$ is defined as in (20). By Lemma
9, it holds that

$\exists\sigma\in\Sigma^{2}_{d-1}[t]\,:\,-(t-\sigma)^{s}\in\Sigma^{2}_{\xi}[t]+I_{\xi}(\varphi_{a})[t]$
(49)

Note that $s$ and $\xi$ only depend on $d$. From this, (49) is equivalent to
“$t\geq 0$ on $V(\varphi_{a})$”. Moreover, (49) can be written as

$\begin{cases}\exists G_{j}\succeq 0\,,\,\exists
u\in{\mathbb{R}}^{2(\xi-d)+1}\,:\\\
-(t-v_{d-1}^{\top}G_{0}v_{d-1})^{s}=v_{\xi}^{\top}G_{1}v_{\xi}+v_{2(\xi-d)}^{\top}u\varphi_{a}\,,\end{cases}$
(50)

where $v_{\eta}$ is the vector of monomials in $t$ up to degree $\eta$. It not
hard to see that (50) is equivalent to

$\begin{cases}\exists G_{0}\in{\mathbb{R}}^{d\times d}\,,\,\exists
G_{1}\in{\mathbb{R}}^{(\xi+1)\times(\xi+1)}\,,\,\exists
u\in{\mathbb{R}}^{2(\xi-d)+1}\,:\\\ G_{j}^{\top}=G_{j}\,,\,F(G_{j})\geq
0\,,\,H(G_{0},G_{1},u,\varphi_{a}^{(0)},\dots,\varphi_{a}^{(d)})=0\,,\end{cases}$
(51)

where $F$ denotes the vector of principal minors of a matrix, and $H$ is a
vector of polynomials. Since $\varphi_{a}^{(j)}$ is a polynomial in $a$, (51)
is equivalent to that $a$ is in the projection of a basic semi-algebraic set
on the coordinates w.r.t. $a$, which yields the result. ∎

We close the paper by stating what would be a consequence of the generalized
Lax conjecture (see, e.g., [2, Remark 1.7]):

######  Corollary 2.

Let $f$ be a hyperbolic polynomial in ${\mathbb{R}}[x]$ w.r.t.
$e\in{\mathbb{R}}^{n}$. Consider the following hyperbolic program:

$\begin{array}[]{rl}\inf\limits_{x\in{\mathbb{R}}^{n}}&c^{\top}x\\\
\text{s.t.}&Ax=b\,,\,x\in\Lambda_{+}(f,e)\,,\end{array}$ (52)

where $A\in{\mathbb{R}}^{m\times n}$, $b\in{\mathbb{R}}^{m}$ and
$c\in{\mathbb{R}}^{n}$ are given. Then there is a symbolic algorithm with
input $A,b,c,f,e$ which produces a sequence of semidefinite programs with
minimum values $(\zeta_{r})_{r=1}^{s}$ such that (52) is equivalent to the
semidefinite program with smallest minimum value
$\zeta_{\bar{r}}=\min\limits_{r=1,\dots,s}\zeta_{r}$.

###### Proof.

Let $h^{\star}$ be the infimum value of problem (52). Thanks to Lemma 16, (52)
can be written as polynomial optimization problem (9) with minimum value
$h^{\star}$ (see Remark 1). Note that the objective and constraint polynomials
$h_{0},\dots,h_{l}$ are built from $A,b,c,f,e$. By Corollary 1, there is a
symbolic algorithm with input $h_{0},\dots,h_{l}$ which produces a finite
sequence of semidefinite programs such that (9) is equivalent to a
semidefinite program of the smallest minimum value. Hence the result follows.
∎

######  Remark 14.

The framework of Corollary 2 provides a constructive way to obtain an
equivalent semidefinite program for the hyperbolic program (52) with given
$A,b,c,f,e$. However, it has yet to easily be seen that the result of
Corollary 2 provides a solution to the generalized Lax conjecture. It is
because the equivalence of hyperbolic and semidefinite programs might not
directly imply the equality of their feasible sets.

#### Acknowledgements.

The authors would like to thank Bernard Mourrain, Markus Schweighofer, and
Claus Scheiderer for their valuable discussions about this paper.

The first author was supported by the funding from ANITI. The second author
was supported by the Tremplin ERC Stg Grant ANR-18-ERC2-0004-01 (T-COPS
project) and by the FMJH Program PGMO (EPICS project) and EDF, Thales, Orange
et Criteo. This work has benefited from the European Union’s Horizon 2020
research and innovation programme under the Marie Sklodowska-Curie Actions,
grant agreement 813211 (POEMA) as well as from the AI Interdisciplinary
Institute ANITI funding, through the French “Investing for the Future PIA3”
program under the Grant agreement n∘ANR-19-PI3A-0004.

## References

  * [1] S. Albrecht and M. Ulbrich.  Mathematical programs with complementarity constraints in the context of inverse optimal control for locomotion.  Optimization Methods and Software, 32(4):670–698, 2017.
  * [2] N. Amini.  Spectrahedrality of hyperbolicity cones of multivariate matching polynomials.  Journal of Algebraic Combinatorics, 50(2):165–190, 2019.
  * [3] L. Baldi and B. Mourrain.  Exact Moment Representation in Polynomial Optimization.  arXiv preprint arXiv:2012.14652, 2020.
  * [4] L. Baldi and B. Mourrain.  Computing real radicals by moment optimization.  In Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation, pages 43–50, 2021.
  * [5] E. Becker and R. Neuhaus.  Computation of real radicals of polynomial ideals.  In Computational algebraic geometry, pages 1–20. Springer, 1993\.
  * [6] R. Bellman and K. Fan.  On systems of linear inequalities in Hermitian matrix variables.  Convexity, 7:1–11, 1963.
  * [7] M. A. Bucero and B. Mourrain.  Exact relaxation for polynomial optimization on semi-algebraic sets.  arXiv preprint arXiv:1307.6426, 2013.
  * [8] S. Burgdorf, C. Scheiderer, and M. Schweighofer.  Pure states, nonnegative polynomials and sums of squares.  Commentarii Mathematici Helvetici, 87(1):113–140, 2012.
  * [9] M. Coste.  An introduction to semialgebraic geometry, 2000.
  * [10] D. Cox, J. Little, and D. OShea.  Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra.  Springer Science & Business Media, 2013.
  * [11] 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.
  * [12] R. M. Freund.  Optimality conditions for constrained optimization problems.  Massachusetts Institute of Technology (available at: link), 2004\.
  * [13] L. Gårding.  An inequality for hyperbolic polynomials.  Journal of Mathematics and Mechanics, pages 957–965, 1959.
  * [14] P. Gianni, B. Trager, and G. Zacharias.  Gröbner bases and primary decomposition of polynomial ideals.  Journal of Symbolic Computation, 6(2-3):149–167, 1988.
  * [15] M. X. Goemans and D. P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  Journal of the ACM (JACM), 42(6):1115–1145, 1995.
  * [16] O. Güler.  Hyperbolic polynomials and interior point methods for convex programming.  Mathematics of Operations Research, 22(2):350–377, 1997.
  * [17] J. D. Hauenstein and C. W. Wampler.  Isosingular sets and deflation.  Foundations of Computational Mathematics, 13(3):371–403, 2013.
  * [18] J. W. Helton and V. Vinnikov.  Linear matrix inequality representation of sets.  Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 60(5):654–674, 2007.
  * [19] D. Henrion, S. Naldi, and M. Safey El Din.  Exact algorithms for semidefinite programs with degenerate feasible set.  In Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, pages 191–198, 2018.
  * [20] D. Hilbert.  Über die Darstellung Definiter Formen als Summe von Formenquadraten.  Mathematische Annalen, 32(3):342–350, 1888.
  * [21] H. Hironaka.  Resolution of Singularities of an Algebraic Variety Over a Field of Characteristic Zero: I.  Annals of Mathematics, pages 109–203, 1964.
  * [22] H. Hironaka.  Resolution of singularities of an algebraic variety over a field of characteristic zero: II.  Annals of Mathematics, pages 205–326, 1964.
  * [23] J.-L. Krivine.  Anneaux préordonnés.  Journal d’analyse mathématique, 12(1):307–326, 1964.
  * [24] M. Kummer.  Determinantal representations and bézoutians.  Mathematische Zeitschrift, 285(1):445–459, 2017.
  * [25] M. Kummer, S. Naldi, and D. Plaumann.  Spectrahedral representations of plane hyperbolic curves.  Pacific Journal of Mathematics, 303(1):243–263, 2019.
  * [26] M. Kummer, D. Plaumann, and C. Vinzant.  Hyperbolic polynomials, interlacers, and sums of squares.  Mathematical Programming, 153(1):223–245, 2015.
  * [27] P. Lairez and M. Safey El Din.  Computing the dimension of real algebraic sets.  In Proceedings of the 2021 on International Symposium on Symbolic and Algebraic Computation, pages 257–264, 2021.
  * [28] J. B. Lasserre.  Global optimization with polynomials and the problem of moments.  SIAM Journal on optimization, 11(3):796–817, 2001.
  * [29] J. B. Lasserre.  An introduction to polynomial and semi-algebraic optimization, volume 52.  Cambridge University Press, 2015.
  * [30] 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.
  * [31] N. H. A. Mai.  A symbolic algorithm for exact polynomial optimization strengthened with Fritz John conditions.  arXiv preprint arXiv:2206.02643, 2022.
  * [32] N. H. A. Mai.  Complexity for exact polynomial optimization strengthened with Fritz John conditions.  arXiv e-prints, pages arXiv–2205, 2022.
  * [33] N. H. A. Mai.  Exact polynomial optimization strengthened with Fritz John conditions.  arXiv preprint arXiv:2205.04254, 2022.
  * [34] N. H. A. Mai.  A nichtnegativstellensatz on singular varieties under the denseness of regular loci.  arXiv preprint arXiv:2211.12440, 2022.
  * [35] N. H. A. Mai.  Semi-algebraic description of the closure of the image of a semi-algebraic set under a polynomial.  arXiv preprint arXiv:2210.13933, 2022.
  * [36] 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.
  * [37] 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.
  * [38] M. Marshall.  Representations of non-negative polynomials, degree bounds and applications to optimization.  Canadian Journal of Mathematics, 61(1):205–221, 2009.
  * [39] S. Naldi and D. Plaumann.  Symbolic computation in hyperbolic programming.  Journal of Algebra and Its Applications, 17(10):1850192, 2018.
  * [40] T. Netzer, D. Plaumann, and A. Thom.  Determinantal representations and the hermite matrix.  Michigan Mathematical Journal, 62(2):407–420, 2013.
  * [41] T. Netzer and A. Thom.  Polynomials with and without determinantal representations.  Linear algebra and its applications, 437(7):1579–1595, 2012.
  * [42] R. Neuhaus.  Computation of real radicals of polynomial ideals—ii.  Journal of Pure and Applied Algebra, 124(1-3):261–280, 1998.
  * [43] J. Nie.  An exact Jacobian SDP relaxation for polynomial optimization.  Mathematical Programming, 137(1):225–255, 2013.
  * [44] J. Nie.  Polynomial optimization with real varieties.  SIAM Journal On Optimization, 23(3):1634–1646, 2013.
  * [45] J. Nie.  Optimality conditions and finite convergence of Lasserre’s hierarchy.  Mathematical programming, 146(1-2):97–121, 2014.
  * [46] OSCAR – Open Source Computer Algebra Research system, Version 0.9.0, 2022.
  * [47] T. S. Pham and H. H. Vui.  Genericity in polynomial optimization, volume 3.  World Scientific, 2016.
  * [48] M. Putinar.  Positive polynomials on compact semi-algebraic sets.  Indiana University Mathematics Journal, 42(3):969–984, 1993.
  * [49] C. Scheiderer.  Sums of squares of regular functions on real algebraic varieties.  Transactions of the American Mathematical Society, 352(3):1039–1069, 2000.
  * [50] C. Scheiderer.  Sums of squares on real algebraic curves.  Mathematische zeitschrift, 245(4):725–760, 2003.
  * [51] C. Scheiderer.  Sums of squares on real algebraic surfaces.  manuscripta mathematica, 119(4):395–410, 2006.
  * [52] K. Schmüdgen.  The K-moment problem for compact semi-algebraic sets.  Mathematische Annalen, 289(1):203–206, 1991.
  * [53] M. Schweighofer.  Spectrahedral relaxations of hyperbolicity cones.  arXiv preprint arXiv:1907.13611, 2019.
  * [54] A. Sheffer.  Polynomial methods and incidence theory, volume 197.  Cambridge University Press, 2022.
  * [55] M. Sitharam, A. S. John, and J. Sidman.  Handbook of geometric constraint systems principles.  Chapman and Hall/CRC, 2018.
  * [56] K. Smith, L. Kahanpää, P. Kekäläinen, and W. Traves.  An invitation to algebraic geometry.  Springer Science & Business Media, 2004.