∎

11institutetext:  Vu Trung Hieu<EMAIL_ADDRESS>22institutetext:
Department of Mathematical Sciences, Norwegian University of Science and
Technology
7491, Trondheim, Norway
Akiko Takeda<EMAIL_ADDRESS><EMAIL_ADDRESS>33institutetext: Department of Mathematical Informatics, The University of
Tokyo
113-8656, Tokyo, Japan
Center for Advanced Intelligence Project, RIKEN
103-0027, Tokyo, Japan

# Computing local minimizers in polynomial optimization under genericity
conditions

Vu Trung Hieu  Akiko Takeda

(Received: date / Accepted: date)

###### Abstract

In this paper, we aim at computing all local minimizers of a polynomial
optimization problem under genericity conditions. By using a technique in
computer algebra, we provide a univariate representation for the set of local
minimizers. In particular, for an unconstrained problem, the coordinates of
all local minimizers can be represented by several univariate polynomial
equalities and one univariate polynomial matrix inequality. We also develop
the technique for constrained problems having equality constraints. Based on
the above technique, we design algorithms to enumerate the local minimizers.
At the end of the paper, we provide some experimental examples.

###### Keywords:

local minimizer second-order optimality condition zero-dimensional ideal
radical of an ideal reduced Gröbner basis

###### MSC:

14P05 13P10 90C23

##  1 Introduction

We denote by $\operatorname{\mathbb{R}}$ the field of real numbers and by $x$
the $n$-tuple of variables $(x_{1},\dots,x_{n})$. Let $f,h_{1},\dots,h_{m}$ be
$m+1$ polynomials in $n$ variables $x$ with real coefficients. The real
algebraic set of $h:=(h_{1},\dots,h_{m})$ is denoted by
$V_{\operatorname{\mathbb{R}}}(h)$,

$V_{\operatorname{\mathbb{R}}}(h)=\\{x\in{\operatorname{\mathbb{R}}}^{n}:h_{1}(x)=\dots=h_{m}(x)=0\\}.$

A point $u\in V_{\operatorname{\mathbb{R}}}(h)$ is a local minimizer of $f$
over $V_{\operatorname{\mathbb{R}}}(h)$ if there exists $\varepsilon>0$ such
that $f(u)\leq f(x)$ for any $x\in V_{\operatorname{\mathbb{R}}}(h)$
satisfying $\|x-u\|<\varepsilon$. Then, one says that the value $f(u)$ is a
local minimum of $f$ over $V_{\operatorname{\mathbb{R}}}(h)$.

The set of all local minimizers of $f$ over $V_{\operatorname{\mathbb{R}}}(h)$
may have infinitely many points; for example, the set of local minimizers of
$f=(x_{1}-x_{2})^{2}$ over $\operatorname{\mathbb{R}}^{2}$ is the line
$\\{(x_{1},x_{2})\in\operatorname{\mathbb{R}}^{2}:x_{1}=x_{2}\\}$. However,
when $f,h$ are generic, according to Nie’s result (nie2014optimality, ,
Theorem 1.2), the set has finitely many points. For such cases, in this paper,
we introduce a method to compute all points of the set.

We would like to remark that, in the literature of polynomial optimization,
most work is for computing global minimums or infimums. Computing global
minimums in polynomial optimization is usually based on sum of squares
relaxations, for example, by Lasserre lasserre2001global , Parrilo
parrilo2003semidefinite , Parrilo and Sturmfels parrilo2001minimizing , and
Nie, Demmel and Sturmfels nie2006 . We refer monographs by Lasserre
lasserre2009moments  or Laurent laurent2009  to this approach.

Meanwhile, local minimums and minimizers are important not only in theory but
also in applications nie2015hierarchy . For example, in modern computational
chemistry, the potential energy surface is a fundamental concept to describe
the energy of a chemical system as a function of its geometry. The local
minimizers correspond to stable structure, from which one may calculate energy
barriers and minimum-energy paths that describe chemical reactivity, and there
are various papers (e.g., he2015 ; morrow2021 ) that attempt to find as many
local minimizers as possible. There is also a demand for methods to enumerate
local minimizers in machine learning. Some nonconvex machine learning models
such as deep learning kawaguchi2016  and low-rank matrix optimization problems
based on Burer-Monteiro factorization yalcin2022  are known to have no
spurious local minimizers, which indicates that there are no local minimizers
that have larger objective values than the optimal value, i.e., every local
minimizer is a global minimizer. The next step in the research stream would be
to enumerate local minimizers in order to determine which of multiple
minimizers achieve the best prediction performance. Indeed, there is some
study mehta2022  enumerating minimizers of a deep learning model.

Characterizations of local minimizers of quadratic functions over Euclidean
balls, spheres or polyhedrons have been investigated, for example, in
martinez1994local ; phu2001stability . As shown recently in
ahmadi2022complexity  by Ahmadi and Zhang, the problem of deciding whether a
quadratic function has a local minimizer over polyhedron is NP-hard. Before
that, Pardalos and Schnitger proved that it is NP-hard to test whether a given
point is a local minimizer of constrained quadratic programming
pardalos1988checking . Recently, some characterizations of local minimizers of
semi-algebraic functions from the viewpoint of tangencies are discussed in
pham2020local  by Pham. Nie in nie2015hierarchy  introduces a method to
computing the hierarchy of critical values and local minimums of a polynomial
optimization problem based on the second-order optimality conditions and semi-
definite relaxations.

Contributions. This paper studies how to compute all local minimizers of
polynomial optimization problems under generic conditions without using semi-
definite relaxations.

  * •

Unconstrained problem. We consider the unconstrained problem given by a
polynomial $f$. Under genericity conditions, Theorem 3.1 shows a necessary and
sufficient condition for local optimality. Relying on this condition, we can
obtain a representation for the set of local minimizers that includes $n+1$
univariate polynomial equalities and one univariate polynomial matrix
inequality. Based on the proof, we design an algorithm to enumerate all local
minimizers of $f$. Interestingly, if the infimum of $f$ over
$\operatorname{\mathbb{R}}^{n}$ is reached, in Theorem 3.2 we prove that this
value can be computed equivalently to a univariate optimization problem.

  * •

Constrained problem. We also consider the problem of computing local
minimizers of a polynomial $f$ with $m$ equality constraints under genericity
conditions. We provide a univariate representation for the set of local
minimizers and design an algorithm to compute this set.

  * •

Implementation. The algorithms are implemented in Maple. We provide
experimental results on Rosenbrock functions with both unconstrained and
constrained cases.

The remaining part of this paper consists of four sections. Section 2 gives
some definitions, notations, and auxiliary results on computational
commutative algebra and optimization theory. Section 3 establishes results
concerning the unconstrained case. Results on constrained cases are shown in
Section 4. The last section is about experimental results, namely Section 5.

##  2 Preliminaries

This section recalls basic notions and results from computational commutative
algebra and optimization theory; Further details can be found in cox2013  and
bertsekas2nd .

###  2.1 Zero-dimensional ideals and the Shape Lemma

We denote by $\operatorname{\mathbb{C}}$ the field of complex numbers that is
the algebraic closure of the field $\operatorname{\mathbb{R}}$. The ring of
all polynomials in variables $x$ with real coefficients is denoted by
$\operatorname{\mathbb{R}}[x]$. An additive subgroup
$\operatorname{\mathcal{I}}$ of $\operatorname{\mathbb{R}}[x]$ is said to be
an ideal of $\operatorname{\mathbb{R}}[x]$ if
$pg\in\operatorname{\mathcal{I}}$ for any $p\in\operatorname{\mathcal{I}}$ and
$g\in\operatorname{\mathbb{R}}[x]$. Given $p_{1},\dots,p_{s}$ in
$\operatorname{\mathbb{R}}[x]$, we denote by $\left\langle
p_{1},\dots,p_{s}\right\rangle$ the ideal generated by $p_{1},\dots,p_{s}$. If
$\operatorname{\mathcal{I}}$ is an ideal of $\operatorname{\mathbb{R}}[x]$
then, according to Hilbert’s basis theorem (see, for example Theorem 4 in
(cox2013, , Chapter 2, §5)), there exist
$p_{1},\dots,p_{s}\in\operatorname{\mathbb{R}}[x]$ such that
$\operatorname{\mathcal{I}}=\left\langle p_{1},\dots,p_{s}\right\rangle$.

Let $\operatorname{\mathcal{I}}$ be an ideal of
$\operatorname{\mathbb{R}}[x]$. The complex algebraic variety associated to
$\operatorname{\mathcal{I}}$ is defined as

$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}):=\\{x\in{\operatorname{\mathbb{C}}}^{n}:g(x)=0,\forall
g\in\operatorname{\mathcal{I}}\\}.$

The real algebraic variety associated to $\operatorname{\mathcal{I}}$ is
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}})=V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})\cap\operatorname{\mathbb{R}}^{n}$.
Recall that the ideal $\operatorname{\mathcal{I}}$ is zero-dimensional if the
cardinality of $V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})$,
denoted by $\\#V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})$, is
finite. The radical of $\operatorname{\mathcal{I}}$, denoted by
$\operatorname{rad}(\operatorname{\mathcal{I}})$, is the following set:

$\\{g\in\operatorname{\mathbb{R}}[x]:g^{k}\in\operatorname{\mathcal{I}}\text{
for some }k\in\operatorname{\mathbb{N}}\\}.$

The set $\operatorname{rad}(\operatorname{\mathcal{I}})$ is also an ideal that
contains $\operatorname{\mathcal{I}}$. One says that the ideal
$\operatorname{\mathcal{I}}$ is radical if
$\operatorname{\mathcal{I}}=\operatorname{rad}(\operatorname{\mathcal{I}})$.

The following lemma asserts that the radical of an ideal is radical; Moreover,
the complex (real) varieties of $\operatorname{\mathcal{I}}$ and its radical
are coincident, see, for example Lemma 5 and Theorem 7 in (cox2013, , Chapter
4, §2):

###### Lemma 1

Let $\operatorname{\mathcal{I}}$ be an ideal of
$\operatorname{\mathbb{R}}[x]$. Then,
$\operatorname{rad}(\operatorname{\mathcal{I}})$ is radical. Moreover, one has
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})=V_{\operatorname{\mathbb{C}}}(\operatorname{rad}(\operatorname{\mathcal{I}}))$,
hence
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}})=V_{\operatorname{\mathbb{R}}}(\operatorname{rad}(\operatorname{\mathcal{I}}))$.

