ABSTRACT

This paper deals with the global optimization of several variables Holderian functions. An algorithm using a sequence of overestimators of a single variable objective function was developed converging to the maximum. Then by the use of α-dense curves, we show how to implement this algorithm in a multidimensional optimization problem. Finally, we validate the algorithm by testing it on some test functions.

Subject Areas:

Numerical Mathematics, Operational Research

Keywords:

Global Optimization, Branch and Bound, Holderian Functions, Alienor Method

1. Introduction

When modeling economic, biologic, …, systems, we often meet situations where we are led to minimize or maximize objective multivariate functions [1] . Generally, we are seeking global optimums. It’s well known that global optimization algorithms are scare, when compared to the local optimization ones [2] , and when they exist, their implementation is not so obvious. This difficulty increases when the number of the decision variables gets higher.

In this paper, the objective function is deterministic and available and the variables are bounded but the derivative information is either unavailable or its manipulation is expensive.

When information derivative is not required, many authors have used the regularity of the objective function to elaborate algorithms giving the optimum [3] [4] .

Shubert [5] , Ammar and Cherruault [6] [7] , Evtushenko Ya. G., Malkova V. U. and Stanevichyus A. A. [8] , Gergel V. P. and Sergeyev Ya. D. [9] , Sergeyev Y. D. and Kvasov D. E. [10] considered the case where the objective function is lipschitzian. They developed methods generating sequences converging to the optimum. Other authors, Gourdin E. Jaumard B. and Ellaia R. [11] , Lera D. and Sergeyev Ya. D. [12] , Rahal M. and Ziadi A. [13] , processed the case of holderian functions by trying to elaborate a sequence to converge to the optimum; except that, here, obtaining a sequence, to converge to the optimum, is not so obvious.

In this paper, we are also interested in holderian objective functions. We will develop a technique to solve a multidimensional optimization problem.

In the first part of this paper we define a sequence of overestimators of a single variable function. Then we describe a global optimization algorithm suitable to such functions converging to the global maximum. Then after, we show how we can give an approximating value of the maximum of a several-variables holderian function. To do this, we introduce, in the second part, the Lissajous α-dense curve: the tool that allows to go from a multidimensional optimization problem to a single dimensional one. We end this paper by validating our algorithm testing it on some test functions [14] .

2. Optimization of a Single Variable Hoderian Function

Let’s consider a single variable holderian function f defined on an interval

$\left[a,b\right]\subset ℝ$ .

Let’s denote by (P) the following unidimensional optimization problem:

