1 Introduction

In this paper, we focus on finding global minimizers of polynomials of even degree. J. Lasserre [1, 2] showed that if a polynomial of even degree has a global minimizer inside a closed ball then the global minimum can be approximated as closely as desired by solving a finite sequence of positive semi-definite programs. Recently, J. Zhu [3] obtained a ball containing the global minimizers of such a polynomial. In [3], the unconstrained minimization of a polynomial is reduced to some constrained optimizations. In this paper, when global minimizers of the polynomial are inside a closed ball, the global minimization of the polynomial is solved by a backward differential flow.

The paper is organized as follows. In Sect. 2, we briefly mention the main result in [3] on obtaining a closed ball containing all global minimizers of the polynomial and reducing the global unconstrained minimization to a constrained optimization problem. We introduce the backward differential flow by the K–T equation (the K–T equation is defined by the K-T optimality condition in optimization theory) with respect to a ball-constrained optimization problem in Sect. 3. In Sect. 4, we solve the global minimization of a polynomial by a backward differential flow. Some examples are provided and an algorithm is given in Sect. 5. In the last section, we present concluding remarks.

2 The Bounds of Global Minimizers

Given a real-valued polynomial \(P(x):\mathbb{R}^{n}\longrightarrow \mathbb{R}\), we are interested in solving the problem (P):

$$ P^* := \min\bigl\{P(x)\mid x\in \mathbb{R}^n\bigr\}, $$
(1)

that is, finding the global minimum P ∗ of P(x) and, if possible, a global minimizer x ∗ [1, 2]. In this paper, we focus on the polynomial having the form:

$$ P(x)=x_1^{2m}+\cdots+x_n^{2m}+ g(x_1,x_2,\dots,x_n). $$
(2)

where g(x 1,x 2,…,x n ) is a real-valued polynomial of degree less than or equal to 2m−1.

In this section, we briefly introduce the result in [3] for estimating a bounds of global minimizers.

For a given positive integer m, we pose the constrained optimization as follows:

$$ \begin{aligned} &\mbox{min} \quad J_{2m}(s):=\sum _{\{1\le k_1,k_2,\dots,k_{2m}\le n\}}\frac{\partial^{2m} P(0)}{\partial x_{k_1}\partial x_{k_2}\cdots\partial x_{k_l}}s_{k_1}s_{k_2}\cdots s_{k_{2m}} \\ &\mbox{s.t.}\quad \ \ \|s\|^2= s_1^2+s_2^2+ \cdots+s_n^2=1. \end{aligned} $$
(3)

Let I 2m denote the minimum of the optimization problem (3).

Theorem 2.1

([3])

If I 2m >0, then all global minimizers of problem (1) stay in ∥x∥<σ 2m , where \(\sigma_{2m}:= \max\{1, \frac{(2m)!(n+\frac{n^{2}}{2!}+\cdots+\frac{n^{2m-1}}{(2m-1)!})M_{2m-1}}{I_{2m}}\}\) and

$$ M_{2m-1}=\max\biggl\{\biggl \vert \frac{\partial^l P(0)}{\partial x_{k_1}\partial x_{k_2}\cdots\partial x_{k_l}}\biggr \vert : 0\le l\le 2m-1; 1\le k_1,\dots,k_l\le n\biggr\}. $$
(4)

Clearly, if there is a global minimizer such that ∥x∥<a for some a>0, then (1) is equivalent to the following constrained optimization:

$$ \begin{aligned} &\mbox{min}\quad P(x) \\ &\mbox{s.t.}\quad \|x\|\le a. \end{aligned} $$
(5)

3 The Backward Differential Flow

In this section, we introduce the backward differential flow to find the global minimizers to the following optimization problem (P1):

$$ \begin{aligned} &\min\quad P(x) \\ &\mbox{s.t.}\quad \ \ x\in D:= \bigl\{x\in \mathbb{R}^n\mid \|x\|\le a \bigr\} \end{aligned} $$
(6)