Let $<$ be a monomial ordering on $\operatorname{\mathbb{R}}[x]$ and
$\operatorname{\mathcal{I}}\neq\\{0\\}$ be an ideal. We denote by
$\operatorname{LT}_{<}(\operatorname{\mathcal{I}})$ the set of all leading
terms $\operatorname{LT}_{<}(p)$ of $p\in\operatorname{\mathcal{I}}$, and by
$\left\langle\operatorname{LT}_{<}(\operatorname{\mathcal{I}})\right\rangle$
the ideal generated by the elements of
$\operatorname{LT}_{<}(\operatorname{\mathcal{I}})$. A subset
$G=\\{p_{1},\dots,p_{s}\\}$ of $\operatorname{\mathcal{I}}$ is said to be a
Gröbner basis of $\operatorname{\mathcal{I}}$ with restpect to the monomial
order $<$ if

$\left\langle\operatorname{LT}_{<}(p_{1}),\dots,\operatorname{LT}_{<}(p_{s})\right\rangle=\left\langle\operatorname{LT}_{<}(\operatorname{\mathcal{I}})\right\rangle.$

Note that every ideal in $\operatorname{\mathbb{R}}[x]$ has a Gröbner basis. A
Gröbner basis $G$ is reduced if the two following conditions hold: i) the
leading coefficient of $p$ is $1$, for all $p\in G$; ii) for all $p\in G$,
there are no monomials of $p$ lying in
$\left\langle\operatorname{LT}_{<}(G\setminus\\{p\\})\right\rangle$. Every
ideal $\operatorname{\mathcal{I}}$ has a unique reduced Gröbner basis. We
refer the reader to cox2013  for more details. Further, when the monomial
order $<$ is clear from the context, we omit as a subscript in the above
notation.

Let $\operatorname{\mathcal{I}}$ be a zero-dimensional and radical ideal in
$\operatorname{\mathbb{R}}[x]$, and $G$ be its reduced Gröbner basis with
respect to the lexicographical order
$x_{1}<_{\operatorname{lex}}\cdots<_{\operatorname{lex}}x_{n}$. One says that
$\operatorname{\mathcal{I}}$ is in shape position if $G$ has the following
shape:

$G=\\{w,x_{2}-v_{2},\dots,x_{n}-v_{n}\\},$ (2.1)

where $w,v_{2},\dots,v_{n}$ are polynomials in
$\operatorname{\mathbb{R}}[x_{1}]$ and $\deg
w=\\#V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})$.

The following lemma, named Shape Lemma, gives us a criteria for the shape
position of an ideal.

###### Lemma 2

(Shape Lemma, gianni89 ) Let $<_{\operatorname{lex}}$ be a lexicographic
monomial order in $\operatorname{\mathbb{R}}[x]$. Suppose that
$\operatorname{\mathcal{I}}$ is a zero-dimensional and radical ideal. If
points in $V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})$ have
distinct $x_{1}$-coordinates, then $\operatorname{\mathcal{I}}$ is in shape
position as in (2.1), where $v_{2},\dots,v_{n}$ are polynomials in
$\operatorname{\mathbb{R}}[x_{1}]$ of degrees at most
$\\#V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})-1$.

###  2.2 Local minimizers of unconstrained problems

Let $Q\in\operatorname{\mathbb{R}}^{n\times n}$ be a symmetric matrix. The
quadratic form associated to $Q$ is given by $p(x)=x^{T}Qx$, for
$x\in\operatorname{\mathbb{R}}^{n}$. Let
$K\subset\operatorname{\mathbb{R}}^{n}$ be a nonempty subset. One says that
$Q$ is positive semi-definite with respect to $K$, denoted by $Q\succeq_{K}0$,
if $p(x)\geq 0$ for all $x\in K$ and that $Q$ is positive definite with
respect to $K$, denoted by $Q\succ_{K}0$, if $p(x)>0$ for all $x\in K$ and
$x\neq 0$. One sees that, if $K$ is a cone, then checking positive semi-
definiteness (resp. positive definiteness) of $Q$ with respect to $K$ is
equivalent to checking positivity of the minimum of $p$ over the compact set
$K\cap\operatorname{\mathbb{S}}$, where $\operatorname{\mathbb{S}}$ is the
unit sphere in $\operatorname{\mathbb{R}}^{n}$. When
$K=\operatorname{\mathbb{R}}^{n}$, we say $Q$ is positive semi-definite (resp.
positive definite) and write $Q\succeq 0$ (resp. $Q\succ 0$) for short. It is
well-known that $Q\succeq 0$ (resp. $Q\succ 0$) if $Q$ has only non-negative
(resp. positive) eigenvalues.

Suppose that the entries of $Q$ are polynomials depending on a real variable
$t$. One says that $Q(t)\succeq_{K}0$ (resp. $Q(t)\succ_{K}0$) is a univariate
polynomial matrix inequality.

Let $f$ be a polynomial in $\operatorname{\mathbb{R}}[x]$. We consider the
problem of computing local minimizers of $f$ over
$\operatorname{\mathbb{R}}^{n}$. A point $x\in\operatorname{\mathbb{R}}^{n}$
is a critical point of $f$ over $\operatorname{\mathbb{R}}^{n}$ if it is a
real root of the system of the $n$ partial derivatives of $f$, i.e.:

$\left\\{\frac{\partial f}{\partial x_{1}}(x)=0\,,\cdots,\,\frac{\partial
f}{\partial x_{n}}(x)=0\right\\}.$

The gradient ideal of $f$, denoted by
$\operatorname{\mathcal{I}}_{\nabla}(f)$, is generated by all partial
derivatives of $f$. From the definition, the set of critical point of $f$ is
the real gradient variety
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$.

We recall from (bertsekas2nd, , Chapter 1) some fundamental results related to
optimality conditions of the unconstrained problem. Suppose that
$x\in\operatorname{\mathbb{R}}^{n}$ is a local minimizer of $f$ over
$\operatorname{\mathbb{R}}^{n}$. According to the necessary conditions for
optimality (bertsekas2nd, , Proposition 1.1.1), $x$ belongs to
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$ and
$\nabla^{2}f$, the Hessian matrix of $f$, is positive semi-definite at $x$.
Conversely, if $x$ is a critical point of $f$ and the second-order sufficiency
condition holds, i.e. $\nabla^{2}f(x)$ is positive definite, then $x$ is a
strict local minimizer (bertsekas2nd, , Proposition 1.1.2).

###  2.3 Local minimizers of constrained problems

Let $f,h_{1},\dots,h_{m}$ be polynomials in $\operatorname{\mathbb{R}}[x]$
with $1\leq m<n$. The complex algebraic variety defined by $h$ is the
following set:

$V_{\operatorname{\mathbb{C}}}(h)=\\{x\in\operatorname{\mathbb{C}}^{n}:h_{1}(x)=\dots=h_{m}(x)=0\\}.$
(2.2)

We recall some notions and fundamental results on local minimizers of $f$ over
the real algebraic variety
$V_{\operatorname{\mathbb{R}}}(h)=V_{\operatorname{\mathbb{C}}}(h)\cap\operatorname{\mathbb{R}}^{n}$.

A point $x\in\operatorname{\mathbb{R}}^{n}$ is a critical point of $f$ over
$V_{\operatorname{\mathbb{R}}}(h)$ if there exists multipliers
$\lambda=(\lambda_{1},\dots,\lambda_{m})\in\operatorname{\mathbb{R}}^{m}$,
called a vector of Lagrange multipliers associated to $x$, such that

$\nabla f(x)+\lambda_{1}\nabla h_{1}(x)+\dots+\lambda_{m}\nabla h_{m}(x)=0,$
(2.3)

where $\nabla g$ is the gradient vector of the polynomial $g$. Such a pair
$(x,\lambda)$ is a critical point of the Lagrangian function that is in $n+m$
variables,

$L(x,\lambda):=f(x)+\lambda^{T}h.$ (2.4)

Suppose the matrix $\nabla h$ is full rank at $x$, i.e. $\nabla
h_{1}(x),\dots,\nabla h_{m}(x)$ are linearly independent, for all $x$ in
$V_{\operatorname{\mathbb{C}}}(h)$. If $x$ is a local minimizer of $f$ over
$V_{\operatorname{\mathbb{R}}}(h)$, then there exists unique
$\lambda\in\operatorname{\mathbb{R}}^{p}$ such that $(x,\lambda)$ is a
critical point of $L$, and the second-order necessary condition holds
(bertsekas2nd, , Proposition 3.1.1):

$u^{T}\Big{(}\nabla^{2}_{xx}L(x,\lambda)\Big{)}u\geq 0,\ \forall
u\in\bigcap_{j=1}^{m}\nabla h_{j}(x)^{\perp},$ (2.5)

where $\nabla^{2}_{xx}L$ is the Hessian matrix of $L$ with respect to only the
variable $x$, $a^{\perp}$ is the orthogonal complement to vector
$a\in\operatorname{\mathbb{R}}^{n}$. Conversely, if $(x,\lambda)$ is a
critical point of $L$ and the second-order sufficiency condition holds:

$u^{T}\Big{(}\nabla^{2}_{xx}L(x,\lambda)\Big{)}u>0,\ \forall 0\neq
u\in\bigcap_{j=1}^{m}\nabla h_{j}(x)^{\perp},$ (2.6)

then $x$ is a strict local minimizer (bertsekas2nd, , Proposition 3.2.1).

We denote by $\nabla h=[\nabla h_{1}\,\cdots\,\nabla h_{m}]^{T}$ and
$\nabla(f,h)=[\nabla f\,\nabla h_{1}\,\cdots\,\nabla h_{m}]^{T}$ the Jacobian
matrices of $h$ and of $(f,h)$, respectively. Clearly, the size of $\nabla h$
is $m\times n$ and that one of $\nabla(f,h)$ is $(m+1)\times n$. We denote by
$\operatorname{MaxMinors}(\nabla(f,h))$ the the set of all maximal minors of
the Jacobian matrix $\nabla(f,h)$ and by
$\operatorname{\mathcal{I}}_{\nabla}(f,h)$ the ideal is generated by
$h_{1},\dots,h_{m}$ and the polynomials in
$\operatorname{MaxMinors}(\nabla(f,h))$, i.e.

$\operatorname{\mathcal{I}}_{\nabla}(f,h):=\left\langle
h,\operatorname{MaxMinors}(\nabla(f,h))\right\rangle.$ (2.7)

##  3 Computing local minimizers of polynomials over
$\operatorname{\mathbb{R}}^{n}$

Let $f$ be a polynomial in $\operatorname{\mathbb{R}}[x]$. We consider the
minimization problem whose objective function is $f$ and constraint set is
$\operatorname{\mathbb{R}}^{n}$.

###  3.1 Technical results

We provide some technical results which will be used to prove the main result
in Theorem 3.1.

By adding an extra condition, the below lemma gives us a necessary and
sufficient condition for strict local minimizers of $f$.

###### Lemma 3

Suppose that $\det(\nabla^{2}f)$ has no roots on
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$. Then,
$x\in\operatorname{\mathbb{R}}^{n}$ is a local minimizer of $f$ if and only if
$x\in V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$
and $(\nabla^{2}f)(x)$ is a positive definite matrix.