(P) $\{\begin{array}{l}\text{Maximize}f\left(x\right)\\ x\in \left[a,b\right]\end{array}$

In fact, we will not search the exact solution $x_{opt}$ of this problem, we just want to have its approximated value. To achieve this, we will develop a global optimization algorithm suited to holderian functions, that will give an approximation $x^{*}$ such that $\left|f\left(x_{opt}\right)-f\left(x^{*}\right)\right|\le {\epsilon }_0$ where ${\epsilon }_0>0$ , is the required accuracy a priori chosen. This algorithm is based on a sequence of overestimators.

2.1. Overestimator of a Holderian Function

Definition 1. A real multivariate function f is said to be holderian on a set $X\subset {ℝ}^n$ , if there exists $k>0$ and $\beta >1$ such that $\forall x\in X$ and $y\in X$ :

$\left|f\left(x\right)-f\left(y\right)\right|\le k{\left|x-y\right|}^{\frac{1}{\beta }}$ .

Definition 2. A function F is said to be an overestimator of a function f on a set X if:

$\forall x\in X,F\left(x\right)\ge f\left(x\right)$ .

Proposition 1. Let f be a holderian univariate function defined on the interval $\left[a,b\right]$ and let $y\in \left[a,b\right]$ . The function H defined on $\left[a,b\right]$ by: $\forall x\in \left[a,b\right]$

$H\left(x\right)=f\left(y\right)+k{\left|x-y\right|}^{\frac{1}{\beta }}$ .

is an overestimator of f on $\left[a,b\right]$ .

Proof. Let’s set $y\in \left[a,b\right]$ , As f is holderian: $\forall x\in \left[a,b\right]$

$\left|f\left(x\right)-f\left(y\right)\right|\le k{\left|x-y\right|}^{\frac{1}{\beta }}$ .

This yields: $f\left(x\right)-f\left(y\right)\le k{\left|x-y\right|}^{\frac{1}{\beta }}$ .

Hence, $f\left(x\right)\le f\left(y\right)+k{\left|x-y\right|}^{\frac{1}{\beta }}=H\left(x\right)$ .

2.2. Sequence of Overestimators

Let $x_0=a$ the left bound of [a, b] and let’s set:

$F_0\left(x\right)=f\left(x_0\right)+k{\left|x-x_0\right|}^{\frac{1}{\beta }}=G_0(\; x\; )$

an overestimator of f whose representative curve is given by Figure 1.

The curve has one vertex $V_1\left(u_1=b,H_1\right)$ such that:

$H_1=f\left(x_0\right)+k{\left|b-x_0\right|}^{\frac{1}{\beta }}=\underset{x\in \left[a,b\right]}{\max }{G}_0(\; x\; )$

Let’s set $x_1=\arg \max \left(G_0\left(x\right)\right)$ . Here, $x_1=b$ . From the point that coordinates are $\left(x_1,f\left(x_1\right)\right)$ , we plot the curve of the overestimator:

$F_1\left(x\right)=f\left(x_1\right)+k{\left|x-x_1\right|}^{\frac{1}{\beta }}$

as shown in Figure 2. We set:

$G_1\left(x\right)=\min (F_1\left(x\right),G_0(\; x\; )\; )$

and $x_2=\arg \max \left(G_1\left(x\right)\right)$ .

The vertex $V_1$ is anymore a vertex of the curve of $G_1$ . It’s replaced by a new vertex ${V^{\prime }}_1\left(x_2,G_1\left(x_2\right)\right)$ , given by the intersection of the curves of $G_1$ and $F_1$ .

The real $x_2$ is solution of the following equation:

$f\left(x_0\right)+k{\left|x_2-x_0\right|}^{\frac{1}{\beta }}=f\left(x_1\right)+k{\left|x_2-x_1\right|}^{\frac{1}{\beta }}$

In general, it is not easy to have the exact value of the solution of the equation above. For this reason, we will introduce an auxiliary function $O_1$ that allows to give a value nearby to $x_2$ that we also denote by $x_2$ .

The point ${V^{\prime }}_1\left(x_2,G_1\left(x_2\right)\right)$ is between two neighbouring points belonging to the curve of $G_1$ : one on its left $L\left(x_0,f\left(x_0\right)\right)$ and one in its right $R\left(x_1,f\left(x_1\right)\right)$ . We denote by:

・ $M_1=\max \left(f\left(x_0\right),f\left(x_1\right)\right)$

・ $m_1=\min \left(f\left(x_0\right),f\left(x_1\right)\right)$

・ ${\mu }_1=\arg \max \left(f\left(x_0\right),f\left(x_1\right)\right)$

・ ${\rho }_1=\arg \min \left(f\left(x_0\right),f\left(x_1\right)\right)$

According to the Figure 2, and in this case, $M_1=f\left(x_1\right)$ and $m_1=f\left(x_0\right)$ . Let’s set $z_1$ in $\left[x_0,x_1\right]$ such that: $G_1\left(z_1\right)=M_1$ and $z_1\ne {\mu }_1$ . That yields that:

$z_1=x_0+{\left(\frac{M_1-m_1}{k}\right)}^{\beta }$

From the point $L_1\left(z_1,M_1\right)$ , we plot the representative curve of:

$O_1\left(x\right)=\min \left(M_1+k{\left|x-x_1\right|}^{\frac{1}{\beta }},M_1+k{\left|x-{\mu }_1\right|}^{\frac{1}{\beta }}\right)1_{J_1}(\; x\; )$

where $J_1=\left[\min \left(z_1,{\mu }_1\right),\max \left(z_1,{\mu }_1\right)\right]$ .

The new function:

${G^{\prime }}_1\left(x\right)=G_1\left(x\right)1_{x\notin J_1}+O_1(\; x\; )$

is also an overestimator.

The curve of ${G^{\prime }}_1$ has a new vertex, given by the curve of $O_1$ , denoted by:

$V^{″}\left(u_1,{H^{\prime }}_1\right)$ such that: $\{\begin{array}{l}{H^{\prime }}_1=M_1+k{\left|u_1-z_1\right|}^{\frac{1}{\beta }}\\ u_1=\frac{z_1+x_1}{2}\end{array}$ as indicated in Figure 3.

Hence, the vertex $V_1$ will be replaced by $V^{″}$ . The new vertex of the curve of ${G^{\prime }}_1$ , now denoted by $V_1$ , will be identified by $\left(u_1,L_1,R_1,H_1\right)$ with

$H_1=M_1+k{\left|u_1-z_1\right|}^{\frac{1}{\beta }}$ and where $L_1\left(z_1,M_1\right)$ and $R_1\left(x_1,M_1\right)$ are, respectively,

the left and the right neighbours of $V_1$ .

Let set $x_2=\arg \max \left({G^{\prime }}_1\left(x\right)\right)$ . Here, $x_2=u_1$ . Let:

・ $F_2\left(x\right)=f\left(x_2\right)+k{\left|x-x_2\right|}^{\frac{1}{\beta }}$

・ $G_2\left(x\right)=\min (F_2\left(x\right),{G^{\prime }}_1(\; x\; )\; )$

Suppose f evaluated at $x_0,x_1,\cdots ,x_n$ and denote by:

${\phi }_n=\max \left(f\left(x_0\right),f\left(x_1\right),\cdots ,f\left(x_n\right)\right)$

The curve of ${G^{\prime }}_n$ has n vertexes: $V_0\le V_1\le \cdots \le V_n$ such that each of them is identified by:

$\{\begin{array}{l}\text{itsleftneighbour}{L}_i\left(l_i,M_i\right)\\ \text{itsrightneighbour}{R}_i\left(r_i,M_i\right)\\ \text{itsabsciss}{u}_i=\frac{l_i+r_i}{2}\\ \text{itsordinate}{H}_i=M_i+k{\left|u_i-r_i\right|}^{\frac{1}{\beta }}\end{array}$ for i from 1 to n. (1)

Let’s $x_{n+1}=\arg \max \left({G^{\prime }}_n\left(x\right)\right)=u_n$ , $y_{n+1}=f\left(x_{n+1}\right)$ , ${\phi }_{n+1}=\max \left({\phi }_n,f\left(x_{n+1}\right)\right)$ and:

・ $F_{n+1}\left(x\right)=f\left(x_{n+1}\right)+k{\left|x-x_{n+1}\right|}^{\frac{1}{\beta }}$

・ $G_{n+1}\left(x\right)=\min ({G^{\prime }}_n\left(x\right),F_{n+1}(\; x\; )\; )$

For the curve of the overestimator $G_{n+1},V_n$ is anymore a summit, but two new vertexes appear from either side of $V_n$ : denoted by $V_L$ (in the left) and $V_R$ (in the right), as indicated in Figure 4. Set:

・ $M_{n+1}=\max \left(f\left(x_{n+1}\right),M_n\right)$

・ $m_{n+1}=\min \left(f\left(x_{n+1}\right),M_n\right)$

For the both vertexes $V_L$ and $V_R$ , it is not obvious to calculate their coordinates. Each of them will be replaced, respectively, by ${V^{\prime }}_L$ and ${V^{\prime }}_R$ as proceeded for $G_1$ .

Let’s determinate the coordinates of vertex ${V^{\prime }}_L$ .

Set ${\mu }_{n+1}^L=\arg \left(M_{n+1}\right)$ and ${\rho }_{n+1}^L=\arg \left(m_{n+1}\right)$ which belong to the set

$\left\{x_{n+1},l_n\right\}$ where $l_n$ is the absciss of the left neighbour $L_n$ of $V_n$ , as mentioned in (1).

Let’s set $z_L$ in $\left[x_{n+1},{\mu }_{n+1}^L\right]$ such that: $G_{n+1}\left(z_L\right)=M_{n+1}$ and $z_L\ne {\mu }_{n+1}^L$ .

This involves:

$z_L={\rho }_{n+1}^L+sign\left({\mu }_{n+1}^L-{\rho }_{n+1}^L\right){\left(\frac{M_{n+1}-m_{n+1}}{k}\right)}^{\frac{1}{\beta }}$

where $sign\left(x\right)=\{\begin{array}{l}+1,\text{if}x\ge 0\\ -1,\text{if}x<0\end{array}$ . Let:

$O_{n+1}^L\left(x\right)=\min \left(M_{n+1}+k{\left|x-z_L\right|}^{\frac{1}{\beta }},M_{n+1}+k{\left|x-{\mu }_{n+1}^L\right|}^{\frac{1}{\beta }}\right)1_{J_{n+1}^L}(\; x\; )$

where $J_{n+1}^L=\left[\min \left(z_L,{\mu }_{n+1}^L\right),\max \left(z_L,{\mu }_{n+1}^L\right)\right]$ .

The part of the curve of $G_{n+1}$ relative to the interval

$\left[\min \left(z_L,{\mu }_{n+1}^L\right),\max \left(z_L,{\mu }_{n+1}^L\right)\right]$ is replaced by the one of $O_{n+1}^L$ . That makes appear a new vertex ( ${V^{\prime }}_L$ ) replacing $V_L$ such that:

・ Its absciss is $u_L=\frac{1}{2}\left(z_L+{\mu }_{n+1}^L\right)$

・ Its ordinate is $H_L=M_{n+1}+k{\left|{\mu }_{n+1}^L-u_L\right|}^{\frac{1}{\beta }}$

Furthermore, ${V^{\prime }}_L$ will be identified by its neighbours:

・ The left neighbour $L\left(\min \left(z_L,{\mu }_{n+1}^L\right),M_{n+1}\right)$

・ The right neighbour $R\left(\max \left(z_L,{\mu }_{n+1}^L\right),M_{n+1}\right)$

Those values will be saved in memory.

Similarly, $V_R$ will be replaced by ${V^{\prime }}_R$ determined as follows:

Set ${\mu }_{n+1}^R=\arg \left(M_{n+1}\right)$ and ${\rho }_{n+1}^R=\arg \left(m_{n+1}\right)$ which belong to the set

$\left\{x_{n+1},r_n\right\}$ where $r_n$ is the absciss of the right neighbour of $V_n$ . Let:

ü $z_R={\rho }_{n+1}^R+sign\left({\mu }_{n+1}^R-{\rho }_{n+1}^R\right){\left(\frac{M_{n+1}-m_{n+1}}{k}\right)}^{\frac{1}{\beta }}$

ü $O_{n+1}^R\left(x\right)=\min \left(M_{n+1}+k{\left|x-z_R\right|}^{\frac{1}{\beta }},M_{n+1}+k{\left|x-{\mu }_{n+1}^R\right|}^{\frac{1}{\beta }}\right)1_{J_{n+1}^R}(\; x\; )$

where $J_{n+1}^R=\left[\min \left(z_R,{\mu }_{n+1}^R\right),\max \left(z_R,{\mu }_{n+1}^R\right)\right]$ .

The vertex ${V^{\prime }}_R$ that will replace $V_R$ has the following coordinates:

・ Its absciss is $u_R=\frac{1}{2}\left(z_R+{\mu }_{n+1}^R\right)$

・ Its ordinate is $H_R=M_{n+1}+k{\left|{\mu }_{n+1}^R-u_R\right|}^{\frac{1}{\beta }}$

${V^{\prime }}_R$ will also be identified by its neighbours:

・ The left neighbour $L\left(\min \left(z_R,{\mu }_{n+1}^R\right),M_{n+1}\right)$

・ The right neighbour $R\left(\max \left(z_R,{\mu }_{n+1}^R\right),M_{n+1}\right)$

Let’s set:

${G^{\prime }}_{n+1}\left(x\right)=G_{n+1}^L\left(x\right)+G_{n+1}^R\left(x\right)+G_{n+1}\left(x\right)1_{x\in J_{n+1}}(\; x\; )$

where $J_{n+1}=\left[\min \left(z_L,{\mu }_{n+1}^L\right),\max \left(z_R,{\mu }_{n+1}^R\right)\right]=J_{n+1}^L\cup J_{n+1}^R$ .

Furthermore, the vertex $V_n$ is eliminated and replaced by ${V^{\prime }}_R$ and ${V^{\prime }}_L$ . Hence, we have $n+1$ simmits that we organize in an increasing order, that yields:

$V_1\le V_2\le \cdots \le V_{n+1}$

2.3. Convergence Theorem

Theorem 1. Let $f$ a $\left(C,\frac{1}{\beta }\right)$ -holderian function defined on the interval

$\left[a,b\right]$ . The sequence ${\left(H_n\right)}_{n\in \mathbb{N}}$ , defined above, decreases to the maximum of $f$ .

Proof. Denote by $\phi ={\max }_{x\in \left[a,b\right]}f\left(x\right)$ and $\text{Φ}=\left\{x\in \left[a,b\right];f\left(x\right)=\phi \right\}$ ,

$\forall x\in \left[a,b\right],G_n\left(x\right)\ge f\left(x\right)$ for all $n\in \mathbb{N}$ . This involves that:

$H_n=\underset{x\in \left[a,b\right]}{\max }{G}_n\left(x\right)\ge \underset{x\in \left[a,b\right]}{\max }\left(x\right)=\phi$

As ${\phi }_{n+1}=\max \left(f\left(x_0\right),\cdots ,f\left(x_{n+1}\right)\right)$ and by the construction of $M_n$ , we deduce that:

$M_{n+1}\le {\phi }_{n+1}\le H_{n+1}$

Hence:

$\begin{array}{c}\left|H_{n+1}-{\phi }_{n+1}\right|\le \left|H_{n+1}-M_{n+1}\right|\le k{\left|x_{L_{n+1}}-x_{n+1}\right|}^{\frac{1}{\beta }}\le k{\left|\frac{1}{2}\left(x_{L_{n+1}}-x_{R_{n+1}}\right)\right|}^{\frac{1}{\beta }}\\ \le k{\left|\frac{1}{2^2}\left(x_{L_n}-x_{R_n}\right)\right|}^{\frac{1}{\beta }}\le k{\left|\frac{1}{2^n}\left(x_{L_1}-x_{R_1}\right)\right|}^{\frac{1}{\beta }}\end{array}$

which vanishes to 0.

As $\left({\phi }_n\right)$ is an increasing bounded sequence, it converges. Suppose that ${\phi }_n$ converges to $\mu \ne \phi$ . As $f\left(\left[a,b\right]\right)$ is a compact, $\mu \in f\left(\left[a,b\right]\right)$ . Let $y_n\in \left[a,b\right]$ such that ${\phi }_n=f\left(y_n\right)$ . As $\left[a,b\right]$ is a compact, the sequence $\left(y_n\right)$ admits a subsequence $\left(y_{n_k}\right)$ that converges to $z$ in $\left[a,b\right]$ . The continuity of $f$ involves that $f\left(z\right)=\mu$ .

Let $\epsilon =\phi -\mu$ . Since $\left(y_{n_k}\right)$ converges to $z$ , $\exists K,\forall k\ge K,\left|y_{n_k}-z\right|<{\left(\frac{\epsilon }{2C}\right)}^{\beta }$ . The property of Holder involves that: $\left|f\left(y_{n_k}\right)-f\left(z\right)\right|\le C{\left|y_{n_k}-z\right|}^{\frac{1}{\beta }}\le \frac{\epsilon }{2}$ . This

means that $\forall k\ge K$ :

${\phi }_{n_k}=f\left(y_{n_k}\right)\le f\left(z\right)+\frac{\epsilon }{2}=\mu +\frac{\epsilon }{2}.$

On the other hand, $\forall n\ge n_k$ :

$G_n\left(x\right)\le G_{n_k}\left(x\right)=f\left(y_{n_k}\right)+C{\left|x-y_{n_k}\right|}^{\frac{1}{\beta }}={\phi }_{n_k}+C{\left|x-y_{n_k}\right|}^{\frac{1}{\beta }}.$

Hence, $\forall x\in \left[a,b\right]$ and $\forall n\ge n_k$ such that $\left|x-y_{n_k}\right|<{\left(\frac{\epsilon }{2C}\right)}^{\beta }$ , we have:

$G_n\left(x\right)={\phi }_{n_k}+\frac{\epsilon }{2}\le \mu +\frac{\epsilon }{2}+\frac{\epsilon }{2}=\phi$

The real $z\in \left]y_{n_k}-{\left(\frac{\epsilon }{2C}\right)}^{\beta },y_{n_k}+{\left(\frac{\epsilon }{2C}\right)}^{\beta }\right[$ , then $\exists j>K$ such that:

$\left|y_{n_j}-y_{n_K}\right|<{\left(\frac{\epsilon }{2C}\right)}^{\beta }$ .

This means that $H_{n_j}=G_{n_j}\left(y_{n_j}\right)<\phi$ . This is absurd. Then $\left(y_{n_k}\right)$ converges to $\phi$ .

2.4. Description of the Algorithm

2.4.1. Initialization

$x_0=a,x_1=b,n=1$ .

・ $M_1=\max \left(f\left(x_0\right),f\left(x_1\right)\right)$

・ $m_1=\min \left(f\left(x_0\right),f\left(x_1\right)\right)$

・ ${\mu }_1=\arg \max \left(f\left(x_0\right),f\left(x_1\right)\right)$

・ $V_1\left(u_1=\frac{z_1+x_1}{2},H_1=M_1+k{\left|u_1-z_1\right|}^{\frac{1}{\beta }}\right)$

$L_1\left(z_1,M_1\right)$ and $R_1\left(x_1,M_1\right)$

2.4.2. Iterative Steps

・ ${\phi }_n=\max \left(f\left(x_0\right),f\left(x_1\right),\cdots ,f\left(x_n\right)\right)$

・ $x_{n+1}=u_n$

・ $M_{n+1}=\max \left(f\left(x_{n+1}\right),M_n\right)$

・ $m_{n+1}=\min \left(f\left(x_{n+1}\right),M_n\right)$

・ ${V^{\prime }}_L\{\begin{array}{l}{u}_L=\frac{1}{2}\left(z_L+{\mu }_{n+1}^L\right)\\ H_L=M_{n+1}+k\left|{\mu }_{n+1}^L-u_L\right|\\ L\left(\min \left(z_L,{\mu }_{n+1}^L\right),M_{n+1}\right)\\ R\left(\max \left(z_L,{\mu }_{n+1}^L\right),M_{n+1}\right)\end{array}$

・ ${V^{\prime }}_R\{\begin{array}{l}{u}_R=\frac{1}{2}\left(z_R+{\mu }_{n+1}^R\right)\\ H_R=M_{n+1}+k\left|{\mu }_{n+1}^R-u_R\right|\\ L\left(\min \left(z_R,{\mu }_{n+1}^R\right),M_{n+1}\right)\\ R\left(\max \left(z_R,{\mu }_{n+1}^R\right),M_{n+1}\right)\end{array}$

Organize in an increasing order $V_1,V_2,\cdots ,V_{n-1},{V^{\prime }}_L,{V^{\prime }}_R$ : $V_1\le V_2\le \cdots \le V_n\le V_{n+1}$ .

2.4.3. Stopping Criterion

If $\left|H_{n+1}-{\phi }_{n+1}\right|\le {\epsilon }_0$ , then stop, else, $n=n+1$ and back to iterative steps.

3. α-Dense Curves

The principal tool that enables one to apply the algorithm above for a multivariate function is the α-dense curves [15] [16] [17] .

3.1. The α-Dense Curves

Definition 3. Let $X$ be a non empty set and $S$ a subset of $X$ . $S$ is said to be α-dense in $X$ , if:

$\forall M\in X,\exists M^{\prime }\in S:d\left(M,M^{\prime }\right)\le \alpha$

Among the α-dense curves, we have chosen the Lissajous curves.

3.2. Lissajous Curve

In mathematics, a Lissajous curve, also known as Lissajous figure or Bowditch curve, is the graph of a system of parametric equations which describe complex harmonic motion.

3.2.1. Bidimensional Case

In the bidimensional case, a Lissajous figure can be defined by the following parametric equations:

$\{\begin{array}{l}x\left(t\right)=a\sin \left(t\right)\\ y\left(t\right)=b\sin \left(nt+\varphi \right)\end{array}$ where $0\le \varphi \le \frac{\text{π}}{2}$ and $n\ge 1$ .

The number $n$ is named the parameter of the curve. If $n$ is rational, it can

be expressed in the form $n=\frac{p}{q}$ . Hence, the parametric equation describing the

curve becomes:

$\{\begin{array}{l}x\left(t\right)=a\sin \left(pt\right)\\ y\left(t\right)=b\sin \left(qt+\varphi \right)\\ 0\le t\le 2\text{π}\end{array}$ where: $0\le \varphi \le \frac{\text{π}}{2p}$

In what follows, we set $\varphi =0$ and let consider the following function $\Gamma$ defined by:

$\begin{array}{l}\Gamma :\left[0,2\text{π}\right]\to \left[0,2\text{π}\right]\times \left[0,2\text{π}\right]\\ t\mapsto \Gamma \left(t\right)=\left({\Gamma }_1\left(t\right),{\Gamma }_2\left(t\right)\right)\end{array}$ (2)

where $\{\begin{array}{l}{\Gamma }_1\left(t\right)=\text{π}\sin \left(pt\right)+\text{π}\\ {\Gamma }_2\left(t\right)=\text{π}\sin \left(qt\right)+\text{π}\end{array}$ such that: p is an even number and $q=p+1$ , of which the representative curve is given by Figure 5;

Theorem 2. If $\alpha =\text{π}\sin \left(\frac{\text{π}}{p}\right)$ , the Lissajous curve $\Gamma$ , given by (2), is α-dense

in ${\left[0,2\text{π}\right]}^2$ .

Proof. Let $M_0\left(x,y\right)$ any point in ${\left[0,2\text{π}\right]}^2$ . Let show that there exists $t\in \left[0,2\text{π}\right]$ such that:

$d\left(M_0,\Gamma \left(t\right)\right)\le \text{π}\sin (\; \pi \; p\; )$

We Set: $\{\begin{array}{l}{\Gamma }_1\left(t\right)=\text{π}\sin \left(pt\right)+\text{π}\\ {\Gamma }_2\left(t\right)=\text{π}\sin \left(qt\right)+\text{π}\end{array}$ .

$p$ is an even number and $q=p+1$ .

Let’s set t in $\left[0,2\text{π}\right]$ . Notice that the function ${\Gamma }_1$ is $\frac{\text{2π}}{p}$ periodic. Let

$t^{\prime }=t+\frac{\text{2π}}{p}$ .

Consider the points $M\left({\text{Γ}}_1\left(t\right),{\text{Γ}}_2\left(t\right)\right)$ and $M^{\prime }\left({\Gamma }_1\left(t^{\prime }\right),{\Gamma }_2\left(t^{\prime }\right)\right)$ . The points $M$ and $M^{\prime }$ have the same abscissa.

$\begin{array}{c}d{\left(M,M^{\prime }\right)}^2={\left({\Gamma }_2\left(t^{\prime }\right)-{\Gamma }_2\left(t\right)\right)}^2={\text{π}}^2{\left(\sin \left(q{t}^{\prime }\right)-\sin \left(qt\right)\right)}^2\\ =4{\text{π}}^2{\sin }^2\left(\frac{q}{2}\left(t^{\prime }-t\right)\right){\cos }^2\left(\frac{q}{2}\left(t+t^{\prime }\right)\right)\\ =4{\text{π}}^2{\sin }^2\left(q\frac{\text{π}}{p}\right){\cos }^2\left(qt+q\frac{\text{π}}{p}\right)\\ =4{\text{π}}^2{\sin }^2\left(\frac{\text{π}}{p}\right){\cos }^2\left(qt+\frac{\text{π}}{p}\right)\end{array}$

This distance reaches its maximum value when ${\cos }^2\left(qt+\frac{\text{π}}{p}\right)=1$ , for

$t=\frac{1}{q}\left(k\text{π}+\frac{\text{π}}{p}\right)$ where $k\in \left\{1,2,\cdots ,2q\right\}$ .

Hence, $d\left(M,M^{\prime }\right)\le 2\text{π}\sin \left(\frac{\text{π}}{p}\right)$ .

As ${\Gamma }_1$ is surjective from $\left[0,\frac{\text{2π}}{p}\right]$ on $\left[0,2\text{π}\right]$ , there exists $t_1\in \left[0,\frac{2\text{π}}{p}\right]$ such

that $x={\Gamma }_1\left(t_1\right)$ .

As ${\text{Γ}}_2$ is surjective from $\left[0,\frac{\text{2π}}{p}\right]$ on $\left[0,2\text{π}\right]$ , there exists $t_2\in \left[0,\frac{2\text{π}}{p}\right]$ such

that $y={\Gamma }_2\left(t_2\right)$ .

There exists $k\in \left\{0,1,\cdots ,p-1\right\}$ such that: either

${\Gamma }_2\left(t_1+\frac{2k\text{π}}{p}\right)\le {\Gamma }_2\left(t_2\right)\le {\Gamma }_2\left(t_1+\frac{2\left(k+1\right)\text{π}}{p}\right)$

or

${\Gamma }_2\left(t_1+\frac{2k\text{π}}{p}\right)\ge {\Gamma }_2\left(t_2\right)\ge {\Gamma }_2\left(t_1+\frac{2\left(k+1\right)\text{π}}{p}\right)$

This does not occur only when $y=0$ or $y=2\text{π}$ , that means that when the point $M$ in on the boundary.

This yields that $M_0$ is in the segment:

$\left[M_k\left(\Gamma \left(t_1+\frac{2k\text{π}}{p}\right)\right),M_{k+1}\left(\Gamma \left(t_1+\frac{2\left(k+1\right)\text{π}}{p}\right)\right)\right]$ .

So that, any point $M_0$ can be framed between two points of type $M_k$ and $M_{k+1}$ .

Hence, we can approximate any point of ${\left[0,2\text{π}\right]}^2$ by a point of the Lissajous curve.

When trying to α-densify ${\left[0,2\text{π}\right]}^2$ using the parametric curve $\Gamma \left(t\right)$ , we choose the coefficient $p$ such that:

$\alpha =\text{π}\sin \left(\frac{\text{π}}{p}\right)$ .

Generally, let $a>0$ and set a curve $h$ that parametric equation is:

$\begin{array}{l}h:\left[0,2\text{π}\right]\to \left[-a,a\right]\times \left[-a,a\right]\\ t\mapsto \{\begin{array}{l}{h}_1\left(t\right)=\frac{a}{\text{π}}{\Gamma }_1\left(t\right)-a=a\sin \left(pt\right)\\ h_2\left(t\right)=\frac{a}{\text{π}}{\Gamma }_2\left(t\right)-a=a\sin (\; q\; t\; )\end{array}\end{array}$

Corollary 1. For $\alpha =a\sin \left(\frac{\text{π}}{p}\right)$ , any point in ${\left[-a,a\right]}^2$ can be approximated,

with a precision $\alpha$ , by at least one point of $h$ .

$\forall M\in {\left[-a,a\right]}^2$ , there exists $t\in \left[0,2\text{π}\right]$ such that $d\left(M,h\left(t\right)\right)\le \alpha$ .

3.2.2. Multidimensional Case

ü In dimension two, we defined the Lissajous curve by:

$\begin{array}{l}\text{Γ}:\left[0,2\text{π}\right]\to \left[0,2\text{π}\right]\times \left[0,2\text{π}\right]\\ t\mapsto \{\begin{array}{l}{\Gamma }_1\left(t\right)=\text{π}\sin \left(pt\right)+\text{π}\\ {\Gamma }_2\left(t\right)=\text{π}\sin \left(qt\right)+\text{π}\end{array}\end{array}$

with: $p$ a given even number and $q=p+1$ .

ü In dimension three, let’s consider $\left(x_1,x_2,x_3\right)\in {\left[0,2\text{π}\right]}^3$ , We first link $x_1$ and $x_2$ as done in the bidimensional case: that means:

$x_1={\Gamma }_1\left(t^{*}\right)$ and $x_2={\Gamma }_2(\; t\; *\; )$

with $t^{*}$ in $\left[0,2\text{π}\right]$ , then we link $t^{*}$ and $x_3$ , similarly, by setting:

$t^{*}={\Gamma }_1\left(t\right)$ and $x_3={\Gamma }_2(\; t\; )$

with $t$ in $\left[0,2\text{π}\right]$ . This involves:

$\{\begin{array}{l}{x}_1={\Gamma }_1\left(t^{*}\right)={\Gamma }_1\left({\Gamma }_1\left(t\right)\right)\\ x_2={\Gamma }_2\left(t^{*}\right)={\Gamma }_2\left({\Gamma }_1\left(t\right)\right)\\ x_3={\Gamma }_2(\; t\; )\end{array}$

Hence, we obtain parametric curve $H\left(t\right)=\left(H_1\left(t\right),H_2\left(t\right),H_3\left(t\right)\right)$ defined by the following expression:

$\{\begin{array}{l}{H}_1\left(t\right)={\Gamma }_1\circ {\Gamma }_1\left(t\right)\\ H_2\left(t\right)={\Gamma }_2\circ {\Gamma }_1\left(t\right)\\ H_3\left(t\right)={\Gamma }_2(\; t\; )\end{array}$

with $t\in \left[0,2\text{π}\right]$ .

ü We can generalize this process to n variables $\left(x_1,x_2,\cdots ,x_n\right)$ by linking two by two by the same manner. At the end of the process, we get the new variable t belonging to $\left[0,2\text{π}\right]$ that all variables will be expressed by:

$x_i=H_i\left(t\right),i=1,\cdots ,n$

where $H_i\left(t\right)$ are defined as follows:

$\{\begin{array}{l}{H}_1\left(t\right)={\Gamma }_1^{n-1}\left(t\right)=\underset{n-1\text{times}}{\underbrace{{\Gamma }_1\circ {\Gamma }_1\circ \cdots \circ {\Gamma }_1}}\left(t\right)\\ H_i\left(t\right)={\Gamma }_2\circ {\Gamma }_1^{n-i}\left(t\right)\forall i=2,\cdots ,n\end{array}$

Then, let’s consider the parametric curve $H$ defined by:

$\begin{array}{l}H:\left[0,2\text{π}\right]\to {\left[0,2\text{π}\right]}^n\\ t\mapsto (H_1\left(t\right),H_2\left(t\right),\cdots ,H_n(\; t\; )\; )\end{array}$

Theorem 3. Let $\alpha =\text{π}\sin \left(\frac{\text{π}}{p}\right)$ .

The parametric curve defined by $H\left(t\right)=\left(H_1\left(t\right),H_2\left(t\right),\cdots ,H_n\left(t\right)\right)$ such that:

$\{\begin{array}{l}{H}_1\left(t\right)={\Gamma }_1^{n-1}\left(t\right)\\ H_i\left(t\right)={\Gamma }_2\circ {\Gamma }_1^{n-i}\left(t\right)\forall i=2,\cdots ,n\end{array}$

for $t\in \left[0,2\text{π}\right]$ is α-dense on ${\left[0,2\text{π}\right]}^n$ .

Proof. Let $H\left(t\right)$ and $H\left(t+\frac{2\text{π}}{p}\right)$ two points of the curve $H$ . As the function ${\Gamma }_1$ is $\frac{2\text{π}}{p}$ periodic, the $\left(n-1\right)$ first coordinates of these two points are

equal. As proceeded in the second part of the proof of the previous theorem, we show that:

$d\left(H\left(t\right),H\left(t+\frac{2\text{π}}{p}\right)\right)\le 2\text{π}\sin (\; \pi \; p\; )$

Therefore, any point $M_0\left(x_1,x_2,\cdots ,x_n\right)$ can be framed between two points of the curve of type:

$H\left(t+\frac{2k\text{π}}{p}\right)$ and $H\left(t+\frac{2\left(k+1\right)\text{π}}{p}\right)$ where $t\in \left[0,2\text{π}\right]$ .

Generally, let $a>0$ and set a curve $h$ that parametric equation is:

$\begin{array}{l}h:\left[0,2\text{π}\right]\to {\left[-a,a\right]}^n\\ t\mapsto (h_1\left(t\right),h_2\left(t\right),\cdots ,h_n(\; t\; )\; )\end{array}$

$\{\begin{array}{l}{h}_1\left(t\right)=\frac{a}{\text{π}}{\Gamma }_1^{n-1}\left(t\right)-a\\ h_j\left(t\right)=\frac{a}{\text{π}}{\Gamma }_2\circ {\Gamma }_1^{n-j}\left(t\right)-a\text{for}j=2,\cdots ,n\end{array}$

Corollary 2. For $\alpha =a\sin \left(\frac{\text{π}}{p}\right)$ , any point in ${\left[-a,a\right]}^n$ can be approximated,

with a precision α, by at least one point of the parametric curve given by $h$ .

$\forall M\in {\left[-a,a\right]}^n$ , there exists $t\in \left[0,2\text{π}\right]$ such that $d\left(M,h\left(t\right)\right)\le \alpha$ .

4. Optimization of a Multivariate Holderian Function

Let $f$ be a multivariate holderian function with constants of Holder are: $k>0$ and $\beta >1$ .

Let us consider the following multidimensional optimization problem:

$\left(P_n\right)\underset{x\in {\left[-a,a\right]}^n}{\text{Min}}f(\; x\; )$

In fact, we don’t look for the exact value of the minimum value of $f$ , we’d just want an approximating value of that minimum value with a given accuracy $\epsilon$ .

By means of an α-dense Lissajous curve on ${\left[-a,a\right]}^n$ , we convert the initial multidimensional problem $\left(P_n\right)$ into an unidimensional one as follows:

$\left(P_1\right)\underset{t\in \left[0,2\text{π}\right]}{\text{Min}}{f}^{*}(\; t\; )$

where: $f^{*}=f\circ h$ , the single variable function approximating the multivariate function $f$ . (where $\left(h_1,h_2,\cdots ,h_n\right)$ defined above)

Proposition 2. If $f$ is $\left(k,\frac{1}{\beta }\right)$ -holderian and $h_{i=1,n}$ is $\left({k^{\prime }}_i,\frac{1}{{\beta }^{\prime }}\right)$ -holderian, then $f^{*}=f\circ h$ is holderian where the constant is “ $k{\left({\displaystyle {\sum }_{i=1}^n{k^{\prime }}_i^2}\right)}^{\frac{1}{2\beta }}$ ” and the exponent is “ $\frac{1}{\beta {\beta }^{\prime }}$ ”.

Proof. $\begin{array}{c}\left|f^{*}\left(x\right)-f^{*}\left(y\right)\right|=\left|f\circ h\left(x\right)-f\circ h\left(y\right)\right|=\left|f\left(h\left(x\right)\right)-f\left(h\left(y\right)\right)\right|\\ \le k{\Vert h\left(x\right)-h\left(y\right)\Vert }^{\frac{1}{\beta }}\le k{\left({\displaystyle \sum }_{i=1}^n\sqrt{{\left(h_i\left(x\right)-h_i\left(y\right)\right)}^2}\right)}^{\frac{1}{\beta }}\\ \le k{\left({\displaystyle \sum }_{i=1}^n\sqrt{{\left({k^{\prime }}_i{\left|x-y\right|}^{\frac{1}{{\beta }^{\prime }}}\right)}^2}\right)}^{\frac{1}{\beta }}\le k{\left({\displaystyle \sum }_{i=1}^n\sqrt{{k^{\prime }}_i^2}{\left|x-y\right|}^{\frac{1}{{\beta }^{\prime }}}\right)}^{\frac{1}{\beta }}\\ \le k{\left({\displaystyle \sum }_{i=1}^n{k^{\prime }}_i^2\right)}^{\frac{1}{2\beta }}{\left|x-y\right|}^{\frac{1}{\beta {\beta }^{\prime }}},t\in \left[0,2\text{π}\right]\end{array}$

Let $x_{opt}=\arg \min \left(f\right)$ and $t_{opt}=\arg \min \left(f^{*}\right)$ .

Theorem 4. If $\alpha ={\left(\frac{\epsilon }{k}\right)}^{\beta }$ then $\left|f\left(x_{opt}\right)-f^{*}\left(t_{opt}\right)\right|\le \epsilon$ .

Remark 1. The knowledge of the minimum of $f^{*}$ allows us to surround the minimum value of $f$ in the interval $\left[f^{*}\left(t_{opt}\right)-\epsilon ,f^{*}\left(t_{opt}\right)+\epsilon \right]$ .

Proof. We set: $x_{opt}=\arg {\min }_{x\in {\left[-a,a\right]}^n}f(\; x\; )$

As $x_{opt}\in {\left[-a,a\right]}^n$ , the α-density guarantees the existence of $t^{*}\in \left[0,2\text{π}\right]$ such that $\left|x_{opt}-h\left(t^{*}\right)\right|\le \alpha$

$\begin{array}{c}\left|f\left(x_{opt}\right)-f^{*}\left(t^{*}\right)\right|=\left|f\left(x_{opt}\right)-f\left(h\left(t^{*}\right)\right)\right|\\ \le k{\Vert x_{opt}-h\left(t^{*}\right)\Vert }^{\frac{1}{\beta }}\le k{\alpha }^{\frac{1}{\beta }}=\epsilon \end{array}$

Hence, if we want to estimate the optimum with an accuracy $\epsilon$ , we just have

to take $\alpha ={\left(\frac{\epsilon }{k}\right)}^{\beta }$ .

Suppose that there exists $x_0\in {\left[-a,a\right]}^n$ such that:

$f\left(x_0\right)<f^{*}\left(t_{opt}\right)-\epsilon$

So that:

$f\left(x_0\right)+\epsilon <f^{*}\left(t_{opt}\right)$ (*)

The α-density involves that there exists $t_0\in \left[0,2\text{π}\right]$ such that $\Vert x_0-h\left(t_0\right)\Vert <\alpha$

$\left|f\left(x_0\right)-f\left(h\left(t_0\right)\right)\right|\le k{\Vert x_0-h\left(t_0\right)\Vert }^{\frac{1}{\beta }}\le \epsilon$

$f\left(x_0\right)-\epsilon \le f\left(h\left(t_0\right)\right)\le f\left(x_0\right)+\epsilon$

Considering (*) involves:

$f^{*}\left(t_0\right)=f\left(h\left(t_0\right)\right)\le f\left(x_0\right)+\epsilon <f^{*}\left(t_{opt}\right)$

This is absurd.

5. Numerical Tests (Figures 6-9)

1) $f_1\left(x\right)=\sqrt{1-x^2},x\in \left[-0.25,0.5\right]$

The holderian constants are $=\sqrt{2}$ , $\beta =2$ . The accuracy is: $\epsilon ={10}^{-5}$ .

The result is:

$\{\begin{array}{l}\Rrightarrow x^{\text{*}}=0.5\\ \Rrightarrow f_1\left(x^{\text{*}}\right)=0.866\\ f_1{}_{opt}\in \left[f_1\left(x^{\text{*}}\right)-\epsilon ,f_1\left(x^{\text{*}}\right)\right]\end{array}$

2) $f_2\left(x\right)={\displaystyle {\sum }_{k=1}^{5}k\left|\sin \left(\left(3k+1\right)x+k\right)\right|{\left|x-k\right|}^{\frac{1}{5}}},x\in \left[0,10\right]$

$k=77,\beta =5,\epsilon =0.003$

$\{\begin{array}{l}\Rrightarrow x^{\text{*}}=2.829917922\\ \Rrightarrow x^{\text{*}}=2.829917922\end{array}$

3) $f_3\left(x,y\right)={\left|x+y-0.25\right|}^{\frac{2}{3}}-3\cos \left(\frac{x}{2}\right),\left(x,y\right)\in {\left[-\frac{1}{2},\frac{1}{2}\right]}^2$

$k=2.42,\beta =\frac{3}{2},\epsilon =0.01$

$\{\begin{array}{l}\Rrightarrow x^{\text{*}}=\left(-0.004,0.253\right)\\ \Rrightarrow f_3\left(x^{\text{*}}\right)=-2.99\\ f_3{}_{opt}\in \left[f_3\left(x^{\text{*}}\right)-\epsilon ,f_3\left(x^{\text{*}}\right)\right]\end{array}$

4) $f_4\left(x,y\right)={\displaystyle {\sum }_{k=1}^3\frac{1}{k}\left|\cos \left(\left(\frac{3}{k}+1\right)\left(x+5\right)+\frac{1}{k}\right)\right|{\left|x-y\right|}^{\frac{1}{3}}},\left(x,y\right)\in {\left[-5,5\right]}^2$

$k=14.77,\beta =3,\epsilon =0.1$

$\{\begin{array}{l}\Rrightarrow x^{\text{*}}=\left(-4.499796,-4.500100\right)\\ \Rrightarrow f_4\left(x^{\text{*}}\right)=0.067788\end{array}$

5) $f_5\left(x,y\right)=-\cos x\cos y\exp \left(1-\frac{\sqrt{x^2+y^2}}{\text{π}}\right),\left(x,y\right)\in {\left[-6,6\right]}^2$

$k=45.265,\beta =\frac{1}{2},\epsilon =0.03$

$\{\begin{array}{l}\Rrightarrow x^{\text{*}}=\left(0.023391875,-0.01321677\right)\\ \Rrightarrow f_5\left(x^{\text{*}}\right)=-2.694161027\end{array}$

6) $f_6\left(x_1,x_2,x_3\right)=\frac{1}{2}{\displaystyle {\sum }_{i=1}^3\left(x_i{}^4-16x_i{}^2+5x_i\right)},\left(x_1,x_2,x_3\right)\in {\left[-5,5\right]}^3$

$k=180,\beta =7,\epsilon =0.02$

$\{\begin{array}{l}\Rrightarrow x^{\text{*}}=\left(-2.899891,-3.000102,-2.923504\right)\\ \Rrightarrow f_6\left(x^{\text{*}}\right)=-117.3248028\end{array}$

7) Let the following functions test. In [10] , RPS method was used to optimize them.

$\{\begin{array}{l}\circ f_1\left(x_1,x_2\right)=-4\left|\sin \left(x_1\right)\cos \left(x_2\right)\exp \left(\left|\cos \left(\frac{x_1^2+x_2^2}{200}\right)\right|\right)\right|,\left(x_1,x_2\right)\in {\left[-10,10\right]}^2\\ \circ f_2\left(x_1,x_2\right)=-\left|\cos \left(x_1\right)\cos \left(x_2\right)\exp \left(\left|1-\left(\frac{\sqrt{x_1^2+x_2^2}}{\text{π}}\right)\right|\right)\right|,\left(x_1,x_2\right)\in {\left[-10,10\right]}^2\\ \circ f_3\left(x_1,x_2\right)=-\exp \left(-{\left|\cos \left(x_1\right)\cos \left(x_2\right)\exp \left(\left|1-\left(\frac{\sqrt{x_1^2+x_2^2}}{\text{π}}\right)\right|\right)\right|}^{-1}\right),\left(x_1,x_2\right)\in {\left[-11,11\right]}^2\end{array}$

In what follows, we compare our method with the RPS one (The Particle Swarm Method of Global Optimization)

Cite this paper

Yahyaoui, A. and Ammar, H. (2017) Global Optimization of Multivariate Holderian Functions Using Overestimators. Open Access Library Jour- nal, 4: e3511. https://doi.org/10.4236/oalib.1103511

References