where P(x) is a twice continuously differentiable function on \(\mathbb{R}^{n}\).

In what follows, we construct the differential system [4, 5] to deal with the global optimization (6).

We consider the function P(x) to be twice continuously differentiable in \(\mathbb{R}^{n}\). Define the set

$$ G=\bigl\{\rho\ge 0\mid \bigl[\nabla^2 P( x)+\rho I \bigr]>0, \forall x\in D\bigr\}. $$
(7)

Clearly, if \(\hat{\rho}\in G\) then ρ∈G for \(\forall \rho \ge \hat{\rho}\).

When there is a pair \((\hat{\rho},\hat{x})\in G\times D\) satisfying the following equation

$$ \nabla P(\hat{x})+\hat{\rho}\hat{x}=0, $$
(8)

we focus on the flow \(\hat{x}(\rho)\) which is well-defined near \(\hat{\rho}\) by the initial value problem

(9)
(10)

As long as the \(\nabla^{2} P(\hat{x}(\rho))+\rho I>0\), by the theory of ordinary differential equations, the flow \(\hat{x}(\rho)\) can be extended for ρ in an interval I⊂[0,+∞[. The dual function with respect to the given flow \(\hat{x}(\rho)\) is defined as follows:

$$ P_d(\rho)=P\bigl(\hat{x}(\rho)\bigr)+\frac{\rho}{2} \bigl[\hat{x}^T(\rho)\hat{x}(\rho)-a^2\bigr]. $$
(11)

Lemma 3.1

For a given flow defined by (9) and (10), we have

(12)
(13)

Proof

Since P d (ρ) is differentiable,

$$\begin{aligned} \frac{dP_d(\rho)}{d\rho}&=\frac{dP(\hat{x}(\rho))}{d\rho}+\frac{1}{2}\hat{x}^T( \rho)\hat{x}(\rho)+\frac{1}{2}\rho\frac{d(\hat{x}^T(\rho)\hat{x}(\rho))}{d\rho}-\frac{a^2}{2} \\ &=\nabla P\bigl(\hat{x}(\rho)\bigr)\frac{d(\hat{x}(\rho))}{d\rho}+\frac{1}{2}\hat{x}^T(\rho)\hat{x}(\rho)+\frac{1}{2}\rho\frac{d(\hat{x}^T(\rho)\hat{x}(\rho))}{d\rho}- \frac{a^2}{2} \\ &=-\rho\hat{x}^T(\rho)\frac{d(\hat{x}(\rho))}{d\rho}+\frac{1}{2}\hat{x}^T(\rho)\hat{x}(\rho)+\frac{1}{2}\rho\frac{d(\hat{x}^T(\rho)\hat{x}(\rho))}{d\rho}- \frac{a^2}{2} \\ &=\frac{-1}{2}\rho\frac{d(\hat{x}^T(\rho)\hat{x}(\rho))}{d\rho}+\frac{1}{2}\hat{x}^T(\rho)\hat{x}(\rho)+\frac{1}{2}\rho\frac{d(\hat{x}^T(\rho)\hat{x}(\rho))}{d\rho}- \frac{a^2}{2} \\ &=\frac{1}{2}\hat{x}^T(\rho)\hat{x}(\rho)-\frac{a^2}{2}. \end{aligned}$$

Further, since P(x) is twice continuously differentiable, by (12) we have

$$\begin{aligned} \frac{d^2 P_d(\rho)}{d{\rho}^2}&=\hat{x}^T(\rho)\frac{d\hat{x}(\rho)}{d\rho} \\ &=-\biggl(\frac{d\hat{x}(\rho)}{d\rho}\biggr)^T\bigl[\nabla^2 P \bigl(\hat{x}(\rho)\bigr)+ \rho I\bigr]\frac{d\hat{x}(\rho)}{d\rho}. \end{aligned}$$

 □

Lemma 3.2

Let \(\hat{x}(\rho)\) be a given flow defined by (9) and (10), and let P d (ρ) be the corresponding dual function defined by (11). We have: (i) For every ρ∈G, \(\frac{d^{2} P_{d}(\rho)}{d{\rho}^{2}}\le 0\); (ii) If \(\hat{\rho}\in G\), then \(\frac{dP_{d}(\rho)}{d\rho}\) monotonously decreases in \([\hat{\rho}, +\infty[\); (iii) If \(\hat{\rho}\in G\), in \(]\hat{\rho},+\infty[\), P d (ρ) is monotonously decreasing.

Proof

When ρ∈G, by the definition of G, we have \(\nabla^{2} P(\hat{x}(\rho))+ \rho I>0\). It follows from (13) that \(\frac{d^{2} P_{d}(\rho)}{d{\rho}^{2}}\le 0\). Consequently, by Lemma 3.1, we see that \(\frac{dP_{d}(\rho)}{d\rho}\) monotonously decreases in \([\hat{\rho}, +\infty[\) when \(\hat{\rho}\in G\). Finally, since \(\hat{x}(\hat{\rho})\in D\), \(\frac{dP_{d}(\hat{\rho})}{d\rho}\le 0\) by (12). It follows from \(\hat{\rho}\in G\) that \(\frac{dP_{d}(\rho)}{d\rho}\le 0\) in \([\hat{\rho}, +\infty)\) because \(\frac{dP_{d}(\rho)}{d\rho}\) monotonously decreases. Thus, P d (ρ) is monotonously decreasing in \(]\hat{\rho},+\infty[\). □

Definition 3.1

Let \(\hat{x}(\rho)\) be a flow defined by (9) and (10). We call \(\hat{x}(\rho),\rho \in [0,\hat{\rho}]\) the backward differential flow iff \(\hat{x}(\rho)\) is well-defined on \([0,\hat{\rho}]\) such that \(\nabla^{2} P(\hat{x}(\rho))+\rho I>0\) on \([0,\hat{\rho}]\).

In other words, the backward differential flow \(\hat{x}(\rho),\ \rho\in ]0,\hat{\rho}]\) is the solution which solves (9) backwards from \(\hat{\rho}\).

4 Finding a Global Minimizer by the Backward Differential Flow

In this section, we use the backward differential flow to find a global minimizer of the function P(x) in (6) over D. Since D is a closed ball with the center at the origin of \(\mathbb{R}^{n}\) and P(x) is twice continuously differentiable, we can choose a large positive parameter ρ ∗ such that ∇2 P(x)+ρ ∗ I>0, ∀x∈D and ρ ∗>sup D {∥∇2 P(x)∥}. If ∇P(0)≠0, noting that \(\|\frac{\nabla^{2} P(x)}{\rho^{*}}\|<1\) uniformly on D, then there is a unique nonzero fixed point x ∗∈D such that

$$ \frac{-\nabla P(x^*)}{\rho^*}=x^* $$
(16)

by Brown’s fixed-point theorem [6]. It means that, for the pair (x ∗,ρ ∗),

$$ \nabla P\bigl(x^*\bigr)+\rho^* x^*=0,\qquad \nabla^2 P(x)+ \rho^* I>0, \quad \forall x\in D. $$
(17)

We solve

(18)
(19)

backwards from ρ ∗ to get the flow \(\hat{x}(\rho), \rho \in [0,\rho^{*}]\).

By Theorem 2.1 in Sect. 2, we can take a positive real a such that all global minimizers of P(x) over \(\mathbb{R}^{n}\) staying inside ∥x∥<a. Particularly, there is no global minimizer of P(x) on the boundary ∥x∥=a.

In the following, we assume that ∇P(0)≠0. If this is not the case, we can carry out a coordinate conversion by selecting a vector z with ∥z∥<a to make the function Q(y):=P(y+z) such that ∇Q(0)=∇P(z)≠0 and get a bound b>0 such that a+∥z∥<b. It follows that the global minimizers of Q(y) are all inside ∥y∥<b since the global minimizers of P(x) are all inside ∥x∥<a. In fact, if Q(y) has a global minimizer \(\bar{y}\) such that \(\|\bar{y}\|\ge b\), then \(\bar{x}:=\bar{y}+z\) is a global minimizer of P(x) since for every \(x\in \mathbb{R}^{n}\) and y=x−z, \(P(x)=P(y+z)=Q(y)\ge Q(\bar{y})=P(\bar{y}+z)=P(\bar{x})\). But \(\|\bar{x}\|\ge \|\bar{y}\|-\|z\| \ge b-\|z\|>a\). It contradicts to the fact that all global minimizers of P(x) over \(\mathbb{R}^{n}\) stay inside ∥x∥<a.

By (16), when \(\nabla^{2} P(\hat{x}(\rho))+\rho I>0\),

$$ \frac{d(\nabla P(\hat{x}(\rho))+ \rho\hat{x}(\rho))}{d\rho}=\bigl[\nabla^2 P\bigl(\hat{x}(\rho) \bigr)+\rho I\bigr]\frac{d\hat{x}(\rho)}{d\rho} +\hat{x}(\rho)=0, $$
(20)

it follows from (15) and (17) that along the flow \(\hat{x}(\rho)\)

$$ \nabla P\bigl(\hat{x}(\rho)\bigr)+ \rho\hat{x}(\rho)=0. $$
(21)

If the flow \(\hat{x}(\rho)\) can be extended backwards to ρ=0, then we have \(\nabla P(\hat{x}(0))= 0\). In the following, we assume that the backward flow \(\hat{x}(\rho)\) can be well defined on [0,ρ ∗].

Theorem 4.1

If the backward flow \(\hat{x}(\rho)\) is located in ∥x∥<a and on D, ∇2 P(x)+ρI>0 holds on ]0,ρ ∗], then \(\hat{x}(0)\) is a global minimizer of P(x) over \(\mathbb{R}^{n}\).

Proof

Since the backward flow \(\hat{x}(\rho)\) is located in ∥x∥<a and on D, ∇2 P(x)+ρI>0 holds on ]0,ρ ∗], the dual function P d (ρ) is well defined. It follows from Lemma 3.2 that P d (ρ) is concave and monotonously decreasing on [0,ρ ∗]. By the Lagrange duality theory [5], from Lemma 3.1, we have