Proof. Recall that the polynomial $f$ is twice continuously differentiable on
$\operatorname{\mathbb{R}}^{n}$. It is easy to see that the sufficient
condition is the second-order sufficient condition for optimality
(bertsekas2nd, , Proposition 1.1.2). We only need to prove the necessary
condition.

Let $x\in\operatorname{\mathbb{R}}^{n}$ be a local minimizer of $f$ over
$\operatorname{\mathbb{R}}^{n}$. According to (bertsekas2nd, , Proposition
1.1.1), the second-order necessary condition holds, i.e. $x\in
V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$ and
$(\nabla^{2}f)(x)$ is a positive semi-definite matrix. From the assumption
that $\det(\nabla^{2}f)$ has no roots on
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$, the
value of $\det(\nabla^{2}f)$ at $x$ must be nonzero, hence all eigenvalues
$(\nabla^{2}f)(x)$ are non-zero. It follows that the matrix $(\nabla^{2}f)(x)$
is positive definite. ∎

###### Example 1

We consider the polynomial $f=x_{1}^{2}+(x_{1}x_{2}-1)^{2}$ in
$\operatorname{\mathbb{R}}[x_{1},x_{2}]$. The real gradient variety has only
one point,
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))=\\{(0,0)\\}$.
The determinant of the Hessian matrix of $f$ is
$\det(\nabla^{2}f)=-12x_{1}^{2}x_{2}^{2}+4x_{1}^{2}+16x_{1}x_{2}-4$ that is
negative at $(0,0)$. According to Lemma 3, $f$ has no local minimizers.

###### Lemma 4

Suppose that $\operatorname{\mathcal{I}}_{\nabla}(f)$ is zero-dimensional and
points in
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$ have
distinct $x_{1}$-coordinates. Then, there exist $w,v_{2},\dots,v_{n}$ in
$\operatorname{\mathbb{R}}[x_{1}]$, with $\deg v_{i}<\deg
w=\\#V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$
for $i=2,\dots,n$, such that

$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))=\left\langle
w(x_{1}),x_{2}-v_{2}(x_{1}),\dots,x_{n}-v_{n}(x_{1})\right\rangle.$ (3.1)

Proof. We consider the radical ideal of
$\operatorname{\mathcal{I}}_{\nabla}(f)$ and the lexicographical ordering
$x_{1}<x_{2}<\cdots<x_{n}$ in $\operatorname{\mathbb{R}}[x]$. From the first
conclusion in Lemma 1, the complex variety of
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$ coincides with
that one of $\operatorname{\mathcal{I}}_{\nabla}(f)$. Hence,
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$ is also zero-
dimensional, and obviously satisfies the condition: points in
$V_{\operatorname{\mathbb{C}}}(\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f)))$
have distinct $x_{1}$-coordinates. Moreover, thanks to the second conclusion
in Lemma 1, $\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$ is
also radical. According to the Shape Lemma (Lemma 2), the reduced Gröbner
basis of $\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$ is in
shape position, i.e. there exist polynomials $w,v_{2},\dots,v_{n}$ satisfying
(3.1) as claimed. ∎

###  3.2 Transferring equivalently to a univariate problem

The following theorem provides a method to compute all local minimizers of the
polynomial $f$ over $\operatorname{\mathbb{R}}^{n}$ under genericity
conditions.

###### Theorem 3.1

Suppose that $\operatorname{\mathcal{I}}_{\nabla}(f)$ is zero-dimensional and
points in
$V_{\operatorname{\mathbb{C}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$
have distinct $x_{1}$-coordinates. If $\det(\nabla^{2}f)$ has no roots on
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$,
then we have the following conclusions:

  * (a)

There exist $w,v_{2},\dots,v_{n}\in\operatorname{\mathbb{R}}[x_{1}]$
satisfying (3.1);

  * (b)

The vector $x$ is a local minimizer of $f$ over
$\operatorname{\mathbb{R}}^{n}$ if and only if its coordinates satisfy

$w(x_{1})=0,x_{2}=v_{2}(x_{1}),\dots,x_{n}=v_{n}(x_{1}),$ (3.2)

and $(\nabla^{2}f)(x)$ is positive definite.

Proof. Since points in
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$ have
distinct $x_{1}$-coordinates, according to Lemma 4, there exist univariate
polynomials $w,v_{2},\dots,v_{n}$ as a certificate of being in shape position
(3.1) of the radical ideal
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$. We recall from
Lemma 1 that

$V_{\operatorname{\mathbb{R}}}(\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f)))\equiv
V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f)).$ (3.3)

Let $x\in\operatorname{\mathbb{R}}^{n}$ be a local minimizer of $f$. Since the
assumption saying that $\det(\nabla^{2}f)$ has no roots on
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$,
according to Lemma 3, $x\in
V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$ and
$(\nabla^{2}f)(x)$ is a positive definite matrix. Hence, we only need to point
out that $x$ satisfies the $n$ equalities in (3.2). Indeed, since $x$ is a
critical point of $f$, $x$ belongs to
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$.
Thanks to (3.3), $x$ belongs to
$V_{\operatorname{\mathbb{R}}}(\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f)))$.
Therefore, with $w,v_{2},\dots,v_{n}$ above, from (3.1), the coordinates of
$x$ satisfy the conditions: $w(x_{1})=0$, $x_{2}=v_{2}(x_{1}),$ $\dots,$
$x_{n}=v_{n}(x_{1})$.

Conversely, suppose $x\in\operatorname{\mathbb{R}}^{n}$ such that (3.2) is
satisfied and $(\nabla^{2}f)(x)$ is positive definite. It follows from (3.1)
and the $n$ equalities in (3.2) that $x$ belongs to
$V_{\operatorname{\mathbb{R}}}(\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f)))$
and hence to
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$ as
(3.3). We conclude from Lemma 3 that $x$ is a local minimizer of $f$ over
$\operatorname{\mathbb{R}}^{n}$. ∎

We illustrate Theorem 3.1 by considering a simple example.

###### Example 2

We consider the polynomial $f$ in two variables $x_{1},x_{2}$ with real
coefficients as follows $f=x_{1}^{4}+4x_{1}x_{2}+2x_{2}^{2}$. The gradient
ideal of $f$ is given by

$\operatorname{\mathcal{I}}_{\nabla}(f)=\left\langle
4x_{1}^{3}+4x_{2},4x_{1}+4x_{2}\right\rangle=\left\langle
x_{1}^{3}-x_{1},x_{2}+x_{1}\right\rangle.$

This ideal is zero-dimensional and radical. Hence,
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))=\operatorname{\mathcal{I}}_{\nabla}(f)$.
With the graded lexicographical order $x_{1}<x_{2}$,
$\operatorname{\mathcal{I}}_{\nabla}(f)=\left\langle
x_{1}^{3}-x_{1},x_{2}+x_{1}\right\rangle$ is in shape position as in (2.1),
where $w(x_{1})=x_{1}^{3}-x_{1}$ and $v_{2}(x_{1})=-x_{1}$ of degree $1$.
Moreover, the variety of $\operatorname{\mathcal{I}}_{\nabla}(f)$ is the
following set that has only real points

$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))=\left\\{(-1,1),(0,0),(1,-1)\right\\}=V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f)).$

Hence,
$\\#V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))=3$
and distinct points in this set have distinct $x_{1}$-coordinates. The real
root set of $w$ is $\\{-1,0,1\\}$.

Its Hessian matrix with respect to variables $(x_{1},x_{2})$ is given by

$\nabla^{2}f=4\begin{bmatrix}3x_{1}^{2}&1\\\ 1&1\end{bmatrix}.$

The determinant of $\nabla^{2}f$ is $16(3x_{1}^{2}-1)$. This determinant is
nonzero on the real gradient variety
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$;
Moreover, $\nabla^{2}f$ is positive definite at two points $(-1,1)$ and
$(1,-1)$, hence the second-order sufficiency condition is satisfied. We
conclude that the set of all local minimizes of $f$ over
$\operatorname{\mathbb{R}}^{2}$ is $\\{(-1,1),(1,-1)\\}$.

Under the assumptions in Theorem 3.1 if the infimum of $f$ over
$\operatorname{\mathbb{R}}^{n}$, denoted by $f_{\min}$, is attained, we show
in the following theorem that this value can be computed though a univariate
optimization problem.

###### Theorem 3.2

Suppose the conditions in Theorem 3.1 hold and $w,v_{2},\dots,v_{n}$ are given
in Theorem 3.1. We define

$p(t):=f(t,v_{2}(t),\dots,v_{n}(t)),\ t\in\operatorname{\mathbb{R}}.$ (3.4)

Let $r$ be the remainder of the division of $p$ by $w$ with $\deg r<\deg w$.
If the infimum of $f$ over $\operatorname{\mathbb{R}}^{n}$, denoted
$f_{\min}$, is attained, then

$f_{\min}=\min\\{r(t):w(t)=0\\}.$ (3.5)

Proof. Suppose that the infimum of $f$ over $\operatorname{\mathbb{R}}^{n}$ is
attained. We will demonstrate the following equalities:

$f_{\min}=\min\\{p(t):w(t)=0\\}=\min\\{r(t):w(t)=0\\}.$ (3.6)

The first equality of (3.6) is obtained from the following relations:

$\displaystyle\min_{x}\\{f(x):x\in\operatorname{\mathbb{R}}^{n}\\}$
$\displaystyle=\min_{x}\left\\{f(x):x\in
V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f))\right\\}$
$\displaystyle=\min_{x}\left\\{f(x):x\in
V_{\operatorname{\mathbb{R}}}(\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f)))\right\\}$
$\displaystyle=\min_{x_{1}}\left\\{f(x_{1},v_{2}(x_{1}),\dots,v_{n}(x_{1})):w(x_{1})=0\right\\}$
$\displaystyle=\min_{t}\left\\{p(t):w(t)=0\right\\}.$

We give here some explanations for these equalities. We have the first
equality because every global minimizer is in the critical set. The second
equality is obtained relying on (3.3). The third one is implied from Theorem
3.1. Specifically, $w,v_{2},\dots,v_{n}$ are a certificate of being in shape
position (3.1) of
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$; Hence, the set
$\\{(t,v_{2}(t),\dots,v_{n}(t)):w(t)=0\\}$ coincides with the set
$V_{\operatorname{\mathbb{R}}}(\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f)))$.
The last equality is obtained from the definition of $p$.

The last equality in (3.6) is implied from the fact that $p=gw+r$ and that the
values of $p$ and $r$ are coincident on the set $\\{t:w(t)=0\\}$. ∎

###### Example 3

We consider the polynomial $f$ in Example 2. One can check that the polynomial
$f$ is coercive on $\operatorname{\mathbb{R}}^{2}$, hence the infimum of $f$
is attained. Recall from Example 2 that $w=t^{3}-t$ and $v_{2}=-t$, thus the
polynomial $p$ and remainder $r$ of the division of $p$ by $w$ are given
respectively by:

