Open Access Library Journal
Vol.04 No.05(2017), Article ID:76017,18 pages
10.4236/oalib.1103511
Global Optimization of Multivariate Holderian Functions Using Overestimators
Amine Yahyaoui1, Hamadi Ammar2
1Faculty of Sciences of Bizerte, Carthage University, Tunis, Tunisia
2Faculty of Economics and Management of Nabeul, Carthage University, Tunis, Tunisia
Copyright © 2017 by authors and Open Access Library Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: March 9, 2017; Accepted: May 2, 2017; Published: May 5, 2017
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
.
Let’s denote by (P) the following unidimensional optimization problem:
(P)
In fact, we will not search the exact solution 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 such that where , 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 , if there exists and such that and :
.
Definition 2. A function F is said to be an overestimator of a function f on a set X if:
.
Proposition 1. Let f be a holderian univariate function defined on the interval and let . The function H defined on by:
.
is an overestimator of f on .
Proof. Let’s set , As f is holderian:
.
This yields: .
Hence, .
2.2. Sequence of Overestimators
Let the left bound of [a, b] and let’s set:
an overestimator of f whose representative curve is given by Figure 1.
The curve has one vertex such that:
Let’s set . Here, . From the point that coordinates are , we plot the curve of the overestimator:
as shown in Figure 2. We set:
Figure 1. Curve of F0.
Figure 2. Curve of G1.
and .
The vertex is anymore a vertex of the curve of . It’s replaced by a new vertex , given by the intersection of the curves of and .
The real is solution of the following equation:
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 that allows to give a value nearby to that we also denote by .
The point is between two neighbouring points belonging to the curve of : one on its left and one in its right . We denote by:
・
・
・
・
According to the Figure 2, and in this case, and . Let’s set in such that: and . That yields that:
From the point , we plot the representative curve of:
where .
The new function:
is also an overestimator.
The curve of has a new vertex, given by the curve of , denoted by:
such that: as indicated in Figure 3.
Hence, the vertex will be replaced by . The new vertex of the curve of , now denoted by , will be identified by with
and where and are, respectively,
the left and the right neighbours of .
Let set . Here, . Let:
・
・
Suppose f evaluated at and denote by:
The curve of has n vertexes: such that each of them is identified by:
for i from 1 to n. (1)
Let’s , , and:
・
・
For the curve of the overestimator is anymore a summit, but two new vertexes appear from either side of : denoted by (in the left) and (in the right), as indicated in Figure 4. Set:
Figure 3. Curve of .
Figure 4. Curve of Gn+1.
・
・
For the both vertexes and , it is not obvious to calculate their coordinates. Each of them will be replaced, respectively, by and as proceeded for .
Let’s determinate the coordinates of vertex .
Set and which belong to the set
where is the absciss of the left neighbour of , as mentioned in (1).
Let’s set in such that: and .
This involves:
where . Let:
where .
The part of the curve of relative to the interval
is replaced by the one of . That makes appear a new vertex ( ) replacing such that:
・ Its absciss is
・ Its ordinate is
Furthermore, will be identified by its neighbours:
・ The left neighbour
・ The right neighbour
Those values will be saved in memory.
Similarly, will be replaced by determined as follows:
Set and which belong to the set
where is the absciss of the right neighbour of . Let:
ü
ü
where .
The vertex that will replace has the following coordinates:
・ Its absciss is
・ Its ordinate is
will also be identified by its neighbours:
・ The left neighbour
・ The right neighbour
Let’s set:
where .
Furthermore, the vertex is eliminated and replaced by and . Hence, we have simmits that we organize in an increasing order, that yields:
2.3. Convergence Theorem
Theorem 1. Let a -holderian function defined on the interval
. The sequence , defined above, decreases to the maximum of .
Proof. Denote by and ,
for all . This involves that:
As and by the construction of , we deduce that:
Hence:
which vanishes to 0.
As is an increasing bounded sequence, it converges. Suppose that converges to . As is a compact, . Let such that . As is a compact, the sequence admits a subsequence that converges to in . The continuity of involves that .
Let . Since converges to , . The property of Holder involves that: . This
means that :
On the other hand, :
Hence, and such that , we have:
The real , then such that:
.
This means that . This is absurd. Then converges to .
2.4. Description of the Algorithm
2.4.1. Initialization
.
・
・
・
・
and
2.4.2. Iterative Steps
・
・
・
・
・
・
Organize in an increasing order : .
2.4.3. Stopping Criterion
If , then stop, else, 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 be a non empty set and a subset of . is said to be α-dense in , if:
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:
where and .
The number is named the parameter of the curve. If is rational, it can
be expressed in the form . Hence, the parametric equation describing the
curve becomes:
where:
In what follows, we set and let consider the following function defined by:
(2)
where such that: p is an even number and , of which the representative curve is given by Figure 5;
Theorem 2. If , the Lissajous curve , given by (2), is α-dense
in .
Proof. Let any point in . Let show that there exists such that:
We Set: .
is an even number and .
Let’s set t in . Notice that the function is periodic. Let
.
Consider the points and . The points and have the same abscissa.
Figure 5. Lissajous curve in the bidimensional case.
This distance reaches its maximum value when , for
where .
Hence, .
As is surjective from on , there exists such
that .
As is surjective from on , there exists such
that .
There exists such that: either
or
This does not occur only when or , that means that when the point in on the boundary.
This yields that is in the segment:
.
So that, any point can be framed between two points of type and .
Hence, we can approximate any point of by a point of the Lissajous curve.
When trying to α-densify using the parametric curve , we choose the coefficient such that:
.
Generally, let and set a curve that parametric equation is:
Corollary 1. For , any point in can be approximated,
with a precision , by at least one point of .
, there exists such that .
3.2.2. Multidimensional Case
ü In dimension two, we defined the Lissajous curve by:
with: a given even number and .
ü In dimension three, let’s consider , We first link and as done in the bidimensional case: that means:
and
with in , then we link and , similarly, by setting:
and
with in . This involves:
Hence, we obtain parametric curve defined by the following expression:
with .
ü We can generalize this process to n variables by linking two by two by the same manner. At the end of the process, we get the new variable t belonging to that all variables will be expressed by:
where are defined as follows:
Then, let’s consider the parametric curve defined by:
Theorem 3. Let .
The parametric curve defined by such that:
for is α-dense on .
Proof. Let and two points of the curve . As the function is periodic, the first coordinates of these two points are
equal. As proceeded in the second part of the proof of the previous theorem, we show that:
Therefore, any point can be framed between two points of the curve of type:
and where .
Generally, let and set a curve that parametric equation is:
Corollary 2. For , any point in can be approximated,
with a precision α, by at least one point of the parametric curve given by .
, there exists such that .
4. Optimization of a Multivariate Holderian Function
Let be a multivariate holderian function with constants of Holder are: and .
Let us consider the following multidimensional optimization problem:
In fact, we don’t look for the exact value of the minimum value of , we’d just want an approximating value of that minimum value with a given accuracy .
By means of an α-dense Lissajous curve on , we convert the initial multidimensional problem into an unidimensional one as follows:
where: , the single variable function approximating the multivariate function . (where defined above)
Proposition 2. If is -holderian and is -holderian, then is holderian where the constant is “ ” and the exponent is “ ”.
Proof.
Let and .
Theorem 4. If then .
Remark 1. The knowledge of the minimum of allows us to surround the minimum value of in the interval .
Proof. We set:
As , the α-density guarantees the existence of such that
Hence, if we want to estimate the optimum with an accuracy , we just have
to take .
Suppose that there exists such that:
So that:
(*)
The α-density involves that there exists such that
Considering (*) involves:
This is absurd.
5. Numerical Tests (Figures 6-9)
1)
The holderian constants are , . The accuracy is: .
The result is:
2)
Figure 6. Curve of f2.
Figure 7. Curve of f5.
Figure 8. Curve of .
Figure 9. Curve of f1, f2 and fa.
3)
4)
5)
6)
7) Let the following functions test. In [10] , RPS method was used to optimize them.
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
- 1. Ammar, H., Abbaoui, K. and Ndour, M. (1996) An Example of an Interaction Model between Two Species. Kybernetes, 25, 106-118.
- 2. Miguel, R.L. and Sahinidis, N.V. (2013) Derivative-Free Optimization: A Review of Algorithms and Comparison of Software Implementations. Journal of Global Optimization, 56, 1247-1293.
https://doi.org/10.1007/s10898-012-9951-y - 3. Lavigne, D. and Cherruault, Y. (1991) Alienor-Gabriel Global Optimization of a Function of Several Variables. Mathematical and Computer Modelling, 15, 125-134.
https://doi.org/10.1016/0895-7177(91)90097-Q - 4. Mora, G., Cherruault, Y. and Ziadi, A. (2001) Global Optimization. A New Variant of the Alienor Method. Computers and Mathematics with Applications, 41, 63-71.
https://doi.org/10.1016/S0898-1221(01)85006-9 - 5. Shubert, B.O. (1972) A Sequential Method Seeking the Global Maximum of a Function. SIAM Journal on Numerical Analysis, 9, 379-388.
https://doi.org/10.1137/0709036 - 6. Ammar, H. and Cherruault, Y. (1993) Approximation of Several Variables Function by a One Variable Function and Application to Global Optimization. Mathematical and Computer Modelling, 18, 17-21.
https://doi.org/10.1016/0895-7177(93)90003-H - 7. Ammar, H. and Cherruault, Y. (1995) Implementation of Alienor Technique in the Multidimensional Bissection Method. Application to Global Optimization. A New Accelerated Algorithm. Kybernetes, 24, 31-40.
https://doi.org/10.1108/03684929510147272 - 8. Evtushenko, Ya.G., Malkova, V.U. and Stanevichyus, A.A. (2009) Parallel Global Optimization of Function of Several Variables. Computational Mathematics and Mathematical Physics, 49, 246-260.
https://doi.org/10.1134/S0965542509020055 - 9. Gerge, V.P. and Sergeyev, Ya.D. (1999) Sequential and Parallel Algorithms for Global Minimizing Functions with Lipschitzian Derivatives. Computers and Mathematics with Applications, 37, 163-179.
https://doi.org/10.1016/S0898-1221(99)00067-X - 10. Sergeyev, Y.D. and Kvasov, D.E. (2013) Lipschitz Global Optimization Methods in Control Problems. Automation and Remote Control, 74, 1435-1448.
https://doi.org/10.1134/S0005117913090014 - 11. Gourdin, E., Jaumard, B. and Ellaia, R. (1996) Global Optimization of Hölder Functions. Journal of Global Optimization, 8, 323-348.
https://doi.org/10.1007/BF02403997 - 12. Lera, D. and Sergeyev, Ya.D. (2002) Global Minimization Algorithms for Hölder Functions. BIT Numerical Mathematics, 42, 119-133.
https://doi.org/10.1023/A:1021926320198 - 13. Rahal, M. and Ziadi, A. (2008) A New Extension of Piyavskii's Method to Holder Functions of Several Variables. Applied Mathematics and Computation, 197, 478-488.
https://doi.org/10.1016/j.amc.2007.07.067 - 14. Mishra, S.K. (2007) Some New Test Functions for Global Optimization and Performance of Repulsive Particle Swarm Method. University Library of Munich, Germany, MPRA Paper 2718.
- 15. Mora, G. and Cherruault, Y. (1997) Characterization and Generation of α-Dense Curve. Computers & Mathematics with Applications, 33, 83-91.
https://doi.org/10.1016/S0898-1221(97)00067-9 - 16. Mora, G., Cherruault, Y. and Ziadi, A. (2000) Functional Equations Generating Space-Densifying Curves. Computers and Mathematics with Applications, 39, 45-55.
https://doi.org/10.1016/S0898-1221(00)00085-7 - 17. Sergeyev, Y.D., Strongin, R.G. and Lera, D. (2013) Introduction to Global Optimization Exploiting Space-Filling Curves. Springer Briefs in Optimization.
https://doi.org/10.1007/978-1-4614-8042-6