$$ \min_D P(x)\ge \max_{\rho\in [0,\rho^*]} P_d(\rho). $$
(22)

Because P d (ρ) is monotonously decreasing on [0,ρ ∗],

$$ P_d(0)=\max_{\rho\in [0,\rho^*]} P_d( \rho). $$
(23)

Thus for every x∈D

$$ P(x)\ge P_d(0)=P\bigl(\hat{x}(0)\bigr)+ \frac{0}{2}\bigl(\hat{x}^T(0)\hat{x}(0)-a^2\bigr)=P \bigl(\hat{x}(0)\bigr). $$
(24)

Consequently, \(\hat{x}(0)\) is a global minimizer of P(x) over D. Noting that the ball D contains a global minimizer of P(x) over \(\mathbb{R}^{n}\), we deduce that \(\hat{x}(0)\) is a global minimizer of P(x) over \(\mathbb{R}^{n}\). □

5 Examples

Example 5.1

Let us take a look at the polynomial which is non-convex on \(\mathbb{R}\):

$$ P(x)=\frac{x^4}{4}+\frac{x^3}{3}-x^2-2x. $$
(25)

Consider the global optimization problem

$$ \min\bigl\{P(x)\mid x\in \mathbb{R}^1\bigr\}. $$
(26)

By Sect. 2, we may get bounds of the global minimizer of P(x) over \(\mathbb{R}\):