$p(t)=f(t,v_{2}(t))=t^{4}-2t^{2},\ r(t)=-t^{2}.$

According to the formula (3.5) in Theorem 3.2, one has

$f_{\min}=\min\\{-t^{2}:t^{3}-t=0\\}=-1.$

###### Remark 1

It is worth to emphasize here the meaning of equalities in (3.5) and (3.6).
Suppose that $f$ reaches its infimum and the ideal
$\operatorname{\mathcal{I}}_{\nabla}(f)$ is zero-dimensional. From Bezout’s
theorem (cox2013, , Chapter 8, §7),
$\\#V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$ is
at most $(d-1)^{n}$, where $d$ is the degree of $f$. Since $\deg v_{i}<\deg w$
for $i=2,\dots,n$, the degree of $p$ does not exceed $d(d-1)^{n}$, this number
is significantly larger than $(d-1)^{n}-1$ that is the possibly highest degree
of $r$. It turns out from (3.5) that computing the minimum of the polynomial
$f$ in $n$ variables of degree $d$ over $\operatorname{\mathbb{R}}^{n}$ is
equivalent to computing the minimum of a univariate polynomial $r$ of degree
at most $(d-1)^{n}-1$ over the real roots of another univariate polynomial
$w$, with $\deg r<\deg w\leq(d-1)^{n}$. Thanks the last equality in (3.6), the
complexity of computing $\min\\{r(t):w(t)=0\\}$ is less than $d$ times
compared to $\min\\{p(t):w(t)=0\\}$.

###  3.3 Genericity of the assumptions in Theorem 3.1

Denote by $\operatorname{\mathbb{R}}[x]_{d}$ the linear space of all
polynomials in $\operatorname{\mathbb{R}}[x]$ of degree at most $d$. A
property is said to be generic on $\operatorname{\mathbb{R}}[x]_{d}$ if it
holds on a subset
$\operatorname{\mathcal{O}}\subset\operatorname{\mathbb{R}}[x]_{d}$ such that
its complement
$\operatorname{\mathbb{R}}[x]_{d}\setminus\operatorname{\mathcal{O}}$ has
Lebesgue measure zero.

The first assumption related to being zero-dimensional of
$\operatorname{\mathcal{I}}_{\nabla}(f)$ is generic (nie2006, , Proposition
1). Moreover, if this assumption is satisfied, then the second assumption,
saying that distinct points in
$V_{\operatorname{\mathbb{C}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$
have distinct $x_{1}$-coordinates, is also generic. If not, we can take a
generic matrix $A$ of size $n\times n$, then $f(Ax)$ satisfies the condition.
In particular, we can choose matrix $A$ as in Subsection 3.5.

We discuss the last assumption. Assume that the first two assumptions are
satisfied. There exist $w,v_{2},\dots,v_{n}\in\operatorname{\mathbb{R}}[t]$
satisfying (3.1). We replace $x_{i}$ by in $\det(\nabla^{2}f)$ by
$v_{i}(x_{1})$, for $i=2,\dots,n$. The determinant is a polynomial depending
only on variable $x_{1}$. Then the image of $\\{x_{1}:w(x_{1})=0\\}$ through
this polynomial function has finitely many points.

###  3.4 Algorithms computing local minimizers and the minimum

Based on Theorem 3.1, we design an algorithm named
$\operatorname{\mathtt{GRULOM}}$ to compute all LOcal Minimizers of a
polynomial $f$ over $\operatorname{\mathbb{R}}^{n}$ (Unconstrained) though its
GRadient ideal, and another one named $\operatorname{\mathtt{GRULOM}^{+}}$,
based on Theorem 3.2, to compute the minimum if it exists.

####  3.4.1 Algorithm $\operatorname{\mathtt{GRULOM}}$

The input of Algorithm $\operatorname{\mathtt{GRULOM}}$ is a polynomial
$f\in\operatorname{\mathbb{R}}[x]$ such that the assumptions in Theorem 3.1
are satisfied. The output of $\operatorname{\mathtt{GRULOM}}$ includes a list
of finitely many numbers $T\subset\operatorname{\mathbb{R}}$ and a list of
univariate polynomials
$\\{w,v_{2},\dots,v_{n}\\}\subset\operatorname{\mathbb{R}}[t]$ such that
$\\{(t,v_{2}(t),\dots,v_{n}(t)):t\in T\\}$ is the set of all local minimizers
of $f$.

At Line 1, we compute
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$, the radical
ideal of $\operatorname{\mathcal{I}}_{\nabla}(f)$. Next, at Line 2, we compute
the reduced Gröbner basis $\\{w,x_{2}-v_{2},\dots,x_{n}-v_{n}\\}$ of
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$ with the
lexicographical ordering $x_{1}<x_{2}<\cdots<x_{n}$. By substituting
$x_{1}=t$, $x_{2}=v_{2}(t),\dots,x_{n}=v_{n}(t)$ in the Hessian matrix
$(\nabla^{2}f)(x)$, we obtain obtain $H(t)$ at Line 3; $H(t):=\tilde{H}(t)\mod
w(t)$ means

$H_{ij}(t):=\tilde{H}_{ij}(t)\mod w,$

for all $i,j=1,\dots,n$. At Line 4, we compute the real roots of the
univariate polynomial $w$, listed by $\\{t_{1},\dots,t_{s}\\}$. At Line 5, at
first we set $T$ is empty; after this line, $T$ contains all $t$ in
$\\{t_{1},\dots,t_{s}\\}$ such that $H(t)$ is positive definite.

Algorithm 1 $\operatorname{\mathtt{GRULOM}}$ computing local minimizers of a
polynomial over $\operatorname{\mathbb{R}}^{n}$

Input: $f\in\operatorname{\mathbb{R}}[x]$ such that
$\operatorname{\mathcal{I}}_{\nabla}(f)$ is zero-dimensional, points in
$V_{\operatorname{\mathbb{C}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$
have distinct $x_{1}$-coordinates, and $\det(\nabla^{2}f)$ is nonzero on
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$

Output: a list $T\subset\operatorname{\mathbb{R}}$ and a list
$\\{w,v_{2},\dots,v_{n}\\}\subset\operatorname{\mathbb{R}}[t]$ such that the
set of all local minimizers of $f$ over $\operatorname{\mathbb{R}}^{n}$ is
given by

$\\{(t,v_{2}(t),\dots,v_{n}(t)):t\in T\\}$

  1. 1:

Compute $\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$

  2. 2:

Compute the reduced Gröbner basis $[w,x_{2}-v_{2},\dots,x_{n}-v_{n}]$ of
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$ with the
lexicographical ordering $x_{1}<x_{2}<\cdots<x_{n}$

  3. 3:

Obtain $\tilde{H}(t)$ by substituting
$x_{1}=t,x_{2}=v_{2}(t),\dots,x_{n}=v_{n}(t)$ in $(\nabla^{2}f)(x)$. Compute
$H(t):=\tilde{H}(t)\mod w(t)$.

  4. 4:

Compute the real roots $\\{t_{1},\dots,t_{s}\\}$ of $w$

  5. 5:

Set $T:=\emptyset$. For each $t\in\\{t_{1},\dots,t_{s}\\}$, if $H(t)\succ 0$
then $T:=T\cup\\{t\\}$.

  6. 6:

Return $T$ and $[w,v_{2},\dots,v_{n}]$

The correctness of Algorithm $\operatorname{\mathtt{GRULOM}}$ is stated in the
following proposition.

###### Proposition 1

Let $f\in\operatorname{\mathbb{R}}[x]$ such that the conditions in Theorem 3.1
hold. On input $f$, Algorithm $\operatorname{\mathtt{GRULOM}}$ terminates and
returns all local minimizers of $f$.

Proof. From the assumptions, we see that the radical ideal
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$ is zero-
dimensional and radical. Because the Shape Lemma’s assumption holds, with the
lexicographical monomial order $x_{1}<x_{2}<\dots<x_{n}$, the reduced Gröbner
basis of $\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(f))$ at Line
2 has the form $\\{w,x_{2}-v_{2},\dots,x_{n}-v_{n}\\}$. The matrix
$\tilde{H}(t)$, obtained at Line 3 by substituting $x_{1}=t$,
$x_{i}=v_{i}(t),i=2,\dots,n$ in $(\nabla^{2}f)(x)$, is a symmetric and
univariate polynomial matrix. The polynomial $w$ is univariate with real
coefficients, hence we can compute its real roots $\\{t_{1},\dots,t_{s}\\}$.
After Line 5, for each $t\in T$, $H(t)\succ 0$ is equivalent to
$\tilde{H}(t)\succ 0$ because $H_{ij}(t)$ and $\tilde{H}_{ij}(t)$ have the
same value on $w(t)=0$. This implies that, at $x=(t,v_{2}(t),\dots,v_{n}(t))$,
$f$ satisfies the second-order sufficient condition for optimality (see Lemma
3). Hence, according to Theorem 3.1, $\\{(t,v_{2}(t),\dots,v_{n}(t)):t\in
T\\}$ is the set of all local minimizers of $f$. ∎

###### Remark 2

The algorithm $\operatorname{\mathtt{GRULOM}}$ can provide a univariate
representation for the set of local minimizers of $f$ over
$\operatorname{\mathbb{R}}^{n}$ whose can be described as a system of $n+1$
univariate polynomial equalities and one univariate polynomial matrix
inequality:

$\\{w(t)=0,\,x_{1}=t,\,x_{i}=v_{i}(t),i=2,\dots,n,\,H(t)\succ 0\\}.$

Furthermore, by the definition at Line 3, one has $\deg H_{ij}(t)\leq\deg w$.
Hence, we claim that the degrees of all polynomials $w,v_{i},H_{ij}$ do not
exceed $(d-1)^{n}$.

###### Remark 3

We would like to remark that a computer algebra system, for example Maple, can
handle the tasks in Algorithm $\operatorname{\mathtt{GRULOM}}$. By using the
package $\mathtt{Groebner}$ of Maple, to compute the radical of an ideal, we
use the command $\mathtt{Radical}$; to compute the reduced Gröbner basis of an
ideal with respect to a given lexicographical order, we use the command
$\mathtt{Basis}$. Furthermore, the input conditions of Algorithm
$\operatorname{\mathtt{GRULOM}}$ are verifiable. To be more specific, we point
out here some techniques to verify them:

  * •

To check whether an ideal $\operatorname{\mathcal{I}}$ is zero-dimensional or
not, we use the command $\mathtt{IsZeroDimensional}$.

  * •

Suppose that $\operatorname{\mathcal{I}}$ is zero-dimensional. We compute the
reduced Gröbner basis of $\operatorname{\mathcal{I}}$ with respect to a given
lexicographical order $x_{1}<\dots<x_{n}$. If the basis is in shape position
with the form $\\{w,x_{2}-v_{2},\dots,x_{n}-v_{n}\\}$, where
$v_{i}\in\operatorname{\mathbb{R}}[x_{1}]$, and if $w$ is square-free then we
conclude that points
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})$ have distinct
$x_{1}$-coordinates. Indeed, by the definition, one has
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})=\\{(t,v_{2}(t),\dots,v_{n}(t)):t\in\operatorname{\mathbb{C}},w(t)=0\\}$.
Recall that “$w$ is square-free” means that all complex roots of $w$ are
distinct. Equivalently, in this situation, the $x_{1}$-coordinate of all
points $V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}})$ are
distinct. The command $\mathtt{sqrfree}$ helps us to check whether a
polynomial is square-free or not.

  * •

One sees that $\det(\nabla^{2}f)$ is nonzero on
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$
if and only if the two univariate polynomials $\det H(t)$, where $H(t)$ is
defined at Line 3, and $w(t)$ have no common real zero points. To verify this
property, we can use the command $\mathtt{gcd}$ to compute the greatest common
divisor of polynomials.

####  3.4.2 Algorithm $\operatorname{\mathtt{GRULOM}^{+}}$

The input of this algorithm is a polynomial $f\in\operatorname{\mathbb{R}}[x]$
such that the conditions in the input of $\operatorname{\mathtt{GRULOM}}$ are
satisfied and the infimum of $f$ over $\operatorname{\mathbb{R}}^{n}$ is
attained. The output of $\operatorname{\mathtt{GRULOM}^{+}}$ includes
$f_{\min}$ the global minimum of $f$ over $\operatorname{\mathbb{R}}^{n}$.

At Line 1, we perform $\operatorname{\mathtt{GRULOM}}(f)$ to obtain the list
of univariate polynomials $[w,v_{2},\dots,v_{n}]$. At Line 2, we compute the
univariate polynomials $p$ and $r$, where $r$ is the remainder of the division
of $p$ by $w$. At Line 3, we compute the minimum of $r$ with the constraint
$\\{t\in\operatorname{\mathbb{R}}:w(t)=0\\}$.

Algorithm 2 $\operatorname{\mathtt{GRULOM}^{+}}$ computing the minimum of a
polynomial over $\operatorname{\mathbb{R}}^{n}$

Input: $f\in\operatorname{\mathbb{R}}[x]$ such that
$\operatorname{\mathcal{I}}_{\nabla}(f)$ is zero-dimensional, all points in
$V_{\operatorname{\mathbb{C}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$
have distinct $x_{1}$-coordinates, $\det(\nabla^{2}f)$ is nonzero on
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$,
and $f_{\min}$ attains

Output: $f_{\min}$ the global minimum of $f$ over
$\operatorname{\mathbb{R}}^{n}$

  * 1:

Compute as at Lines 1–2 in Algorithm $\operatorname{\mathtt{GRULOM}}$ to get
$\\{w,v_{2},\dots,v_{n}\\}$

  * 2:

Set $p(t):=f(t,v_{2}(t),\dots,v_{n}(t))$ and compute the remainder $r$ of the
division of $p$ by $w$

  * 3:

Compute $f_{\min}=\min\\{r(t):w(t)=0\\}$

  * 4:

Return $f_{\min}$

###### Proposition 2

Let $f$ be in $\operatorname{\mathbb{R}}[x]$ such that the conditions in
Theorem 3.1 hold. Suppose that the infimum of $f$ over
$\operatorname{\mathbb{R}}^{n}$ attains. On input $f$, Algorithm
$\operatorname{\mathtt{GRULOM}^{+}}$ terminates and returns the infimum.

Proof. Since $f$ satisfies the conditions of the input of
$\operatorname{\mathtt{GRULOM}}$, we perform Lines 1–2 in
$\operatorname{\mathtt{GRULOM}}$ and obtain $\\{w,v_{2},\dots,v_{n}\\}$.
Recall that $r$ is the remainder of the division of $p$ by $w$, therefore the
values of $r$ and $p$ are coincident on
$\\{t\in\operatorname{\mathbb{R}}:w(t)=0\\}$. According to Theorem 3.2,
$\min\\{r(t):w(t)=0\\}$ is the minimum of $f$ over
$\operatorname{\mathbb{R}}^{n}$. ∎

###  3.5 What if points in
$V_{\operatorname{\mathbb{C}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$
having same $x_{1}$-coordinates?

We consider the case that there are two distinct points in
$V_{\operatorname{\mathbb{C}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$
such that their $x_{1}$’s-coordinates are equal. We handle this case as in the
proof of (magron2023, , Theorem 3.1).

Denote by $\delta$ the cardinality of
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$,
according to (rouillier1999, , Lemma 2.1), there is a number $j$ in the set
$\\{1,\dots,(n-1)\delta(\delta-1)/2\\}$ such that the linear function
$u:=x_{1}+jx_{2}+\dots+j^{n-1}x_{n}$ separates
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$, i.e.,
$u(x)\neq u(y)$ for any distinct points $x,y$ in
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$. We
consider the change of variables $y=Ax$, where

$A=\begin{bmatrix}1&j&j^{2}&\cdots&j^{n-1}\\\ 0&1&0&\cdots&0\\\
0&0&1&\cdots&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\cdots&1\end{bmatrix}.$ (3.7)

Clearly, $A$ is an invertible matrix. Then we obtain a new polynomial $g$ in
variables $y_{1},y_{2},\dots,y_{n}$, says $g(y)=f(A^{-1}y)$. Because of the
chain rule $\nabla g=\nabla f\circ A^{-1}$, we have

$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(g))=\\{y\in\operatorname{\mathbb{C}}^{n}:y=Ax,\,x\in
V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))\\}.$

It follows that the ideal $\operatorname{\mathcal{I}}_{\nabla}(g)$ is also
zero-dimensional. Since $y_{1}=u(x)$ separates
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(g))$,
distinct points in
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(g))$ have
distinct $y_{1}$-coordinates. Furthermore, we have
$\nabla^{2}g=\nabla^{2}f\circ A^{-1}$, thus

$\det(\nabla^{2}g)=\det(\nabla^{2}f)\times\det(A^{-1})$

has no roots on
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(g))$ if
$\det(\nabla^{2}f)$ has no roots on
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$.
From above results, we observe that $g\in\operatorname{\mathbb{R}}[y]$
satisfies the conditions of Theorem 3.1.

Hence, we now apply $\operatorname{\mathtt{GRULOM}}$ and
$\operatorname{\mathtt{GRULOM}^{+}}$ to $g$. We obtain lists $T_{g}$ and
$[w_{g},v_{g,2},\dots,v_{g,n}]$ such that
$\\{(t,v_{g,2}(t),\dots,v_{g,n}(t)):t\in T_{g}\\}$ is the set of all local
minimizers of $g$, and its minimum value $g_{\min}$. To recover all local
minimizers of $f$, we only need to apply the change of variables $x=A^{-1}y$.
The set of all local minimizers of $f$ is given by

$\\{A^{-1}(t,v_{g,2}(t),\dots,v_{g,n}(t))^{T}:t\in T_{g}\\}.$

###### Example 4

We consider the polynomial $f$ in two variables $x_{1},x_{2}$ of degree $4$
with real coefficients $f=x_{1}^{2}+x_{2}^{4}-2x_{2}^{2}$. The gradient ideal
$\operatorname{\mathcal{I}}_{\nabla}(f)$ is

$\operatorname{\mathcal{I}}_{\nabla}(f)=\left\langle
2x_{1},4x_{2}^{3}-4x_{2}\right\rangle.$ (3.8)

This ideal is zero-dimensional and radical. The gradient variety of $f$ is the
following set that has only real points

$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))=\left\\{(0,-1),(0,0),(0,1)\right\\}=V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f)).$

The points in
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$ have
the same $x_{1}$-coordinates. Hence, we use the technique in Subsection 3.5.
We choose $j=1$, then we can check that the linear function $u=x_{1}+x_{2}$
separates
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))$. We
consider the change of variables $y=Ax$, where

$A=\begin{bmatrix}1&1\\\ 0&1\end{bmatrix},\text{ and
}A^{-1}=\begin{bmatrix}1&-1\\\ 0&1\end{bmatrix}.$

and obtain the polynomial $g$ in variables $y_{1},y_{2}$,

$g(y)=f(A^{-1}y)=y_{1}^{2}+y_{2}^{4}-y_{2}^{2}-2y_{1}y_{2}.$

By an easy computation, we obtain
$\operatorname{\mathcal{I}}_{\nabla}(g)=\left\langle
y_{1}^{3}-y_{1},y_{2}-y_{1}\right\rangle$ with $w_{g}=y_{1}^{3}-y_{1}$,
$v_{g,2}=y_{1}$ and

$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(g))=\\{(-1,-1),(0,0),(1,1)\\}=\\{y\in\operatorname{\mathbb{C}}^{2}:y=Ax,x\in
V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f))\\}.$

We perform $\operatorname{\mathtt{GRULOM}}$ with the input $g$ and get
$T_{g}=\\{-1,1\\}$ such that $\\{(t,v_{g,2}(t):t\in T_{g}\\}$ is the set of
all local minimizers of $g$. Hence, the set of all local minimizers of $f$ is
given by

$\\{A^{-1}(t,v_{g,2}(t)):t\in T_{g}\\}=\\{(0,-1),(0,1)\\}.$

##  4 Computing local minimizers with equality constraints

Let $f,h_{1},\dots,h_{m}$ be polynomials in $\operatorname{\mathbb{R}}[x]$.
The present section considers the minimization problem whose objective
function is $f$ and constraint set is $V_{\operatorname{\mathbb{R}}}(h)$.

The techniques used in this section are almost the same techniques in the
previous section, hence several proofs will be omitted or sketched out.

###  4.1 Technical results

Similar to the unconstrained case, we need to provide some technical results
which are essential to prove the main results.

Recall that $L$ is the Lagrangian function defined in (2.4);
$\operatorname{\mathcal{I}}_{\nabla}(L)$ is the gradient ideal of $L$;
$\det(\nabla^{2}_{xx}L)$ is the Hessian matrix of $L$ with respect to only the
variable $x$, this determinant is a polynomial in variables $(x,\lambda)$.

###### Lemma 5

Suppose that $\nabla h$ is full rank on $V_{\operatorname{\mathbb{C}}}(h)$.
Then, we have the following conclusions:

  * (a)

The set of critical points of $f$ over $V_{\operatorname{\mathbb{R}}}(h)$
coincides with
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))$;

  * (b)

If $\operatorname{\mathcal{I}}_{\nabla}(f,h)$ is zero-dimensional then
$\operatorname{\mathcal{I}}_{\nabla}(L)$ so is, hence
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(L))$ has
finitely many points.