$$\begin{aligned} \sigma_{2m}&= \max\biggl\{1, \frac{(2m)!(n+\frac{n^2}{2!}+\cdots+\frac{n^{2m-1}}{(2m-1)!})M_{2m-1}}{I_{2m}}\biggr\} \\ &= \frac{4!(1+\frac{1}{2!}+\frac{1}{3!})2}{24}= \frac{10}{3} \end{aligned}$$

with

$$ M_3=\max\{2, 2,2,0\}=2 $$
(28)

and

$$ I_4=4! \min\bigl\{s_1^4: s_1^2=1\bigr\}=24. $$
(29)

The global optimization problem is equivalent to

$$ \begin{aligned} &\mbox{min}\quad P(x) \\ &\mbox{s.t.}\quad \ \ \|x\|\le \frac{10}{3}. \end{aligned} $$
(30)

Let us solve it with following steps:

Step 1.:

Choose ρ ∗=100 and solve the equation

$$x^3+x^2-2x-2+\rho^*x=0 $$

to get the unique real root x ∗=0.0204 by using Matlab.

Step 2.:

Solve the backward differential equation

$$\frac{dx}{dt}=\frac{-x}{3x^2+2x-2+t},\quad x(100)=0.0204, $$

with Matlab to get the value of its solution at t=0