Proof. (a) Let $x\in V_{\operatorname{\mathbb{R}}}(h)$ be a critical point of
the restriction of $f$ to $V_{\operatorname{\mathbb{R}}}(h)$. There exist
multipliers
$\lambda=(\lambda_{1},\dots,\lambda_{m})\in\operatorname{\mathbb{R}}^{p}$ such
that (2.3) holds; i.e. $\nabla f(x)$ is represented as a linear combination of
$\nabla h_{1}(x),\dots,\nabla h_{m}(x)$. Hence, the ranks of matrices
$\nabla(f,h)$ and $\nabla h$ at $x$ are the same,

$\operatorname{rank}\left(\nabla(f,h)(x)\right)=\operatorname{rank}\left(\nabla
h(x)\right).$

It follows, from $m<n$ and $\nabla h(x)$ has full rank $m$, that all
$(m+1)$-minor of the matrix $\nabla(f,h)(x)$ must be zero. Therefore, $x$ is a
point in the real variety of $\operatorname{\mathcal{I}}_{\nabla}(f,h)$. The
above arguments hold equivalently, hence the inverse conclusion holds
obviously.

$\rm(b)$ Suppose that $\operatorname{\mathcal{I}}_{\nabla}(f,h)$ is zero-
dimensional. It follows that
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))$ has
finitely many points. Let $x$ in
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))$ be
fixed. The matrix $\nabla h(x)$ has full rank. Thus the linear equation system
(2.3) including $m$ equations in $m$ variables $\lambda_{1},\dots,\lambda_{m}$
has a unique solution $\lambda$. The finiteness of
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))$
implies that one of
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(L))$. ∎

For convenience, the conditions (2.5) and (2.6) will be written in the
following way, respectively:

$\nabla^{2}_{xx}L(x,\lambda)\succeq_{K}0\ \text{ and }\
\nabla^{2}_{xx}L(x,\lambda)\succ_{K}0,$

where

$K:=\\{u\in\operatorname{\mathbb{R}}^{n}:\nabla h_{1}(x)^{T}u=0,\cdots,\nabla
h_{m}(x)^{T}u=0\\}.$

###### Lemma 6

Suppose that $\nabla h$ is full rank on $V_{\operatorname{\mathbb{C}}}(h)$,
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))$ has
finite many points, and $\det(\nabla^{2}_{xx}L)$ has no roots on
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(L))$. Then,
$x\in V_{\operatorname{\mathbb{R}}}(h)$ is a local minimizer of $f$ over
$V_{\operatorname{\mathbb{R}}}(h)$ if and only if there is a Lagrange
multiplier vector $\lambda$ such that $\nabla^{2}_{xx}L(x,\lambda)\succ_{K}0$.

Proof. Clearly, the sufficient condition is the second-order sufficient
condition for optimality (bertsekas2nd, , Proposition 3.2.1) with a note that
$f,h_{1},\dots,h_{m}$ are twice continuously differentiable on
$\operatorname{\mathbb{R}}^{n}$. Thus, we only need to prove the necessary
condition.

Suppose that $x\in V_{\operatorname{\mathbb{R}}}(h)$ is a local minimizer of
$f$ over $V_{\operatorname{\mathbb{R}}}(h)$. Since $\nabla h(x)$ is full rank,
according to the second-order necessary condition for optimality
(bertsekas2nd, , Proposition 3.1.1), there exists Lagrange multipliers
$\lambda\in\operatorname{\mathbb{R}}^{p}$ such that

$\nabla f(x)+\lambda_{1}\nabla h_{1}(x)+\dots+\lambda_{m}\nabla h_{m}(x)=0,$

and the second-order necessary condition holds, i.e.
$\nabla^{2}_{xx}L(x,\lambda)\succeq_{K}0$. Recall that $x$ is critical point
of the restriction of $f$ to $V_{\operatorname{\mathbb{R}}}(h)$, from Lemma 5,
$x$ belongs to
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))$.
Thanks to the assumption that $\det(\nabla^{2}_{xx}L)$ has no roots on
$V_{\operatorname{\mathbb{R}}}(\operatorname{\mathcal{I}}_{\nabla}(L))$, we
conclude that the value of $\det(\nabla^{2}_{xx}L)$ at $(x,\lambda)$ is
nonzero.

Suppose on the contrary that $\nabla^{2}_{xx}L(x,\lambda)\succ_{K}0$ does not
hold. From the fact that $\nabla^{2}_{xx}L(x,\lambda)\succeq_{K}0$, there
exists $0\neq v\in K$ such that $v^{T}\big{(}\nabla^{2}_{xx}L(x)\big{)}v=0$.
It follows that the rank of the $n\times n$–matrix
$\nabla^{2}_{xx}L(x,\lambda)$ is strictly smaller than $n$. This contradicts
$\det(\nabla^{2}_{xx}L(x,\lambda))\neq 0$. ∎

###### Lemma 7

Suppose that $\operatorname{\mathcal{I}}_{\nabla}(f,h)$ is zero-dimensional
and points in
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))$ have
distinct $x_{1}$-coordinates. Then, there exist $w,v_{2},\dots,v_{n}$ and
$v_{n+1},\dots,v_{n+m}$ in $\operatorname{\mathbb{R}}[x_{1}]$, with $\deg
v_{i}<\deg
w=\\#V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))$
for $i=2,\dots,n+m$, such that

$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(L))=\left\langle
w(x_{1}),x_{2}-v_{2}(x_{1}),\dots,x_{n}-v_{n}(x_{1}),\lambda_{1}-v_{n+1}(x_{1}),\dots,\lambda_{m}-v_{n+m}(x_{1})\right\rangle.$
(4.1)

Proof. Thanks to the assertion $\rm(b)$ in Lemma 5,
$\operatorname{\mathcal{I}}_{\nabla}(L)$ is zero-dimensional. Moreover,
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(f,h))=\pi(V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(L)))$,
where $\pi$ is the projection $p(x,\lambda)=x$ with
$(x,\lambda)\in\operatorname{\mathbb{R}}^{n}\times\operatorname{\mathbb{R}}^{m}$.
Hence, distinct points in
$V_{\operatorname{\mathbb{C}}}(\operatorname{\mathcal{I}}_{\nabla}(L))$ have
distinct $x_{1}$-coordinates. Since the polynomial $L$ satisfies the condition
of Lemma 4, we conclude that there exist polynomials $w,v_{2},\dots,v_{n}$ and
$v_{n+1},\dots,v_{n+m}$ in $\operatorname{\mathbb{R}}[x_{1}]$ as claimed. ∎

###  4.2 Main results

The following theorem provides a method to compute all local minimizers of the
polynomial $f$ over the real algebraic set $V_{\operatorname{\mathbb{R}}}(h)$
under certain conditions. Moreover, if its infimum is attained then this value
can be computed though a univariate optimization problem.

###### Theorem 4.1

Suppose that $\nabla h$ is full rank on $V_{\operatorname{\mathbb{C}}}(h)$,
$\operatorname{\mathcal{I}}_{\nabla}(f,h)$ is zero-dimensional, and points in
$V_{\operatorname{\mathbb{C}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f,h)\right)$
have distinct $x_{1}$-coordinates. If $\det(\nabla^{2}_{xx}L)$ has no roots on
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(L)\right)$,
then we have the following conclusions:

  * (a)

There exist
$w,v_{2},\dots,v_{n},v_{n+1},\dots,v_{n+m}\in\operatorname{\mathbb{R}}[x_{1}]$
satisfying (4.1);

  * (b)

A vector $x$ is a local minimizer of $f$ over
$V_{\operatorname{\mathbb{R}}}(h)$ if and only if $x$ and $\lambda$, the
Lagrange multiplier vector associated to $x$, satisfy the following relations:

$w(x_{1})=0,x_{2}=v_{2}(x_{1}),\dots,x_{n}=v_{n}(x_{1}),$ (4.2)

and

$\lambda_{1}=v_{n+1}(x_{1}),\dots,\lambda_{m}=v_{n+m}(x_{1}),$ (4.3)

and $\nabla^{2}_{xx}L(x,\lambda)\succ_{K}0$.

Furthermore, we define $p(t):=f(t,v_{2}(t),\dots,v_{n}(t))$,
$t\in\operatorname{\mathbb{R}}$, and let $r$ be the remainder of the division
of $p$ by $w$ with $\deg r<\deg w$. Then, we conclude that:

  * (c)

If the infimum of $f$ over $V_{\operatorname{\mathbb{R}}}(h)$, denoted by
$f_{\min}$, is attained, then

$f_{\min}=\min\\{r(t):w(t)=0\\}.$

Proof. The proof is similar the proofs of Theorems 3.1 and 3.2 by i) replacing
$\det(\nabla^{2}f)\neq 0$ over
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(f)\right)$
by $\det(\nabla^{2}_{xx}L)\neq 0$ over
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(L)\right)$
and ii) replacing the positive definiteness of $\nabla^{2}f(x)$ by that one of
$\nabla^{2}_{xx}L(x,\lambda)$ with respect to $K$.

Thanks to Lemma 7, $w,v_{2},\dots,v_{n}$ and $v_{n+1},\dots,v_{n+m}$ in the
conclusion $\rm(a)$ exist. The conclusion $\rm(b)$ is obtained by applying
Lemma 6. The last conclusion is proved similarly Theorem 3.2. ∎

In (nie2009algebraic, , Proposition 2.1), Nie and Ranestad pointed out the
genericity of some assumptions in the previous theorem. When distinct points
in $V\left(\operatorname{\mathcal{I}}_{\nabla}(f,h)\right)$ have the same
$x_{1}$-coordinate, we apply the technique shown in Subsection 3.5.

###  4.3 An algorithm to compute local minimizers

Based on Theorem 4.1, we design an algorithm named
$\operatorname{\mathtt{GRALOM}}$ to compute all LOcal Minimizers of the
polynomial $f$ over the real Algebraic set $V_{\operatorname{\mathbb{R}}}(h)$
though their GRadient ideals.

The input of $\operatorname{\mathtt{GRALOM}}$ includes polynomials
$f,h_{1},\dots,h_{m}\in\operatorname{\mathbb{R}}[x]$ such that all assumptions
in Theorem 4.1 are satisfied. The output of $\operatorname{\mathtt{GRALOM}}$
includes a list of finitely many numbers $T\subset\operatorname{\mathbb{R}}$
and a list of univariate polynomials
$\\{w,v_{2},\dots,v_{n}\\}\subset\operatorname{\mathbb{R}}[t]$ such that the
set of all local minimizers of $f$ over $V_{\operatorname{\mathbb{R}}}(h)$ is
described by $\\{(t,v_{2}(t),\dots,v_{n}(t)):t\in T\\}$.