$$\hat{x}(0)=1.4141, $$

which is just an approximation to the global minimizer of problem (24).

Remark 5.1

By the statement in the first paragraph of Sect. 4, here we select ρ ∗=100 due to an estimation

$$\begin{aligned} \max_{\|x\|\le \frac{10}{3}}\bigl\{\bigl\|P''(x)\bigr\|\bigr \}<100 . \end{aligned}$$

Using Matlab, the backward differential equation gives the unique flow \(\hat{x}(t)\) which implies that

$$\begin{aligned} 3\hat{x}^2(t)+2x(t)-2+t>0,\quad t\in [0,100]. \end{aligned}$$

We see that \(\hat{x}^{2}(0)<2.0164<\frac{10}{3}\). By Lemma 3.2, \(\hat{x}^{2}(t)\) is monotonously decreasing on [0,100]. Thus the backward flow \(\hat{x}(t)\) can be extended in [0,100] and kept such that \(\|x\|\le \frac{10}{3}\). By Theorem 4.1, \(\hat{x}(0)\) is a global minimizer of problem (24).

Example 5.2

Consider the polynomial P(x) on \(\mathbb{R}^{2}\):

$$ P(x)=x_1^4+x_2^4+3x_1^2+3x_2^2+2x_1x_2+2x_1+2x_2+3. $$
(33)

In this example, we discuss the global optimization problem

$$ P^* := \min\bigl\{P(x)\mid x\in \mathbb{R}^2\bigr\}. $$
(34)

Noting that, \(P^{*}=\min\{P(x)\mid x\in \mathbb{R}^{2}\}\approx 2.5074, p^{mom}\approx -0.4926 \) (where p mom stands for the lower bound of P ∗ by the moment relaxations [1]), it is shown in [1] by J. Lasserre that the polynomial P(x)−P ∗ is not a sum of squares ([1], see Example 1). Thus, it follows from the statement of M. Laurent (p. 113 in [7]) that the global optimal value of this polynomial cannot be found by Lasserre’s SDP relaxation with a finite relaxation order.

In the following, we solve the unconstrained optimization problem (29) by a backward differential flow.

We may get the bound of the global minimizer of P(x) over \(\mathbb{R}^{2}\) as follows. Noting that n=m=2, with

$$ M_3=\max\{6, 2,2,3\}=6 $$
(35)

and

$$ I_4=4! \min\bigl\{s_1^4+s_2^4: s_1^2 +s_1^2=1\bigr\}=12, $$
(36)

we have the bound

$$\begin{aligned} \sigma_{2m} &= \max \biggl\{1, \frac{(2m)!(n+\frac{n^2}{2!}+\cdots+\frac{n^{2m-1}}{(2m-1)!})M_{2m-1}}{I_{2m}} \biggr\} \\ &= \frac{4!(2+\frac{2^2}{2!}+\frac{2^3}{3!})6}{12}= 64. \end{aligned}$$

The global optimization problem is equivalent to

$$ \begin{aligned} & \mbox{min}\quad P(x) \\ &\mbox{s.t.}\quad \ \ \|x\|\le 64. \end{aligned} $$
(38)