All lines in the algorithm are almost the same in
$\operatorname{\mathtt{GRULOM}}$ with noticing that the polynomial $L$ has
$n+m$ variables $(x,\lambda)$. Hence $\nabla^{2}_{xx}L$, at Line 3, might
contain both $x$ and $\lambda$. The purpose of Line 4 is computing the linear
subspace $K(t)$. At Line 6, $H(t)\succ_{K(t)}0$ means $H(t)$ is positive
definite with respect to $K(t)$.

Algorithm 3 $\operatorname{\mathtt{GRALOM}}$ computing local minimizers of $f$
over $V_{\operatorname{\mathbb{R}}}(h)$

Input: $f,h_{1},\dots,h_{m}\in\operatorname{\mathbb{R}}[x]$ such that $\nabla
h$ is full rank over $V_{\operatorname{\mathbb{C}}}(h)$,
$\operatorname{\mathcal{I}}_{\nabla}(f,h)$ is zero-dimensional, all points in
$V\left(\operatorname{\mathcal{I}}_{\nabla}(f,h)\right)$ have distinct
$x_{1}$-coordinates, and $\det(\nabla^{2}_{xx}L)$ is nonzero on
$V_{\operatorname{\mathbb{R}}}\left(\operatorname{\mathcal{I}}_{\nabla}(L)\right)$

Output: a list $T\subset\operatorname{\mathbb{R}}$ and a list
$\\{w,v_{2},\dots,v_{n}\\}\subset\operatorname{\mathbb{R}}[t]$ such that the
set of all local minimizers of $f$ over $V_{\operatorname{\mathbb{R}}}(h)$ is
given by

$\\{(t,v_{2}(t),\dots,v_{n}(t)):t\in T\\}$

  * 1:

Compute $\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(L))$ in
variables $(x,\lambda)$

  * 2:

Compute the reduced Gröbner basis
$\\{w,x_{2}-v_{2},\dots,x_{n}-v_{n},\lambda_{1}-v_{n+1},\dots,\lambda_{m}-v_{n+m}\\}$
of $\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(L))$ with the
lexicographical ordering
$x_{1}<x_{2}<\cdots<x_{n}<\lambda_{1}<\cdots<\lambda_{m}$

  * 3:

Obtain $\tilde{H}(t)$ by substituting $x_{1}=t,x_{i}=v_{i}(t),i=2,\dots,n$ and
$\lambda_{j}=v_{n+j}(t),j=1,\dots,m$ in $\nabla^{2}_{xx}L$. Compute
$H(t):=\tilde{H}(t)\mod w(t)$.

  * 4:

Obtain $l_{j}(t)$ by substituting $x_{1}=t,x_{i}=v_{i}(t),i=2,\dots,n$ in
$\nabla h_{j}(x)$, for $j=1,\dots,m$. Define

$K(t):=\\{v\in\operatorname{\mathbb{R}}^{n}:l_{1}(t)^{T}v=\dots=l_{m}(t)^{T}v=0\\}$

  * 5:

Compute the real roots $\\{t_{1},\dots,t_{s}\\}$ of $w$

  * 6:

Set $T:=\emptyset$. For each $t\in\\{t_{1},\dots,t_{s}\\}$, if
$H(t)\succ_{K(t)}0$ then $T:=T\cup\\{t\\}$.

  * 7:

Return $T$ and $\\{w,v_{2},\dots,v_{n}\\}$

The correctness of $\operatorname{\mathtt{GRALOM}}$ is stated in the following
proposition.

###### Proposition 3

Let $f,h_{1},\dots,h_{m}$ be in $\operatorname{\mathbb{R}}[x]$ such that the
conditions in Theorem 4.1 hold. On input $f,h_{1},\dots,h_{m}$, Algorithm
$\operatorname{\mathtt{GRALOM}}$ terminates and returns all local minimizers
of $f$ over $V_{\operatorname{\mathbb{R}}}(h)$.

Proof. According to the conclusion $\rm(b)$ in Lemma 5,
$\operatorname{\mathcal{I}}_{\nabla}(L)$ is zero-dimensional. Moreover,
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(L))$ satisfies all
assumptions of the Shape Lemma, hence its reduced Gröbner basis is in shape
position. The multipliers $\lambda_{j}$ are polynomial in variable $t$. After
substitutions, we obtain the matrix $H(t)$ and the linear subspace $K(t)$.
According to $\rm(b)$ in Theorem 4.1,

$\\{w(t)=0,x_{1}=t,x_{i}=v_{i}(t),i=2,\dots,n,\,H(t)\succ_{K(t)}0\\}$

is a univariate representation of local minimizers of $f$ over
$V_{\operatorname{\mathbb{R}}}(h)$. Hence, $\operatorname{\mathtt{GRALOM}}$
returns the set of local minimizers. ∎

In Subsection 5.2, we provide an example to illustrate how to
$\operatorname{\mathtt{GRALOM}}$ works.

Algorithm $\operatorname{\mathtt{GRALOM}^{+}}$. Let $f,h_{1},\dots,h_{m}$ be
satisfied the conditions in Theorem 4.1. Suppose that the infimum of $f$ over
$V_{\operatorname{\mathbb{R}}}(h)$ attains. To compute the value, we design
$\operatorname{\mathtt{GRALOM}^{+}}$ the same we do with
$\operatorname{\mathtt{GRULOM}^{+}}$ thanks to the last conclusion $\rm(c)$ in
Theorem 4.1.

##  5 Experimental examples

This section is dedicated to showing experimental results obtained by using
the algorithms for both unconstrained and constrained cases. The algorithms
are implemented in the computer algebra system Maple, and the results are
obtained on an Intel i7 - 8665U CPU (1.90GHz) with 32 GB of RAM.

As mentioned in Remark 3, we use the package $\mathtt{Groebner}$ of Maple to
handle the tasks in the algorithms. Within our implementation, almost the
tasks are done symbolically except the step isolating real roots of $w(t)$.
Here, we set the variable $\texttt{Digits}:=\deg w+10$, where Digits controls
the number of digits that Maple uses when making calculations with software
floating-point numbers.

Since the input conditions of the algorithms are held generically, we can take
input polynomials randomly. However, we perform here our experiment with the
family of Rosenbrock functions that are usually used as a performance test
problem for optimization algorithms, for instance conn1988testing ; wang2022cs
; shang2006note . These functions are polynomial, sparse, and non-convex:

$f_{n}=\sum_{i=1}^{n-1}\left[100(x_{i}^{2}-x_{i+1})^{2}+(x_{i}^{2}-1)^{2}\right],\
n\geq 2.$

Clearly, $f_{n}$ is in $n$ variables, of degree $4$, and non-negative over
$\operatorname{\mathbb{R}}^{n}$. Its minimum is $0$ and reached at the point
$x^{A}:=(1,\dots,1)\in\operatorname{\mathbb{R}}^{n}$.

###  5.1 The $n$-variable Rosenbrock function over
$\operatorname{\mathbb{R}}^{n}$

The authors in shang2006note  point computationally out that $f_{2}$ and
$f_{3}$ has only one local minimizer. For $4\leq n\leq 7$, $f_{n}$ has two
local minimizers. One of them is $x^{A}$ above and another one is a point
$x^{B}$ that is close to $(-1,1,\dots,1)\in\operatorname{\mathbb{R}}^{n}$,
precisely, when we increase $n$, the first coordinate of $x^{B}$ approaches
$-1$ and other coordinates approach $1$, see (shang2006note, , Table 1).

We demonstrate experimental results of $\operatorname{\mathtt{GRULOM}}$ on
these Rosenbrock functions, $n$ runs from $4$ to $7$. By checking
symbolically, the conditions in Theorem 3.1 are satisfied for these functions.
For example, with $n=7$, $\operatorname{\mathcal{I}}_{\nabla}(f_{7})$ is zero-
dimensional and its complex gradient variety has $243$ distinct points. Among
them, there are only $3$ real points and $\det(\nabla^{2}f_{7})$ has no roots
on these three points.

$n$ | $\deg w$ | $\deg h$ | $\deg r$ |  #real$(w)$ | $\\#\operatorname{loc}$ | $x^{A}_{1}$ | $x^{B}_{1}$ | time (s)
---|---|---|---|---|---|---|---|---
2 | 1 | 4 | 0 | 1 | 1 | 1.0 | – | 0.12
3 | 3 | 8 | 2 | 1 | 1 | 1.0 | – | 0.14
4 | 9 | 32 | 8 | 3 | 2 | 1.0 | -0.77565 | 0.28
5 | 27 | 104 | 26 | 3 | 2 | 1.0 | -0.96205 | 0.91
6 | 81 | 320 | 80 | 3 | 2 | 1.0 | -0.98657 | 2.07
7 | 243 | 968 | 242 | 3 | 2 | 1.0 | -0.99172 | 73.11

Table 1. $\operatorname{\mathtt{GRULOM}}$ computing local minimizers of
Rosenbrock functions over $\operatorname{\mathbb{R}}^{n}$

In Table 1, we have information of the degrees of univariate polynomials $w$,
$h$, and $r$; #real$(w)$ is the number of real roots of $w$;
$\\#\operatorname{loc}$ is the number of local minimizers, the time is in
second (s). Denote $x^{A}_{1}$ and $x^{B}_{1}$ by the first coordinates of the
local minimizers $A$ and $B$, respectively, which are the same to the results
in (shang2006note, , Table 1).

Within $\operatorname{\mathtt{GRULOM}}$, computations are symbolic except
computing real roots of the univariate polynomial $w$. The computation time
grows quickly when we increase $n$ the number of variables. Complexity of the
algorithm must be related to the number of the complex points in the gradient
variety of $f_{n}$ that is characterized by $\deg w$, recall that the maximum
of $\deg w$ can be $(d-1)^{n}$ that is reached generically.

###  5.2 The $2$-variable Rosenbrock function over $\mathbb{S}^{1}$

To illustrate $\operatorname{\mathtt{GRALOM}}$ in details, we do an experiment
for the constrained case by considering the local minimizers of the
$2$-variable Rosenbrock function over the unit circle $\mathbb{S}^{1}$.

Recall that $f=100x_{1}^{4}-200x_{1}^{2}x_{2}+x_{1}^{2}+100x_{2}^{2}-2x_{1}+1$
and $\mathbb{S}^{1}=\\{x\in\operatorname{\mathbb{R}}^{2}:h(x)=0\\}$, where
$h=x_{1}^{2}+x_{2}^{2}-1$ (with $m=1$). The gradient of $h$ is $\nabla
h=\left[2x_{1}\,2x_{2}\right]^{T}$ and its rank is always $1$ on the complex
roots of $h$. The Jacobian matrix of $f$ and $h$ is

$\nabla(f,h)=\begin{bmatrix}400x_{1}^{3}-400x_{1}x_{2}+2x_{1}-2\qquad&\qquad-200x_{1}^{2}+200x_{2}\\\
2x_{1}\qquad&\qquad 2x_{2}\end{bmatrix}.$

This matrix is square, hence $\operatorname{MaxMinors}(\nabla(f,h))$ contains
only one polynomial

$\operatorname{MaxMinors}(\nabla(f,h))=\\{800x_{1}^{3}x_{2}+400x_{1}^{3}-800x_{1}x_{2}^{2}-396x_{1}x_{2}-4x_{2}\\}.$

Then, $\operatorname{\mathcal{I}}_{\nabla}(f,h)$ is generated by $h$ and the
above polynomial. This ideal is zero-dimensional and radical.

The Lagrangian function is the polynomial
$L(x,\lambda)=f(x)+\lambda(x_{1}^{2}+x_{2}^{2}-1)$ in three variables
$x_{1},x_{2}$ and $\lambda$. One has
$\operatorname{rad}(\operatorname{\mathcal{I}}_{\nabla}(L))=\operatorname{\mathcal{I}}_{\nabla}(L)$
since $\operatorname{\mathcal{I}}_{\nabla}(L)$ is radical. With the graded
lexicographical order $x_{1}<x_{2}<\lambda$, the reduced Gröbner basis of
$\operatorname{\mathcal{I}}_{\nabla}(L)$ is in shape position

$\operatorname{\mathcal{I}}_{\nabla}(L)=\left\langle
w(x_{1}),x_{2}-v_{2}(x_{1}),\lambda-v_{3}(x_{1})\right\rangle,$

where

$w=40000x_{1}^{8}+10400x_{1}^{6}-400x_{1}^{5}-70599x_{1}^{4}+598x_{1}^{3}+30200x_{1}^{2}-198x_{1}-1$,

$v_{2}=-\frac{4243600}{21191}x_{1}^{7}+\frac{123600}{21191}x_{1}^{6}-\frac{1106936}{21191}x_{1}^{5}+\frac{72100}{21191}x_{1}^{4}+\frac{748774791}{2119100}x_{1}^{3}\vskip
6.0pt plus 2.0pt minus
2.0pt+\frac{9251509}{2119100}x_{1}^{2}-\frac{320081191}{2119100}x_{1}+\frac{1048491}{2119100}$,

$v_{3}=-\frac{1080000}{21191}x_{1}^{7}-\frac{24720000}{21191}x_{1}^{6}-\frac{1000800}{21191}x_{1}^{5}-\frac{22896400}{21191}x_{1}^{4}+\frac{1486173}{21191}x_{1}^{3}\vskip
6.0pt plus 2.0pt minus
2.0pt+\frac{26937036}{21191}x_{1}^{2}-\frac{194182}{2119100}x_{1}-\frac{2120027}{21191}$.

The Hessian matrix of $L$ with respect to $x$ is
$\nabla^{2}_{xx}L=\nabla^{2}f+2\lambda I,$ where $I$ is the $2\times 2$
identity matrix and

$\nabla^{2}f=\begin{bmatrix}1200x_{1}^{2}-400x_{1}+2\qquad&\qquad-400x_{1}\\\
-400x_{1}\qquad&\qquad 200\end{bmatrix}.$

By substituting $x_{2}$ and $\lambda$ by $v_{2}(t)$ and $v_{3}(t)$
respectively in $\nabla^{2}_{xx}L$, we obtain the matrix $H(t)$ at Line 3 in
Algorithm 3. The matrix $K(t)$ at Line 4 is given by

$K(t):=\\{u\in\operatorname{\mathbb{R}}^{2}:tu_{1}+v_{2}(t)u_{2}=0\\}.$

From the above results, we have a univariate representation for the set of
local minimizers of $f$ over $\operatorname{\mathbb{S}}^{1}$:

$\\{w(t)=0,x_{1}=t,x_{2}=v_{2}(t),\;H(t)\succ_{K(t)}0\\}.$

By isolating $w$, we obtain $6$ real roots:

-0.8684745451 | -0.7839301862 | -0.0033445316
---|---|---
0.0099009901 |  0.7864151542 |  0.8658463102

There are three points where $H(t)\succ_{K(t)}0$. This allows us to conclude
that $f$ has three local minimizers, denoted by $A,B,C$ whose coordinates are
listed in Table 2.

point | $x_{1}$ | $x_{2}$ | $f(x)$
---|---|---|---
$A$ | -0.7839301862 |  0.6208489858 | 3.186378996
$B$ |  0.0099009901 | -0.9999509840 | 100.9900990
$C$ |  0.7864151542 |  0.6176983125 | 0.045674808

Table 2. Local minimizers of the 2-variable Rosenbrock function over
$\mathbb{S}^{1}$

## Perspectives

We are able to estimate bit complexity of the proposed algorithms when the
coefficients of the input data are rational relying on an algorithm solving
multi-homogeneous polynomial systems safey2018 . We plan to handle the
constrainted problems whose constraint sets are given by inequalities.
Moreover, we shall extend the technique in the paper to other problems in
optimization theory with polynomial data hieutakeda2023b  such as the
polynomial and tensor complementary problem gowda2016polynomial ;
huang2019tensor , polynomial variational inequality hieu2020solution ,
polynomial bilevel optimization problem nie2021lagrange , and polynomial
equilibrium problem nie2023nash .

## References

  * (1) Nie, J.: Optimality conditions and finite convergence of Lasserre’s hierarchy.  Mathematical programming 146, 97–121 (2014)
  * (2) Lasserre, J.B.: Global optimization with polynomials and the problem of moments.  SIAM Journal on optimization 11(3), 796–817 (2001)
  * (3) Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems.  Mathematical programming 96, 293–320 (2003)
  * (4) Parrilo, P.A., Sturmfels, B.: Minimizing polynomial functions.  Algorithmic and quantitative real algebraic geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science pp. 83–99 (2003)
  * (5) Nie, J., Demmel, J., Sturmfels, B.: Minimizing polynomials via sum of squares over the gradient ideal.  Mathematical Programming 106(3), 587–606 (2006)
  * (6) Lasserre, J.B.: Moments, positive polynomials and their applications, vol. 1.  World Scientific (2009)
  * (7) Laurent, M.: Sums of squares, moment matrices and optimization over polynomials.  In: Emerging applications of algebraic geometry, pp. 157–270. Springer (2009)
  * (8) Nie, J.: The hierarchy of local minimums in polynomial optimization.  Mathematical programming 151(2), 555–583 (2015)
  * (9) He, L., Wang, Y.: An efficient saddle point search method using kriging metamodels.  Proceedings of the ASME 2015 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference pp. V01AT02A008–V01AT02A008 (2015)
  * (10) Morrow, Z., Kwon, H.Y., Kelley, C.T., Jakubikova, E.: Efficient approximation of potential energy surfaces with mixed-basis interpolation.  Journal of Chemical Theory and Computation 17(9), 5673–5683 (2021)
  * (11) Kawaguchi, K.: Deep learning without poor local minima.  Advances In Neural Information Processing Systems pp. 586–594 (2016)
  * (12) Yalcin, B., Zhang, H., Lavaei, J., Sojoudi, S.: Factorization approach for low-complexity matrix completion problems: Exponential number of spurious solutions and failure of gradient methods.  Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS) 2022 151 (2022)
  * (13) Mehta, D., Chen, T., Tang, T., Hauenstein, J.D.: The loss surface of deep linear networks viewed through the algebraic geometry lens.  IEEE Transactions on Pattern Analysis and Machine Intelligence 44(9), 5664–5680 (2022)
  * (14) Martínez, J.M.: Local minimizers of quadratic functions on Euclidean balls and spheres.  SIAM Journal on Optimization 4(1), 159–176 (1994)
  * (15) Phu, H.X., Yen, N.D.: On the stability of solutions to quadratic programming problems.  Mathematical programming 89, 385–394 (2001)
  * (16) Ahmadi, A.A., Zhang, J.: On the complexity of finding a local minimizer of a quadratic function over a polytope.  Mathematical Programming 195(1-2), 783–792 (2022)
  * (17) Pardalos, P.M., Schnitger, G.: Checking local optimality in constrained quadratic programming is NP-hard.  Operations Research Letters 7(1), 33–35 (1988)
  * (18) Pham, T.S.: Local minimizers of semi-algebraic functions from the viewpoint of tangencies.  SIAM Journal on Optimization 30(3), 1777–1794 (2020)
  * (19) Cox, D., Little, J., OShea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra.  Springer Science & Business Media (2013)
  * (20) Bertsekas, D.P.: Nonlinear Programming.  Athena Scientific (1999)
  * (21) Gianni, P., Mora, T.: Algebraic Solution of systems of polynomial equations using Gröbner bases.  In: Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-5, volume 356 of LNCS, pp. 247–257. Springer (1989)
  * (22) Magron, V., Safey El Din, M., Vu, T.H.: Sum of squares decompositions of polynomials over their gradient ideals with rational coefficients.  SIAM Journal on Optimization 33(1), 63–88 (2023)
  * (23) Rouillier, F.: Solving zero-dimensional systems through the rational univariate representation.  Applicable Algebra in Engineering, Communication and Computing 9(5), 433–461 (1999)
  * (24) Nie, J., Ranestad, K.: Algebraic degree of polynomial optimization.  SIAM Journal on Optimization 20(1), 485–502 (2009)
  * (25) Conn, A.R., Gould, N.I., Toint, P.L.: Testing a class of methods for solving minimization problems with simple bounds on the variables.  Mathematics of computation 50(182), 399–430 (1988)
  * (26) Wang, J., Magron, V., Lasserre, J.B., Mai, N.H.A.: CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization.  ACM Transactions on Mathematical Software 48(4), 1–26 (2022)
  * (27) Shang, Y.W., Qiu, Y.H.: A note on the extended Rosenbrock function.  Evolutionary Computation 14(1), 119–126 (2006)
  * (28) Safey El Din, M., Schost, É.: Bit complexity for multi-homogeneous polynomial system solving–application to polynomial minimization.  Journal of Symbolic Computation 87, 176–206 (2018)
  * (29) Hieu, V.T., Takeda, A.: Univariate representations in optimization with polynomial data having rational coefficients.  In progress (2023)
  * (30) Gowda, M.S.: Polynomial complementarity problems.  Pacific Journal of Optimization 13(2), 227–241
  * (31) Huang, Z.H., Qi, L.: Tensor complementarity problems-part I: basic theory.  Journal of Optimization Theory and Applications 183, 1–23 (2019)
  * (32) Hieu, V.T.: Solution maps of polynomial variational inequalities.  Journal of Global Optimization 77(4), 807–824 (2020)
  * (33) Nie, J., Wang, L., Ye, J.J., Zhong, S.: A lagrange multiplier expression method for bilevel polynomial optimization.  SIAM Journal on Optimization 31(3), 2368–2395 (2021)
  * (34) Nie, J., Tang, X.: Nash equilibrium problems of polynomials.  Mathematics of Operations Research (2023)