Using the method of the backward flow, we solve the global optimization problem (29) with the following steps:

Step 1.:

Choose ρ ∗=1000 and solve the system of equations

$$\begin{aligned} &4x_1^3+6x_1+2x_2+2+1000x_1=0, \\ &4x_2^3+6x_2+2x_1+2+1000x_2=0 \end{aligned}$$

to get the unique real root \(x_{1}^{*}\approx -0.00198, x_{2}^{*}\approx -0.00198\) by using Matlab.

Step 2.:

Solve the backward differential equation

$$\begin{aligned} &\dot{x}_1=\frac{2x_2-x_1(12x_2^2+6+\rho)}{(12x_1^2+6+\rho)(12x_2^2+6+\rho)-4}, \\ &\dot{x}_2=\frac{2x_1-x_2(12x_1^2+6+\rho)}{(12x_1^2+6+\rho)(12x_2^2+6+\rho)-4}, \\ &x_1(1000)=-0.00198,\qquad x_2(1000)=-0.00198 \end{aligned}$$

with Matlab to get the value of its solution at ρ=0

$$\begin{aligned} x_1(0)=-0.2428,\qquad x_2(0)=-0.2428, \end{aligned}$$

which is the global minimizer of problem (29).

Remark 5.2

For solving the differential equations which have no easy solutions, we present an algorithm as follows. To compute the backward differential flow, we use the following discrete format for Δρ>0 and Δρ<ρ≤ρ ∗,

$$\hat{x}(\rho-\Delta \rho)=\hat{x}(\rho)+\Delta \rho \bigl(\nabla^2 P \bigl(\hat{x}(\rho)\bigr)+\rho I\bigr)^{-1}\hat{x}(\rho). $$

Algorithm 5.1

Step 1.:

Given reals ϵ,μ>0 and a positive integer N, choose ρ ∗>max D {∥∇2 P(x)∥}. Let \(h=\frac{\rho^{*}}{N}\).

Step 2.:

Compute x ∗ solving ∇P(x)+ρ ∗ x=0. Denote x N =x ∗.

Step 3.:

For i=1,2,…,N, ρ i =ih. If ∇2 P(x i )+ρ i I>μI, then compute

$$x_{i-1}=x_{i}+h \bigl(\nabla^2 P(x_i)+\rho_i I\bigr)^{-1}x_i. $$
Step 4.:

The case of i>1: If ∥∇P(x i−1)+ρ i−1 x i−1∥≤ϵ, then take i=i−1 and go to Step 3. If

$$\bigl\|\nabla P(x_{i-1})+ \rho_{i-1} x_{i-1}\bigr\|> \epsilon, $$

then take N=10N and go to Step 1.

Step 5.:

The case of i=1: If ∥∇P(x 0)+ρ 0 x 0∥>ϵ, then take N=10N and go to Step 1. If ∥∇P(x 0)+ρ 0 x 0∥≤ϵ, then x 0 is an approximation to a global minimizer.

To compute the global minimizer of problem (5) in Example 5.1, we choose \(D=\{|x|\le \frac{10}{3}\}, \rho^{*}=100\), ϵ=10−4, μ=10−2, and N=1000. By using the algorithm above, we obtain the global minimizer \(\hat{x}(0)=1.4141\).

6 Conclusions

In this paper, a new approach to global optimization of polynomials is presented. We focus on finding solutions to a class of problems with polynomials of even degree, which is an important objective in the research of global optimization. As the first step of this approach, we convert the original unconstrained optimization problem to a ball-constrained optimization problem. Then a differential equation is established by the K–T equation with the ball-constrained nonlinear programming. The main contribution is the development of the constructive backward differential flow which can be effectively used for finding a global minimizer. The numerical algorithm for computing the flow developed in this work is based on the Euler’s method and the K–T equality. This is also an attempt to deal with global optimization by using a differential system. Further research on the backward differential flow is needed for it to be applicable when solving other global optimization problems.