# A New Filled Function Method with One Parameter for Global Optimization

Authors: Fei Wei; Yuping Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The filled function method is an effective approach to find the global minimizer of multidimensional multimodal functions. The conventional filled functions are numerically unstable due to exponential or logarithmic term and sensitive to parameters. In this paper, a new filled function with only one parameter is proposed, which is continuously differentiable and proved to satisfy all conditions of the filled function definition. Moreover, this filled function is not sensitive to parameter, and the overflow can not happen for this function. Based on these, a new filled function method is proposed, and it is numerically stable to the initial point and the parameter variable. The computer simulations indicate that the proposed filled function method is efficient and effective.


---

## Body

## 1. Introduction

More and more practical problems in science, economics, engineering, and other fields can be formulated as global optimization problems. Lots of researchers have been attracted to the field of global optimization. In recent years, many new theoretical and computational contributions have been reported for solving global optimization problems. Global optimization is mainly concerned with the characteristics and algorithms for the multimodal functions. In general, the existing approaches can be classified into two categories: deterministic methods ([1–16], e.g.) and probabilistic methods ([17–22], e.g.). The typical examples of the former are the filled function method (FFM) [3–9, 13–15], the trajectory method [2, 10], the tunneling method [12], and the covering method [1, 16], whereas ones of the latter are the clustering method [17], the methods reported in [18, 19], the simulated annealing method [22], and genetic algorithms [20, 21]. Furthermore, some hybrid deterministic and probabilistic algorithms ([23], e.g.) were proposed to solve practical problems.However, the existence of multiple local minima of a general nonconvex objective function makes global optimization become a great challenge. For global optimization problems, there are two major issues.(1)
How to find a lower minimizer of the objective function from a known local minimizer.(2)
How to evaluate the convergence and, accordingly, design the stopping criteria.In this paper, we will focus our research on the FFM and mainly issue (1). Among the existing methods for global optimization problems, the FFM appears to have several advantages over others mainly due to its relatively easy realization with a process that aims at successively finding smaller local minima. The FFM was firstly proposed by Ge in [3], which was used to solve the global minimizer of unconstrained multiextremum function. Later, many scholars have also done a lot of valuable work to improve this method ([5–9, 13–15, 24–28], e.g.). However, conventional filled functions are often nondifferentiable ([13, 25, 26], e.g.), need more than one adjustable parameter ([15], e.g.), or contain ill-conditioned terms ([3, 4, 9], e.g.). To overcome these shortcomings, some parameter-free filled functions ([13, 25], e.g.) and some filled functions without ill-conditioned terms ([26, 27], e.g.) are proposed; however, they are usually nondifferentiable, which often results in additional local minimizers. And some continuously differentiable filled functions with one parameter have been proposed ([8], e.g.), but the parameter is not easy to adjust. To deal with this problem, a new class of filled function with one parameter, which is continuously differentiable and the parameter is easy to adjust, is proposed in this paper. Based on this, a new filled function method with randomly and uniformly local search scheme is proposed, and the algorithm is numerical stability. In addition, the proposed method can be used to solve the multidimensional multi-modal problem.


## 2. Overview of the FFM

In this paper, we consider the following global optimization problem:(P)minf(x)s.t.x∈Rn,
where f(x):Rn→R is a twice continuously differentiable function. Suppose f(x) satisfies the condition f(x)→+∞ as ∥x∥→+∞. Then there exists a closed bounded domain Ω called an operating region that contains all local minimizers of f(x). Then the global optimization Problem (P) can be rewritten into an equivalent form as follows:
(P1)minf(x)s.t.x∈Ω=[l,u]={x∣x∈l≤x≤u,l,u∈Rn}.BecauseΩ can be estimated before Problem (P)  is solved, so we can assume that Ω is known without loss of generality. We only consider Problem (P1) in the following.


### 2.1. Basic Concepts and Assumptions

In this paper, we adopt the following symbols:k: the iteration number;xk′: the initial point in the kth iteration;xk*: the local minimizer of the objective function in the kth iteration;fk*: the function value at xk*;Bk*: the basin of f(x) at an isolated local minimizer xk*;x*: the global minimizer of the objective function.Assumption 1.
The functionf(x) in (P1) is continuously differentiable in Rn, f(x) has only a finite number of minimizers in Ω, and therefore every minimizer is an isolated minimizer.The basinBk* of f(x) at a local minimizer xk* is defined in [3, 4] as a connected domain, it contains xk*, and the steepest descent trajectory of f(x) converges to xk* from any initial point in Bk*. The minimal radius of Bk* at an isolated minimizer xk* is defined as
(1)R-=infx∉Bk*∥x-xk*∥.RadiusR- is not zero if ∇2f(xk*) is positive definite. The basin of f(x) at xk* is said to be lower than another basin of f(x) at another local minimizer x1* if and only if f(xk*)<f(x1*). The hill of f(x) at xk* is the basin of -f(x) at its isolated minimizer xk*.The definition of the filled function was first proposed by Ge in [3] as follows.Definition 2.
Supposexk* is a current local minimizer of f(x). P(x,xk*) is said to be a filled function of f(x) at xk*, if it satisfies the following properties:(i)
xk* is a strictly maximizer of P(x,xk*), and the whole basin Bk* of f(x) at xk* becomes a part of a hill of P(x,xk*);(ii)
P(x,xk*) has no minimizers or stable points in any basin of f(x) higher than Bk*;(iii)
iff(x) has a lower basin than Bk*, then there is a point xk+1′ in such a basin that minimizes P(x,xk*) on the line through x and xk*.Based on the filled functions, a global optimization problem can be solved via a two-phase cycle.In Phase 1, we start from an initial point and use any local minimization method to find a local minimizerxk* of f(x).In Phase 2, we construct a filled function atxk* and minimize the filled function in order to identify a point xk+1′ with f(xk+1′)<f(x*). If such a point xk+1′ is found, xk+1′ is certainly in a lower basin than Bk*. We can then use xk+1′ as an initial point in Phase 1 again, and hence we can find a better local minimizer xk+1* of f(x) with f(xk+1*)<f(x*). This process repeats until no better solution can be found. The final local minimum will be a global minimizer of f(x).


### 2.2. Overview of the FFM

As a deterministic yet a universal global optimization technique, the development of the FFM undergoes the following generations. The representative examples of the FFM in the first generation areP-functions [3] and G-functions [4] given by
(2)P(x,r,ρ)=exp(-∥x-xk*∥2/ρ2)[r+f(x)],G(x,r,ρ)=-(ρ2ln[r+f(x)]+∥x-xk*∥2).The first-generation filled functions share a common feature: there are two adjustable parameters,r and ρ, which greatly affect the performance of the algorithms and need to be appropriately adjusted. However, how to adjust the parameters is a very difficult task. Due to these drawbacks, the second-generation filled functions were proposed, and they have only one parameter. Among them, the representative examples are Q-function [4] and R-function [29]:
(3)Q(x,a)=-[f(x)-f(xk*)]exp(a∥x-xk*∥2),
where the adjustable parameter is a.Consider(4)R(x,a)=11+∥x-xk*∥·φq(f(x)-f(xk*)+q),
where
(5)φq(t)={exp(-q3t),t≠0,0,t=0,0<q<minxk*∈L(P)∖G(P)(f(xk*)-f(xg*)),
and xg*∈G(P); L(P) and G(P) stand for the set of local minimizers of f(x) and global minimizers of f(x), respectively.These filled functions only have one parameter than those in the first generation. However, these functions are liable to be ill-conditioned in practice since their function values increase exponentially due to an exponential function. As the adjustable parameter becomes larger and larger, which is required by the FFM itself, the rapidly increasing exponential function value may result in an overflow in the computation. To overcome this drawback,H-function was proposed by Liu [27]:
(6)H(x,a)=1ln[1+f(x)+f(xk*)]-a∥x-xk*∥2.TheH-function retains the advantage of the Q-function with only a single parameter and without exponential terms. The performance of the H-function in numerical experiments for a large set of testing functions was quite satisfactory [27]. H(x,a) can be regarded as the third generation due to the absence of the exponential term. Nevertheless, the H-function has a drawback which is discontinuous at x∈S={x∣f(x)=f(xk*)}.However, on the one hand, the continuity and differentiability on the FFM are required for the convergence analysis in theory [15]. On the other hand, computationally, most local minimization algorithms for the numerical nonlinear programming require the gradient information in their procedures (readers can refer to [30] or [31] for detail). Thus, it is very necessary to develop a continuously differentiable filled function with as few parameters as possible. There was already some work in this area ([8], e.g.), but the parameters of the filled functions are not easy to adjust. Based on this consideration, a continuously differentiable filled function with one parameter is designed, and the parameter, which can be as large as possible, is relatively easy to adjust.


## 2.1. Basic Concepts and Assumptions

In this paper, we adopt the following symbols:k: the iteration number;xk′: the initial point in the kth iteration;xk*: the local minimizer of the objective function in the kth iteration;fk*: the function value at xk*;Bk*: the basin of f(x) at an isolated local minimizer xk*;x*: the global minimizer of the objective function.Assumption 1.
The functionf(x) in (P1) is continuously differentiable in Rn, f(x) has only a finite number of minimizers in Ω, and therefore every minimizer is an isolated minimizer.The basinBk* of f(x) at a local minimizer xk* is defined in [3, 4] as a connected domain, it contains xk*, and the steepest descent trajectory of f(x) converges to xk* from any initial point in Bk*. The minimal radius of Bk* at an isolated minimizer xk* is defined as
(1)R-=infx∉Bk*∥x-xk*∥.RadiusR- is not zero if ∇2f(xk*) is positive definite. The basin of f(x) at xk* is said to be lower than another basin of f(x) at another local minimizer x1* if and only if f(xk*)<f(x1*). The hill of f(x) at xk* is the basin of -f(x) at its isolated minimizer xk*.The definition of the filled function was first proposed by Ge in [3] as follows.Definition 2.
Supposexk* is a current local minimizer of f(x). P(x,xk*) is said to be a filled function of f(x) at xk*, if it satisfies the following properties:(i)
xk* is a strictly maximizer of P(x,xk*), and the whole basin Bk* of f(x) at xk* becomes a part of a hill of P(x,xk*);(ii)
P(x,xk*) has no minimizers or stable points in any basin of f(x) higher than Bk*;(iii)
iff(x) has a lower basin than Bk*, then there is a point xk+1′ in such a basin that minimizes P(x,xk*) on the line through x and xk*.Based on the filled functions, a global optimization problem can be solved via a two-phase cycle.In Phase 1, we start from an initial point and use any local minimization method to find a local minimizerxk* of f(x).In Phase 2, we construct a filled function atxk* and minimize the filled function in order to identify a point xk+1′ with f(xk+1′)<f(x*). If such a point xk+1′ is found, xk+1′ is certainly in a lower basin than Bk*. We can then use xk+1′ as an initial point in Phase 1 again, and hence we can find a better local minimizer xk+1* of f(x) with f(xk+1*)<f(x*). This process repeats until no better solution can be found. The final local minimum will be a global minimizer of f(x).


## 2.2. Overview of the FFM

As a deterministic yet a universal global optimization technique, the development of the FFM undergoes the following generations. The representative examples of the FFM in the first generation areP-functions [3] and G-functions [4] given by
(2)P(x,r,ρ)=exp(-∥x-xk*∥2/ρ2)[r+f(x)],G(x,r,ρ)=-(ρ2ln[r+f(x)]+∥x-xk*∥2).The first-generation filled functions share a common feature: there are two adjustable parameters,r and ρ, which greatly affect the performance of the algorithms and need to be appropriately adjusted. However, how to adjust the parameters is a very difficult task. Due to these drawbacks, the second-generation filled functions were proposed, and they have only one parameter. Among them, the representative examples are Q-function [4] and R-function [29]:
(3)Q(x,a)=-[f(x)-f(xk*)]exp(a∥x-xk*∥2),
where the adjustable parameter is a.Consider(4)R(x,a)=11+∥x-xk*∥·φq(f(x)-f(xk*)+q),
where
(5)φq(t)={exp(-q3t),t≠0,0,t=0,0<q<minxk*∈L(P)∖G(P)(f(xk*)-f(xg*)),
and xg*∈G(P); L(P) and G(P) stand for the set of local minimizers of f(x) and global minimizers of f(x), respectively.These filled functions only have one parameter than those in the first generation. However, these functions are liable to be ill-conditioned in practice since their function values increase exponentially due to an exponential function. As the adjustable parameter becomes larger and larger, which is required by the FFM itself, the rapidly increasing exponential function value may result in an overflow in the computation. To overcome this drawback,H-function was proposed by Liu [27]:
(6)H(x,a)=1ln[1+f(x)+f(xk*)]-a∥x-xk*∥2.TheH-function retains the advantage of the Q-function with only a single parameter and without exponential terms. The performance of the H-function in numerical experiments for a large set of testing functions was quite satisfactory [27]. H(x,a) can be regarded as the third generation due to the absence of the exponential term. Nevertheless, the H-function has a drawback which is discontinuous at x∈S={x∣f(x)=f(xk*)}.However, on the one hand, the continuity and differentiability on the FFM are required for the convergence analysis in theory [15]. On the other hand, computationally, most local minimization algorithms for the numerical nonlinear programming require the gradient information in their procedures (readers can refer to [30] or [31] for detail). Thus, it is very necessary to develop a continuously differentiable filled function with as few parameters as possible. There was already some work in this area ([8], e.g.), but the parameters of the filled functions are not easy to adjust. Based on this consideration, a continuously differentiable filled function with one parameter is designed, and the parameter, which can be as large as possible, is relatively easy to adjust.


## 3. A New Filled Function and Its Properties

Definition2 relies on the concept of the basin and hill of f(x), which requires that the minima in the operating region are isolated, and Definition 2 also requires that there exists a minimal point of f(x) along a line. This is more difficult to be guaranteed. Therefore, many improvements in the definition are given in the literatures ([6, 14, 28], e.g.), which make it more convenient to construct a new filled function. In this section, we use the definition in [28] for Problem (P1).Definition 3.
Supposexk* is a current local minimizer of f(x). P(x,xk*) is said to be a filled function of f(x) at xk*, if it satisfies the following properties:(i)
xk* is a strictly maximizer of P(x,xk*);(ii)
for anyx∈Ω1, one has 0∉∇P(x,xk*), and Ω1={x∈Ω/f(x)≥f(xk*),x≠xk*};(iii)
ifΩ2={x/f(x)<f(xk*),x∈Ω} is not empty, then there exists a point xk′∈Ω2 such that xk′ is a local minimizers of P(x,xk*).Note that Definition3 about the filled function is different from the definition mentioned in [3]. It is much easier to construct a new filled function by Definition 3, and the local optimal solution of the filled function can be easily found. For example, suppose that xk* is not a global minimizer, then, by condition (iii) of Definition 3, we can find a point xk′∈Ω2 by minimizing P(x,xk*). Therefore, we can obtain a lower local minimizer xk+1* of f(x) by searching f(x) starting at xk′ via local search schemes. In the process of minimizing P(x,xk*), it does not require, unlike Definition 2, that xk+1* must be on the straight line through xk′ and xk*. So the design of the filled function is much easier and flexible.In order to find a global minimizer off(x), the major issue of the filled function method is to find a lower minimizer of f(x) or justify whether the obtained local minimizer is a global minimizer of f(x). This heavily relies on the performance of the filled function used.In this section, we propose a new filled function for Problem(P1) at a local minimizer xk* as follows:
(7)P(x,xk*)=-∥x-xk*∥2g(f(x)-f(xk*)),g(t)={π2,t≥0,r·arctan(t2)+π2,t<0,
where r is an adjustable positive real number as large as possible, used as the weight factor.Note that the proposed filled function has some advantages: first, it has one parameterr which is a positive real number as large as possible, thus it is easy to adjust, and, second, it is continuously differentiable, which makes it more easily solved by the existing local optimization method; finally, arctan(t2)∈[0,π/2) is bounded, which ensures that the calculation of P(x,xk*) will not overflow and is of numerical stability. The following theorems show that P(x,xk*) satisfies Definition 3.Theorem 4.
Suppose thatxk* is a local minimizer of f(x), then xk* is a strictly local maximizer of P(x,xk*).Proof.
Sincexk* is a local minimizer of f(x), then there exists a small positive real number ε, and a neighborhood δ=U(xk*,ε), such that, for all x∈δ, when x≠xk*, then f(x)>f(xk*), and P(x,xk*)=-π/2∥x-xk*∥2<0=P(xk*,xk*). Thus, xk* is a strictly local maximizer of P(x,xk*).Theorem4 clearly shows that P(x,xk*) satisfies the property (i) of Definition 3.Theorem 5.
Suppose Assumption1 is satisfied, xk* is a local minimizer of f(x), and for any x∈Ω1={x/f(x)≥f(xk*),x∈Ω,x≠xk*}, one has 0∉∇P(x,xk*).Proof.
For anyx∈Ω1, f(x)≥f(xk*), and for x≠xk*, one has ∇P(x,xk*)=-π(x-xk*)≠0. Consequently, 0∉∇P(x,xk*).Theorem 6.
Suppose Assumption1 is satisfied, xk* is a local minimizer of f(x), and Ω2={x/f(x)<f(xk*),x∈Ω} is not empty; then there exists a point xk′∈Ω2, such that xk′ is a local minimizer of P(x,xk*).Proof.
LetΩ3={x/f(x)≤f(xk*),x∈Ω}, ∂Ω2={x/f(x)=f(xk*),x∈Ω}; then Ω3=Ω2∪∂Ω2, where ∂Ω2 is the boundary of Ω2 (and Ω3). Since f(x) is continuous and both Ω3 and ∂Ω2 are contained in Ω, then both Ω3 and ∂Ω2 are bounded closed sets. For any x∈∂Ω2,
(8)P(x,xk*)=-π2·∥x-xk*∥2.
Since ∂Ω2 is bounded closed set, then there exists x~∈∂Ω2, such that
(9)minx∈∂Ω2P(x,xk*)=P(x~,xk*)=-π2·∥x~-xk*∥2.
Note that, for any x∈Ω2, f(x)<f(xk*), and
(10)P(x,xk*)=-∥x-xk*∥2×[π2+r·arctan(f(x)-f(xk*))2].
Since Ω2 is not empty, there exists a point x1∈Ω2=intΩ3 such that
(11)P(x1,xk*)=-∥x1-xk*∥2×[π2+r·arctan(f(x1)-f(xk*))2],
when
(12)r>π2·arctan(f(x1)-f(xk*))2(∥x~-xk*∥2∥x1-xk*∥2-1)≜r-,
for example, r=r-+1; one has P(x1,xk*)<P(x~,xk*). In other words, when r=r-+1, at least there exists a point x1∈intΩ3, such that P(x1,xk*)<P(x~,xk*). Since P(x,xk*) is continuous on closed bounded set Ω3, P(x,xk*) must have a global minimizer xk′ on Ω3 for this fixed r. Note that P(xk′,xk*)≤P(x1,xk*)<P(x~,xk*), and x~ is a global minimizer of P(x,xk*) on ∂Ω3 (and ∂Ω2), then xk′∉∂Ω3, and thus xk′∈intΩ3=Ω2, that is, xk′ is also a global minimizer of P(x,xk*) on Ω2; The proof is completed.Theorems4–6 state that the proposed filled function satisfies the conditions of Definition 3.


## 4. Filled Function Algorithm

### 4.1.  A New Local Search Method: RULS

Conventional local optimization method minimizes functionf(x) directly from the initial point xk′, and then a local minimizer xk* is obtained. In the process, the function is called repeatedly when the derivative and the search direction are calculated; in addition, the number of function evaluations is also increased in the one-dimensional search process. More importantly, with the increase of dimension, the number of iterations and the number of function evaluations are also increasing. Thus, the amount of computation for the traditional local search methods is very large, which would affect the computational efficiency. In this subsection, a new local search strategy called randomly and uniformly local search (RULS) is given, which can make the initial point closer to the local optimal solution, thereby the number of iterations and the number of function evaluations will be reduced, and the convergence speed will be accelerated.Algorithm RULS. The details for RULS are as follows.Step 1.
x
k
′
∈
Ω
=
[
l
,
u
]
=
{
x
/
l
≤
x
≤
u
,
l
,
u
∈
R
n
} is an initial point for the kth iteration, and M is the set of all points that have been used so far. Calculate a=(∑i=1|M|‍∥xk′-xi∥)/|M|, xi∈M, where |M| denotes the elements number of the set M.Step 2.
Γ
∈
Ω is a neighborhood at xk′, where Γ=[Γl,Γu]=[xk′-a/m·e,xk′+a/m·e], m>1, and e=(1,…,1)T∈Rn.SetΓl=xk′-a/m·e, and Γu=xk′+a/m·e.Fori=1 to n.IfΓl(i)<l(i) thenΓl(i)=l(i)EndifIfΓu(i)>u(i) thenΓu(i)=u(i)EndifEndforRandomly and uniformly selectb*n points Yk={y1,y2,…,ybn} in Γ, where n is the dimension of the problem, and b is the number of points selected in each dimension, M={M,Yk}.Step 3.
Calculate the function value of these pointsYk={y1,y2,…,ybn} to find the points Y- corresponding to the smallest function value, where
(13)Y-=argminyi∈Yk,i∈{1,2,…,bn}{f(y1),f(y2),…,f(ybn)}.LetX1=argminxk′,y∈Y-∪xk{f(xk′),f(y)} as a set of the initial points.Step 4.
Starting from any pointzk∈X1, minimize f(x) by using a local optimization method to obtain a local minimizer sequence X2={zk*} and a local minimum value sequence F2={f(zk*)}, set M={M,X2}.Step 5.
Calculatef(xk*)=min{f(zk*)} to obtain a local minimizer xk*, M={M,xk*}.Explanation of Algorithm RULS. uniformly and randomly generate some points near the initial point xk′, select one of the points corresponding to the smallest function value as the new initial point to minimize the function f(x), and obtain a local minimizer xk*. Diagram is shown in Figures 4(d1), 4(d2), and 4(d3).


### 4.2. A New Filled Function Algorithm (NFFA)

Based on the results of the previous content, a new filled function algorithm is proposed as follows.Algorithm
1 (NFFA)Step 1.
(initialization step)(a)
Choose a toleranceε>0, for example, ε:=1.0e-3.(b)
Choose a large integer constantB, a positive real number as large as possible r, and a small constant δ:=1.0e-3.(c)
Choose a positive integerC<B.(d)
Setf(xk-1*)=+∞, and k:=1.Step 2.
Randomly and uniformly selectb*n points Yk in the operating region, where Yk={y1,y2,…,ybn}, yi∈Ω, i∈{1,2,…,bn}, n is the dimension of the problem, and b is the number of points selected in each dimension. Calculate the function value of these points, and find the points corresponding to the smallest function value Y-=argminyi∈Yk,i∈{1,2,…,bn}{f(y1),f(y2),…,f(ybn)}. Select for all xk∈Y-.Step 3.
Starting fromxk, minimize f(x) by using RULS to obtain a local minimizer xk*; then go to Step 6.Step 4.
Construct a filled Function (7) at the local minimizer xk*, and Go to Step 5.Step 5.
Setx=xk*+δei, use x as the initial point to minimize P(x,xk*) by using RULS, and find minimizers x′ of P(x,xk*). Let xk+1=x′ and k=k+1, and then go to Step 3.Step 6 (termination step).
Ifk>C and |f(xk*)-f(xk-C*)|≤ε, (k=1,2,…) or k>B, the algorithm will stop, and x*=xk* is taken as a global minimizer of f(x); otherwise, increase r, and go to Step 4.Some Explanations about the above Filled Function Algorithm
(1)
In minimization tof(x) and P(x,xk*), a local optimization method has to be selected firstly. In our algorithm, the MATLAB function “fmincon” is used.
(2)
In Step5, the smaller δ has to be chosen accurately, in the algorithm; the δ is selected to guarantee that ∥∇P(x,xk*)∥ is greater than a threshold.
(3)
Step5 means that if local minimizer x′ of P(x,xk*) is found in Ω with f(x′)<f(xk*), we can use x′ as the initial point to minimize f(x) and obtain a better local minimizer of f(x).
(4)
In Step6, it is necessary to increase r, because the lower local minimizer may not be found when r is not large enough.


## 4.1.  A New Local Search Method: RULS

Conventional local optimization method minimizes functionf(x) directly from the initial point xk′, and then a local minimizer xk* is obtained. In the process, the function is called repeatedly when the derivative and the search direction are calculated; in addition, the number of function evaluations is also increased in the one-dimensional search process. More importantly, with the increase of dimension, the number of iterations and the number of function evaluations are also increasing. Thus, the amount of computation for the traditional local search methods is very large, which would affect the computational efficiency. In this subsection, a new local search strategy called randomly and uniformly local search (RULS) is given, which can make the initial point closer to the local optimal solution, thereby the number of iterations and the number of function evaluations will be reduced, and the convergence speed will be accelerated.Algorithm RULS. The details for RULS are as follows.Step 1.
x
k
′
∈
Ω
=
[
l
,
u
]
=
{
x
/
l
≤
x
≤
u
,
l
,
u
∈
R
n
} is an initial point for the kth iteration, and M is the set of all points that have been used so far. Calculate a=(∑i=1|M|‍∥xk′-xi∥)/|M|, xi∈M, where |M| denotes the elements number of the set M.Step 2.
Γ
∈
Ω is a neighborhood at xk′, where Γ=[Γl,Γu]=[xk′-a/m·e,xk′+a/m·e], m>1, and e=(1,…,1)T∈Rn.SetΓl=xk′-a/m·e, and Γu=xk′+a/m·e.Fori=1 to n.IfΓl(i)<l(i) thenΓl(i)=l(i)EndifIfΓu(i)>u(i) thenΓu(i)=u(i)EndifEndforRandomly and uniformly selectb*n points Yk={y1,y2,…,ybn} in Γ, where n is the dimension of the problem, and b is the number of points selected in each dimension, M={M,Yk}.Step 3.
Calculate the function value of these pointsYk={y1,y2,…,ybn} to find the points Y- corresponding to the smallest function value, where
(13)Y-=argminyi∈Yk,i∈{1,2,…,bn}{f(y1),f(y2),…,f(ybn)}.LetX1=argminxk′,y∈Y-∪xk{f(xk′),f(y)} as a set of the initial points.Step 4.
Starting from any pointzk∈X1, minimize f(x) by using a local optimization method to obtain a local minimizer sequence X2={zk*} and a local minimum value sequence F2={f(zk*)}, set M={M,X2}.Step 5.
Calculatef(xk*)=min{f(zk*)} to obtain a local minimizer xk*, M={M,xk*}.Explanation of Algorithm RULS. uniformly and randomly generate some points near the initial point xk′, select one of the points corresponding to the smallest function value as the new initial point to minimize the function f(x), and obtain a local minimizer xk*. Diagram is shown in Figures 4(d1), 4(d2), and 4(d3).


## 4.2. A New Filled Function Algorithm (NFFA)

Based on the results of the previous content, a new filled function algorithm is proposed as follows.Algorithm
1 (NFFA)Step 1.
(initialization step)(a)
Choose a toleranceε>0, for example, ε:=1.0e-3.(b)
Choose a large integer constantB, a positive real number as large as possible r, and a small constant δ:=1.0e-3.(c)
Choose a positive integerC<B.(d)
Setf(xk-1*)=+∞, and k:=1.Step 2.
Randomly and uniformly selectb*n points Yk in the operating region, where Yk={y1,y2,…,ybn}, yi∈Ω, i∈{1,2,…,bn}, n is the dimension of the problem, and b is the number of points selected in each dimension. Calculate the function value of these points, and find the points corresponding to the smallest function value Y-=argminyi∈Yk,i∈{1,2,…,bn}{f(y1),f(y2),…,f(ybn)}. Select for all xk∈Y-.Step 3.
Starting fromxk, minimize f(x) by using RULS to obtain a local minimizer xk*; then go to Step 6.Step 4.
Construct a filled Function (7) at the local minimizer xk*, and Go to Step 5.Step 5.
Setx=xk*+δei, use x as the initial point to minimize P(x,xk*) by using RULS, and find minimizers x′ of P(x,xk*). Let xk+1=x′ and k=k+1, and then go to Step 3.Step 6 (termination step).
Ifk>C and |f(xk*)-f(xk-C*)|≤ε, (k=1,2,…) or k>B, the algorithm will stop, and x*=xk* is taken as a global minimizer of f(x); otherwise, increase r, and go to Step 4.Some Explanations about the above Filled Function Algorithm
(1)
In minimization tof(x) and P(x,xk*), a local optimization method has to be selected firstly. In our algorithm, the MATLAB function “fmincon” is used.
(2)
In Step5, the smaller δ has to be chosen accurately, in the algorithm; the δ is selected to guarantee that ∥∇P(x,xk*)∥ is greater than a threshold.
(3)
Step5 means that if local minimizer x′ of P(x,xk*) is found in Ω with f(x′)<f(xk*), we can use x′ as the initial point to minimize f(x) and obtain a better local minimizer of f(x).
(4)
In Step6, it is necessary to increase r, because the lower local minimizer may not be found when r is not large enough.


## 5. Numerical Experiments

### 5.1.  Test Problems

In this section, the proposed algorithm is tested on Problem1 and Problems 2–9 taken from [14].Problem 1 (one-dimensional function).
We have(14)minf(x)=sinx+sin2x-cos4x,s.t.-2≤x≤4.
The global minimizer is x*=-1.4523, and the global optimal value is f(x*)=-2.1175.Problem 2 (two-dimensional function).
We have(15)minf(x)=[1-2x2+csin(4πx2)-x1]2minf(x)=+[x2-0.5sin(2πx1)]2,s.t.0≤x1≤10,-10≤x1≤0,
where c=0.2,0.5, and 0.05. The global minimum value is f(x*)=0 for all c.Problem 3 (three-hump back camel function).
We have(16)minf(x)=2x12-1.05x14+16·x16-x1x2+x22,s.t.-3≤x1≤3,-3≤x1≤3.
The global minimizer is x*=(0,0)T, and the global optimal value is f(x*)=0.Problem 4 (six-hump back camel function).
We have(17)minf(x)=4x12-2.1x14+13·x16-x1x2-4x22+4x24,s.t.-3≤x1≤3,-3≤x1≤3.
The global minimizers are x*=(-0.0898,-0.7127)T and x*=(0.0898,0.7127)T, and the global optimal value is f(x*)=-1.0316.Problem 5 (Treccani function).
We have(18)minf(x)=x14+4x13+4x12+x22,s.t.-3≤x1≤3,-3≤x1≤3.
This problem has two global minimizers in total, which are x*=(0,0)T and x*=(-2,0)T, and the global optimal value is f(x*)=0.Problem 6 (Goldstein and Price function).
We have(19)minf(x)=g(x)h(x),s.t.-3≤x1≤3,-3≤x1≤3,
where g(x)=1+(x1+x2+1)2(19-14x1+3x12-14x2+6x1x2+3x22), and h(x)=30+(2x1-3x2)2(18-32x1+12x12+48x2-36x1x2+27x22).The global minimizer isx*=(0,-1)T and the global optimal value is f(x*)=3.Problem 7 (two-dimensional Shubert function).
We have(20)minf(x)={∑i=15‍icos[(i+1)x1+i]}minf(x)=×{∑i=15‍icos[(i+1)x2+i]},s.t.0≤x1≤10,0≤x1≤10.
This problem has two global minimizers in total, which are x*=(4.8581,5.4829)T and x*=(5.4829,4.8581)T. The global minimum value is f(x*)=-186.7309.Problem 8 (Shekel’s function).
We have(21)minf(x)=-∑i=15‍[∑j=14‍(xj-aij)2+ci]-1,s.t.0≤xj≤10,j=1,2,3,4,
where the coefficients aij, i=1,2,3,4, and 5, j=1,2,3, and 4, are given in Table 1. The global minimizer is x=(4.0000,4.0001,4.000,4.0001)T and the global optimal value is f(x*)=-10.1529.Table 1
The coefficientsaij,ci,i=1,2,3,4,5,j=1,2,3,4.
i
a
i
1
a
i
2
a
i
3
a
i
4
c
i
1
4.0
4.0
4.0
4.0
0.1
2
1.0
1.0
1.0
1.0
0.2
3
8.0
8.0
8.0
8.0
0.3
4
6.0
6.0
6.0
6.0
0.4
5
3.0
7.0
3.0
7.0
0.5Problem 9 (n-dimensional function).
We have(22)minf(x)=πn·[10sin2πx1+g(x)+(xn-1)2],s.t.-10≤xi≤10,i=1,2,…,n,
where g(x)=∑i=1n-1‍[(xi-1)2(1+10sin2πxi+1)]. The global minimizer of this problem is x*=(1,…,1)T for all n.


### 5.2. The Experimental Results

In the following, the procedure for solving Problem1 is given, respectively, by using the traditional filled function method and the proposed algorithm, and a comparison of these two algorithms is also given.


#### 5.2.1. Conventional Filled Function Method for Solving Problem1

The procedure of the conventional filled function method is as follows.(1)
Randomly select pointx1=1.043 in the operating region Ω; then minimize f(x) from x1 by using local minimization function “fmincon” to obtain a local minimizer x1*=1.71.(2)
Construct a filled Function (7) at x1*=1.71, where
(23)f(x)=sinx+sin2x-cos4x,g(t)={π2,t≥0,5·arctan(t2)+π2,t<0.(3)
MinimizeP(x,x1*) to obtain a local minimizer x2=-0.32 of P(x,x1*); the specific processes of Steps (1), (2), and (3) are shown in Figure 1. Note that Figure 1(a′) is to enlarge the rectangular box in Figure 1(a), behind Figures 2(b′) and 3(c′), and so on, also said this, therefore, not to repeat explained.(4)
Minimizef(x) from x2=-0.32 to obtain a local minimizer x2*=-0.2 of f(x). Construct a filled function P(x,x2*) at x2*, where r=5, and then minimize the filled function P(x,x2*) to obtain a local minimizer x3=-1.15 of P(x,x2*) (as shown in Figure 2).(5)
Minimizef(x) from x3=-1.15 to obtain a local minimizer x3*=-1.4523. Construct a filled function P(x,x3*) at x3*, where r=5, which is shown in Figure 3, and then minimize P(x,x3*). Without any stable point is found. Then the iteration terminates, and set x*=x3*. The global minimizer x*=-1.4523 and the global minimum value f(x*)=-2.1175 are obtained.Figure 1
((a) and (a′)) The process of Steps(1), (2), and (3) in Section 5.2.1.Figure 2
((b) and (b′)) The process of Step(4) in Section 5.2.1.Figure 3
((c) and (c′)) The process of Step(5) in Section 5.2.1.Figure 4
((d1), (d2), and (d3)) The process of Steps (1), (2), and (3) in Section 5.2.2.Conventional filled function algorithm is run independently 50 times; the mean number of function evaluations is 18.7119.


#### 5.2.2. The Proposed Filled Function Algorithm for Solving Problem1

The procedure of the proposed filled function algorithm for solving Problem1 is as follows.(1)
Uniformly and randomly generate three pointsx01=0, x02=2.2, and x03=3.35 in the operating region, set M={x01,x02,x03}, and calculate the function value f(x) of the three points. Find the point x0′=0 corresponding to the smallest function value, as shown in (d1) of Figure 4.(2)
Calculatea=∑i=1|M|‍∥x0′-xi∥/|M|=(∥0-2.2∥+∥0-3.35∥)/2=2.775 by using the rule in RULS, where xi∈M, i∈{1,2,…,|M|}; let m=5, and then
(24)Γ=[x0′-am,x0′+am]=[x0′-0.555,x0′+0.555].
Randomly select three points Yk in Γ, calculate their value of f(x) to find the point x1 corresponding to the smallest function value, as shown in (d2) of Figure 4, and set M={M,x1}.(3)
Minimizef(x) from x1 by using a local optimization method to find a local minimizer x1*=-0.2 and a minima f(x1*)=-1.285, as shown in (d3) of Figure 4, and set M={M,x1*}.Steps(2) and (3) describe the specific process of RULS, as shown in (d2) and (d3) of Figure 4.(4)
Construct a filled Function (7) at x1*=-0.2, as shown in Figure 5, where f(x)=sinx+sin2x-cos4x,
(25)g(t)={π2,t≥0,4·arctan(t2)+π2,t<0.(5)
Optimize the functionP(x,x1*) at x1*=-0.2 by using RULS method to obtain a minimizer x2=-1.53 of P(x,x1*), as shown in (d4) of Figure 4. Set x0′=x2 and M={M,x2*}, and then minimize f(x) by using RULS to obtain x2*=-1.4523 and f(x2*)=-2.1175.(6)
Construct a filled functionP(x,x2*) at x2*, where r=4, as shown in Figure 6.(7)
FunctionP(x,x2*) without a stable point in {x∈Ω∣x≠x2*}, so the iteration terminates. Set x*=x2*. The global minimizer x*=-1.4523 and the global minimum value f(x*)=-2.1175 are obtained.Figure 5
((d4) and (d4′)) The process of Step (4) in Section 5.2.2.Figure 6
((d5) and (d5′)) The process of Step (5) in Section 5.2.2.The proposed algorithm runs independently 50 times; the mean number of function evaluations is 13.6168, which is significantly less than the former result that uses conventional filled function method.Both experimental results of Sections5.2.1 and 5.2.2 and the mean number of function evaluations show that the proposed filled function method is more efficient.


#### 5.2.3. The Proposed Filled Function Method for Solving the Problems Taken from [14]

The proposed algorithm is executed on the above test Problems2–9. The results obtained by the proposed algorithm and the comparison with [14] are listed in Tables 2, 3, and 4.Table 2
The results obtained by the proposed algorithm.
No.
r
(
>
)
q
x
k
*
f-mean
f-best
f-std
Ratio (%)
2 (c=0.2) (n=2)
100
78.5510
(1.5909; −0.2703)(0.9997; −0.0005) (1.8784; −0.3458) (0.9820; −0.0565)
3.6840
e
-
010
6.2589
e
-
017
1.8044
e
-
009
100
2 (c=0.5) (n=2)
100
67.5000
(1; 0)(1.5872; −0.2606) (1.8973; −0.3005)
1.0221
e
-
012
0
2.0430
e
-
012
100
2 (c=0.05) (n=2)
100
80.7500
(1.8513; −0.4021)(1.5975; −0.2874)
2.9402
e
-
10
2.8417
e
-
012
2.5634
e
-
008
100
3 (n=2)
100
67.9796
(0; 0)
4.7567
e
-
009
0
1.2455
e
-
009
100
4 (n=2)
100
84.2449
(0.0898; 0.7127)(−0.0898; −0.7127)
−1.0316
-
1.0316
1.2574
e
-
007
100
5 (n=2)
100
53.1224
(0; 0)(−2; 0)
3.5872
e
-
008
0
3.5668
e
-
008
100
6 (n=2)
1000
64.9796
(0; −1)
3.0000
3.0000
8.6282
e
-
008
100
7 (n=2)
100
625.4898
(4.8581; 5.4829)(5.4829; 4.8581)
−186.7309
-
186.7309
1.0480
e
-
007
100
8 (n=2)
100
357.1429
(0.0000; 0.0000)
−10.1529
-
10.1529
6.7489
e
-
010
100
9 (n=2)
100
107.6939
(1; 1)
1.8548
e
-
007
0
1.1284
e
-
007
100
9 (n=3)
100
90.1429
(1; 1; 1)
5.6906
e
-
011
0
2.5855
e
-
007
95.92Table 3
The results obtained by the proposed algorithm and the algorithm in [14].
No.
The proposed algorithm
The algorithm of the literature [14]
q
x
k
*
times
q
x
k
*
times
2 (c=0.2) (n=2)
78.5510
(1.5909; −0.2703)(0.9997; −0.0005) (1.8784; −0.3458) (0.9820; −0.0565)
0.341403
500.3
(1.8784; −0.3458)
1.097546
2 (c=0.5) (n=2)
67.5000
(1; 0)(1.5872; −0.2606) (1.8973; −0.3005)
0.175545
641.5
(1.0000;-2.2205e-14)
0.548026
2 (c=0.05) (n=2)
80.7500
(1.8513; −0.4021)(1.5975; −0.2874)
0.548172
262.3
(1.8513; −0.4020)
0.726323
3 (n=2)
67.9796
(0; 0)
0.135797
564
(0; 0)
1.017142
4 (n=2)
84.2449
(0.0898; 0.7127)(−0.0898; −0.7127)
0.162335
551
(0.0898; 0.7127)(−0.0898; −0.7127)
0.453289
5 (n=2)
53.1224
(0; 0)(−2; 0)
0.350461
632
(0; 0)
0.613838
6 (n=2)
64.9796
(0; −1)
0.135588
852.7
(0; −1)
0.356531
7 (n=2)
625.4898
(4.8581; 5.4829)(5.4829; 4.8581)
0.126097
6468
(5.4829; 4.8581)
0.274596
8 (n=4)
357.1429
(4.0000; 4.0001; 4.0000; 4.0001)
0.425600
513
(4.0000; 4.0001; 4.0000; 4.0001)
0.701534
9 (n=2)
107.6939
(1; 1)
0.126054
663
(1; 1)
0.707344
9 (n=3)
90.1429
(1; 1; 1)
0.135507
624.7
(1; 1; 1)
0.212676
9 (n=7)
6028
(1.0000; 1.0000; 1.0001; 1.0001; 1.0001; 1.0001; 1.0003)
1.067376
14678
(1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000)
1.105676
9 (n=10)
6027
(1.0000; 1.0001; 1.0000; 1.0000; 1.0003; 1.0000; 1.0000; 1.0000; 1.0000; 1.0001)
0.123788
31351
(1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000)
0.282408Table 4
The results obtained by the proposed algorithm for solving Problem9 with different dimensions.
No.
r
(
>
)
q
f-mean
f-best
f-std
Ratio (%)
9 (n=7)
1000
6028
7.5895
e
-
008
8.2743
e
-
008
0
100
9 (n=10)
1000
6027
0.0012
8.3180
e
-
007
0.0020
97.10
9 (n=12)
1.0
e
+
5
641.0518
1.5597
e
-
005
2.0935
e
-
010
1.1098
e
-
008
93.47
9 (n=15)
1.0
e
+
6
972.1050
2.4116
e
-
005
1.8709
e
-
013
1.0032
e
-
005
89.78
9 (n=20)
1.0
e
+
9
1321.3011
1.1602
e
-
004
8.2346
e
-
008
5.0653
e
-
006
85.57
9 (n=30)
1.0
e
+
9
2666.1220
0.3012
5.3080
e
-
005
3.0120
e
-
004
89.87The symbols used in Tables2, 3, and 4 are given as follows:No.: the number of the test problems;n: the dimension of the test problems;r: the parameter of the filled function;k: the iteration number;q: the total number of function and gradient evaluations of f(x) and P(x,xk*);xk*: the local minimizer of the objective function in the kth iteration;fk*: the function value at xk*;x*: the global minimizer of the objective function;times: the once running time (second);f-mean: the mean function value, respectively, in the 50 runs;f-best: the best function value, respectively, in the 50 runs;f-std: the standard deviation of function value, respectively, in the 50 runs;ratio: the ratio of the successful runs, that is, the ratio of the runs finding the true optimal solution in the 50 runs.It can be seen from Tables2, 3, and 4 that the proposed algorithm has the following advantages.(1) More Minimizers Are Obtained. In the proposed algorithm, the initial points are randomly and uniformly generated. This is helpful to get more different global minimizers in the 50 runs. For example, for Problems 2, 5, and 7, more optimal solutions are obtained by the proposed algorithm than those obtained by the algorithm in the literature [14].(2) More Effective and Efficient. The optimal solutions of all test problems can be found by the proposed algorithm. This indicates the effectiveness of the proposed algorithm. In addition, it can be seen from Table 3 that both the mean number of function evaluations q and the once running time obtained by the proposed algorithm are smaller than that obtained by the algorithm in [14]. This also indicates the efficiency of the proposed algorithm.(3) More Stability. It can be seen from column ratio in Table 2 that the ratio of the successful runs is more than 95.92%, and most of them are 100%, which shows that the proposed algorithm is stable. In addition, it can be seen from columns f-mean and f-std that difference between f-mean and f-best is small, and f-std is also small. This also indicates that the proposed algorithm is stable and robust to the initial points and parameter variation.(4) Applicable to Multidimensional Problems. In Table 4, Problem 9 with different dimensions is tested, and the numerical results indicate that the proposed algorithm is suitable for solving multidimensional problems.


## 5.1.  Test Problems

In this section, the proposed algorithm is tested on Problem1 and Problems 2–9 taken from [14].Problem 1 (one-dimensional function).
We have(14)minf(x)=sinx+sin2x-cos4x,s.t.-2≤x≤4.
The global minimizer is x*=-1.4523, and the global optimal value is f(x*)=-2.1175.Problem 2 (two-dimensional function).
We have(15)minf(x)=[1-2x2+csin(4πx2)-x1]2minf(x)=+[x2-0.5sin(2πx1)]2,s.t.0≤x1≤10,-10≤x1≤0,
where c=0.2,0.5, and 0.05. The global minimum value is f(x*)=0 for all c.Problem 3 (three-hump back camel function).
We have(16)minf(x)=2x12-1.05x14+16·x16-x1x2+x22,s.t.-3≤x1≤3,-3≤x1≤3.
The global minimizer is x*=(0,0)T, and the global optimal value is f(x*)=0.Problem 4 (six-hump back camel function).
We have(17)minf(x)=4x12-2.1x14+13·x16-x1x2-4x22+4x24,s.t.-3≤x1≤3,-3≤x1≤3.
The global minimizers are x*=(-0.0898,-0.7127)T and x*=(0.0898,0.7127)T, and the global optimal value is f(x*)=-1.0316.Problem 5 (Treccani function).
We have(18)minf(x)=x14+4x13+4x12+x22,s.t.-3≤x1≤3,-3≤x1≤3.
This problem has two global minimizers in total, which are x*=(0,0)T and x*=(-2,0)T, and the global optimal value is f(x*)=0.Problem 6 (Goldstein and Price function).
We have(19)minf(x)=g(x)h(x),s.t.-3≤x1≤3,-3≤x1≤3,
where g(x)=1+(x1+x2+1)2(19-14x1+3x12-14x2+6x1x2+3x22), and h(x)=30+(2x1-3x2)2(18-32x1+12x12+48x2-36x1x2+27x22).The global minimizer isx*=(0,-1)T and the global optimal value is f(x*)=3.Problem 7 (two-dimensional Shubert function).
We have(20)minf(x)={∑i=15‍icos[(i+1)x1+i]}minf(x)=×{∑i=15‍icos[(i+1)x2+i]},s.t.0≤x1≤10,0≤x1≤10.
This problem has two global minimizers in total, which are x*=(4.8581,5.4829)T and x*=(5.4829,4.8581)T. The global minimum value is f(x*)=-186.7309.Problem 8 (Shekel’s function).
We have(21)minf(x)=-∑i=15‍[∑j=14‍(xj-aij)2+ci]-1,s.t.0≤xj≤10,j=1,2,3,4,
where the coefficients aij, i=1,2,3,4, and 5, j=1,2,3, and 4, are given in Table 1. The global minimizer is x=(4.0000,4.0001,4.000,4.0001)T and the global optimal value is f(x*)=-10.1529.Table 1
The coefficientsaij,ci,i=1,2,3,4,5,j=1,2,3,4.
i
a
i
1
a
i
2
a
i
3
a
i
4
c
i
1
4.0
4.0
4.0
4.0
0.1
2
1.0
1.0
1.0
1.0
0.2
3
8.0
8.0
8.0
8.0
0.3
4
6.0
6.0
6.0
6.0
0.4
5
3.0
7.0
3.0
7.0
0.5Problem 9 (n-dimensional function).
We have(22)minf(x)=πn·[10sin2πx1+g(x)+(xn-1)2],s.t.-10≤xi≤10,i=1,2,…,n,
where g(x)=∑i=1n-1‍[(xi-1)2(1+10sin2πxi+1)]. The global minimizer of this problem is x*=(1,…,1)T for all n.


## 5.2. The Experimental Results

In the following, the procedure for solving Problem1 is given, respectively, by using the traditional filled function method and the proposed algorithm, and a comparison of these two algorithms is also given.


### 5.2.1. Conventional Filled Function Method for Solving Problem1

The procedure of the conventional filled function method is as follows.(1)
Randomly select pointx1=1.043 in the operating region Ω; then minimize f(x) from x1 by using local minimization function “fmincon” to obtain a local minimizer x1*=1.71.(2)
Construct a filled Function (7) at x1*=1.71, where
(23)f(x)=sinx+sin2x-cos4x,g(t)={π2,t≥0,5·arctan(t2)+π2,t<0.(3)
MinimizeP(x,x1*) to obtain a local minimizer x2=-0.32 of P(x,x1*); the specific processes of Steps (1), (2), and (3) are shown in Figure 1. Note that Figure 1(a′) is to enlarge the rectangular box in Figure 1(a), behind Figures 2(b′) and 3(c′), and so on, also said this, therefore, not to repeat explained.(4)
Minimizef(x) from x2=-0.32 to obtain a local minimizer x2*=-0.2 of f(x). Construct a filled function P(x,x2*) at x2*, where r=5, and then minimize the filled function P(x,x2*) to obtain a local minimizer x3=-1.15 of P(x,x2*) (as shown in Figure 2).(5)
Minimizef(x) from x3=-1.15 to obtain a local minimizer x3*=-1.4523. Construct a filled function P(x,x3*) at x3*, where r=5, which is shown in Figure 3, and then minimize P(x,x3*). Without any stable point is found. Then the iteration terminates, and set x*=x3*. The global minimizer x*=-1.4523 and the global minimum value f(x*)=-2.1175 are obtained.Figure 1
((a) and (a′)) The process of Steps(1), (2), and (3) in Section 5.2.1.Figure 2
((b) and (b′)) The process of Step(4) in Section 5.2.1.Figure 3
((c) and (c′)) The process of Step(5) in Section 5.2.1.Figure 4
((d1), (d2), and (d3)) The process of Steps (1), (2), and (3) in Section 5.2.2.Conventional filled function algorithm is run independently 50 times; the mean number of function evaluations is 18.7119.


### 5.2.2. The Proposed Filled Function Algorithm for Solving Problem1

The procedure of the proposed filled function algorithm for solving Problem1 is as follows.(1)
Uniformly and randomly generate three pointsx01=0, x02=2.2, and x03=3.35 in the operating region, set M={x01,x02,x03}, and calculate the function value f(x) of the three points. Find the point x0′=0 corresponding to the smallest function value, as shown in (d1) of Figure 4.(2)
Calculatea=∑i=1|M|‍∥x0′-xi∥/|M|=(∥0-2.2∥+∥0-3.35∥)/2=2.775 by using the rule in RULS, where xi∈M, i∈{1,2,…,|M|}; let m=5, and then
(24)Γ=[x0′-am,x0′+am]=[x0′-0.555,x0′+0.555].
Randomly select three points Yk in Γ, calculate their value of f(x) to find the point x1 corresponding to the smallest function value, as shown in (d2) of Figure 4, and set M={M,x1}.(3)
Minimizef(x) from x1 by using a local optimization method to find a local minimizer x1*=-0.2 and a minima f(x1*)=-1.285, as shown in (d3) of Figure 4, and set M={M,x1*}.Steps(2) and (3) describe the specific process of RULS, as shown in (d2) and (d3) of Figure 4.(4)
Construct a filled Function (7) at x1*=-0.2, as shown in Figure 5, where f(x)=sinx+sin2x-cos4x,
(25)g(t)={π2,t≥0,4·arctan(t2)+π2,t<0.(5)
Optimize the functionP(x,x1*) at x1*=-0.2 by using RULS method to obtain a minimizer x2=-1.53 of P(x,x1*), as shown in (d4) of Figure 4. Set x0′=x2 and M={M,x2*}, and then minimize f(x) by using RULS to obtain x2*=-1.4523 and f(x2*)=-2.1175.(6)
Construct a filled functionP(x,x2*) at x2*, where r=4, as shown in Figure 6.(7)
FunctionP(x,x2*) without a stable point in {x∈Ω∣x≠x2*}, so the iteration terminates. Set x*=x2*. The global minimizer x*=-1.4523 and the global minimum value f(x*)=-2.1175 are obtained.Figure 5
((d4) and (d4′)) The process of Step (4) in Section 5.2.2.Figure 6
((d5) and (d5′)) The process of Step (5) in Section 5.2.2.The proposed algorithm runs independently 50 times; the mean number of function evaluations is 13.6168, which is significantly less than the former result that uses conventional filled function method.Both experimental results of Sections5.2.1 and 5.2.2 and the mean number of function evaluations show that the proposed filled function method is more efficient.


### 5.2.3. The Proposed Filled Function Method for Solving the Problems Taken from [14]

The proposed algorithm is executed on the above test Problems2–9. The results obtained by the proposed algorithm and the comparison with [14] are listed in Tables 2, 3, and 4.Table 2
The results obtained by the proposed algorithm.
No.
r
(
>
)
q
x
k
*
f-mean
f-best
f-std
Ratio (%)
2 (c=0.2) (n=2)
100
78.5510
(1.5909; −0.2703)(0.9997; −0.0005) (1.8784; −0.3458) (0.9820; −0.0565)
3.6840
e
-
010
6.2589
e
-
017
1.8044
e
-
009
100
2 (c=0.5) (n=2)
100
67.5000
(1; 0)(1.5872; −0.2606) (1.8973; −0.3005)
1.0221
e
-
012
0
2.0430
e
-
012
100
2 (c=0.05) (n=2)
100
80.7500
(1.8513; −0.4021)(1.5975; −0.2874)
2.9402
e
-
10
2.8417
e
-
012
2.5634
e
-
008
100
3 (n=2)
100
67.9796
(0; 0)
4.7567
e
-
009
0
1.2455
e
-
009
100
4 (n=2)
100
84.2449
(0.0898; 0.7127)(−0.0898; −0.7127)
−1.0316
-
1.0316
1.2574
e
-
007
100
5 (n=2)
100
53.1224
(0; 0)(−2; 0)
3.5872
e
-
008
0
3.5668
e
-
008
100
6 (n=2)
1000
64.9796
(0; −1)
3.0000
3.0000
8.6282
e
-
008
100
7 (n=2)
100
625.4898
(4.8581; 5.4829)(5.4829; 4.8581)
−186.7309
-
186.7309
1.0480
e
-
007
100
8 (n=2)
100
357.1429
(0.0000; 0.0000)
−10.1529
-
10.1529
6.7489
e
-
010
100
9 (n=2)
100
107.6939
(1; 1)
1.8548
e
-
007
0
1.1284
e
-
007
100
9 (n=3)
100
90.1429
(1; 1; 1)
5.6906
e
-
011
0
2.5855
e
-
007
95.92Table 3
The results obtained by the proposed algorithm and the algorithm in [14].
No.
The proposed algorithm
The algorithm of the literature [14]
q
x
k
*
times
q
x
k
*
times
2 (c=0.2) (n=2)
78.5510
(1.5909; −0.2703)(0.9997; −0.0005) (1.8784; −0.3458) (0.9820; −0.0565)
0.341403
500.3
(1.8784; −0.3458)
1.097546
2 (c=0.5) (n=2)
67.5000
(1; 0)(1.5872; −0.2606) (1.8973; −0.3005)
0.175545
641.5
(1.0000;-2.2205e-14)
0.548026
2 (c=0.05) (n=2)
80.7500
(1.8513; −0.4021)(1.5975; −0.2874)
0.548172
262.3
(1.8513; −0.4020)
0.726323
3 (n=2)
67.9796
(0; 0)
0.135797
564
(0; 0)
1.017142
4 (n=2)
84.2449
(0.0898; 0.7127)(−0.0898; −0.7127)
0.162335
551
(0.0898; 0.7127)(−0.0898; −0.7127)
0.453289
5 (n=2)
53.1224
(0; 0)(−2; 0)
0.350461
632
(0; 0)
0.613838
6 (n=2)
64.9796
(0; −1)
0.135588
852.7
(0; −1)
0.356531
7 (n=2)
625.4898
(4.8581; 5.4829)(5.4829; 4.8581)
0.126097
6468
(5.4829; 4.8581)
0.274596
8 (n=4)
357.1429
(4.0000; 4.0001; 4.0000; 4.0001)
0.425600
513
(4.0000; 4.0001; 4.0000; 4.0001)
0.701534
9 (n=2)
107.6939
(1; 1)
0.126054
663
(1; 1)
0.707344
9 (n=3)
90.1429
(1; 1; 1)
0.135507
624.7
(1; 1; 1)
0.212676
9 (n=7)
6028
(1.0000; 1.0000; 1.0001; 1.0001; 1.0001; 1.0001; 1.0003)
1.067376
14678
(1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000)
1.105676
9 (n=10)
6027
(1.0000; 1.0001; 1.0000; 1.0000; 1.0003; 1.0000; 1.0000; 1.0000; 1.0000; 1.0001)
0.123788
31351
(1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000)
0.282408Table 4
The results obtained by the proposed algorithm for solving Problem9 with different dimensions.
No.
r
(
>
)
q
f-mean
f-best
f-std
Ratio (%)
9 (n=7)
1000
6028
7.5895
e
-
008
8.2743
e
-
008
0
100
9 (n=10)
1000
6027
0.0012
8.3180
e
-
007
0.0020
97.10
9 (n=12)
1.0
e
+
5
641.0518
1.5597
e
-
005
2.0935
e
-
010
1.1098
e
-
008
93.47
9 (n=15)
1.0
e
+
6
972.1050
2.4116
e
-
005
1.8709
e
-
013
1.0032
e
-
005
89.78
9 (n=20)
1.0
e
+
9
1321.3011
1.1602
e
-
004
8.2346
e
-
008
5.0653
e
-
006
85.57
9 (n=30)
1.0
e
+
9
2666.1220
0.3012
5.3080
e
-
005
3.0120
e
-
004
89.87The symbols used in Tables2, 3, and 4 are given as follows:No.: the number of the test problems;n: the dimension of the test problems;r: the parameter of the filled function;k: the iteration number;q: the total number of function and gradient evaluations of f(x) and P(x,xk*);xk*: the local minimizer of the objective function in the kth iteration;fk*: the function value at xk*;x*: the global minimizer of the objective function;times: the once running time (second);f-mean: the mean function value, respectively, in the 50 runs;f-best: the best function value, respectively, in the 50 runs;f-std: the standard deviation of function value, respectively, in the 50 runs;ratio: the ratio of the successful runs, that is, the ratio of the runs finding the true optimal solution in the 50 runs.It can be seen from Tables2, 3, and 4 that the proposed algorithm has the following advantages.(1) More Minimizers Are Obtained. In the proposed algorithm, the initial points are randomly and uniformly generated. This is helpful to get more different global minimizers in the 50 runs. For example, for Problems 2, 5, and 7, more optimal solutions are obtained by the proposed algorithm than those obtained by the algorithm in the literature [14].(2) More Effective and Efficient. The optimal solutions of all test problems can be found by the proposed algorithm. This indicates the effectiveness of the proposed algorithm. In addition, it can be seen from Table 3 that both the mean number of function evaluations q and the once running time obtained by the proposed algorithm are smaller than that obtained by the algorithm in [14]. This also indicates the efficiency of the proposed algorithm.(3) More Stability. It can be seen from column ratio in Table 2 that the ratio of the successful runs is more than 95.92%, and most of them are 100%, which shows that the proposed algorithm is stable. In addition, it can be seen from columns f-mean and f-std that difference between f-mean and f-best is small, and f-std is also small. This also indicates that the proposed algorithm is stable and robust to the initial points and parameter variation.(4) Applicable to Multidimensional Problems. In Table 4, Problem 9 with different dimensions is tested, and the numerical results indicate that the proposed algorithm is suitable for solving multidimensional problems.


## 5.2.1. Conventional Filled Function Method for Solving Problem1

The procedure of the conventional filled function method is as follows.(1)
Randomly select pointx1=1.043 in the operating region Ω; then minimize f(x) from x1 by using local minimization function “fmincon” to obtain a local minimizer x1*=1.71.(2)
Construct a filled Function (7) at x1*=1.71, where
(23)f(x)=sinx+sin2x-cos4x,g(t)={π2,t≥0,5·arctan(t2)+π2,t<0.(3)
MinimizeP(x,x1*) to obtain a local minimizer x2=-0.32 of P(x,x1*); the specific processes of Steps (1), (2), and (3) are shown in Figure 1. Note that Figure 1(a′) is to enlarge the rectangular box in Figure 1(a), behind Figures 2(b′) and 3(c′), and so on, also said this, therefore, not to repeat explained.(4)
Minimizef(x) from x2=-0.32 to obtain a local minimizer x2*=-0.2 of f(x). Construct a filled function P(x,x2*) at x2*, where r=5, and then minimize the filled function P(x,x2*) to obtain a local minimizer x3=-1.15 of P(x,x2*) (as shown in Figure 2).(5)
Minimizef(x) from x3=-1.15 to obtain a local minimizer x3*=-1.4523. Construct a filled function P(x,x3*) at x3*, where r=5, which is shown in Figure 3, and then minimize P(x,x3*). Without any stable point is found. Then the iteration terminates, and set x*=x3*. The global minimizer x*=-1.4523 and the global minimum value f(x*)=-2.1175 are obtained.Figure 1
((a) and (a′)) The process of Steps(1), (2), and (3) in Section 5.2.1.Figure 2
((b) and (b′)) The process of Step(4) in Section 5.2.1.Figure 3
((c) and (c′)) The process of Step(5) in Section 5.2.1.Figure 4
((d1), (d2), and (d3)) The process of Steps (1), (2), and (3) in Section 5.2.2.Conventional filled function algorithm is run independently 50 times; the mean number of function evaluations is 18.7119.


## 5.2.2. The Proposed Filled Function Algorithm for Solving Problem1

The procedure of the proposed filled function algorithm for solving Problem1 is as follows.(1)
Uniformly and randomly generate three pointsx01=0, x02=2.2, and x03=3.35 in the operating region, set M={x01,x02,x03}, and calculate the function value f(x) of the three points. Find the point x0′=0 corresponding to the smallest function value, as shown in (d1) of Figure 4.(2)
Calculatea=∑i=1|M|‍∥x0′-xi∥/|M|=(∥0-2.2∥+∥0-3.35∥)/2=2.775 by using the rule in RULS, where xi∈M, i∈{1,2,…,|M|}; let m=5, and then
(24)Γ=[x0′-am,x0′+am]=[x0′-0.555,x0′+0.555].
Randomly select three points Yk in Γ, calculate their value of f(x) to find the point x1 corresponding to the smallest function value, as shown in (d2) of Figure 4, and set M={M,x1}.(3)
Minimizef(x) from x1 by using a local optimization method to find a local minimizer x1*=-0.2 and a minima f(x1*)=-1.285, as shown in (d3) of Figure 4, and set M={M,x1*}.Steps(2) and (3) describe the specific process of RULS, as shown in (d2) and (d3) of Figure 4.(4)
Construct a filled Function (7) at x1*=-0.2, as shown in Figure 5, where f(x)=sinx+sin2x-cos4x,
(25)g(t)={π2,t≥0,4·arctan(t2)+π2,t<0.(5)
Optimize the functionP(x,x1*) at x1*=-0.2 by using RULS method to obtain a minimizer x2=-1.53 of P(x,x1*), as shown in (d4) of Figure 4. Set x0′=x2 and M={M,x2*}, and then minimize f(x) by using RULS to obtain x2*=-1.4523 and f(x2*)=-2.1175.(6)
Construct a filled functionP(x,x2*) at x2*, where r=4, as shown in Figure 6.(7)
FunctionP(x,x2*) without a stable point in {x∈Ω∣x≠x2*}, so the iteration terminates. Set x*=x2*. The global minimizer x*=-1.4523 and the global minimum value f(x*)=-2.1175 are obtained.Figure 5
((d4) and (d4′)) The process of Step (4) in Section 5.2.2.Figure 6
((d5) and (d5′)) The process of Step (5) in Section 5.2.2.The proposed algorithm runs independently 50 times; the mean number of function evaluations is 13.6168, which is significantly less than the former result that uses conventional filled function method.Both experimental results of Sections5.2.1 and 5.2.2 and the mean number of function evaluations show that the proposed filled function method is more efficient.


## 5.2.3. The Proposed Filled Function Method for Solving the Problems Taken from [14]

The proposed algorithm is executed on the above test Problems2–9. The results obtained by the proposed algorithm and the comparison with [14] are listed in Tables 2, 3, and 4.Table 2
The results obtained by the proposed algorithm.
No.
r
(
>
)
q
x
k
*
f-mean
f-best
f-std
Ratio (%)
2 (c=0.2) (n=2)
100
78.5510
(1.5909; −0.2703)(0.9997; −0.0005) (1.8784; −0.3458) (0.9820; −0.0565)
3.6840
e
-
010
6.2589
e
-
017
1.8044
e
-
009
100
2 (c=0.5) (n=2)
100
67.5000
(1; 0)(1.5872; −0.2606) (1.8973; −0.3005)
1.0221
e
-
012
0
2.0430
e
-
012
100
2 (c=0.05) (n=2)
100
80.7500
(1.8513; −0.4021)(1.5975; −0.2874)
2.9402
e
-
10
2.8417
e
-
012
2.5634
e
-
008
100
3 (n=2)
100
67.9796
(0; 0)
4.7567
e
-
009
0
1.2455
e
-
009
100
4 (n=2)
100
84.2449
(0.0898; 0.7127)(−0.0898; −0.7127)
−1.0316
-
1.0316
1.2574
e
-
007
100
5 (n=2)
100
53.1224
(0; 0)(−2; 0)
3.5872
e
-
008
0
3.5668
e
-
008
100
6 (n=2)
1000
64.9796
(0; −1)
3.0000
3.0000
8.6282
e
-
008
100
7 (n=2)
100
625.4898
(4.8581; 5.4829)(5.4829; 4.8581)
−186.7309
-
186.7309
1.0480
e
-
007
100
8 (n=2)
100
357.1429
(0.0000; 0.0000)
−10.1529
-
10.1529
6.7489
e
-
010
100
9 (n=2)
100
107.6939
(1; 1)
1.8548
e
-
007
0
1.1284
e
-
007
100
9 (n=3)
100
90.1429
(1; 1; 1)
5.6906
e
-
011
0
2.5855
e
-
007
95.92Table 3
The results obtained by the proposed algorithm and the algorithm in [14].
No.
The proposed algorithm
The algorithm of the literature [14]
q
x
k
*
times
q
x
k
*
times
2 (c=0.2) (n=2)
78.5510
(1.5909; −0.2703)(0.9997; −0.0005) (1.8784; −0.3458) (0.9820; −0.0565)
0.341403
500.3
(1.8784; −0.3458)
1.097546
2 (c=0.5) (n=2)
67.5000
(1; 0)(1.5872; −0.2606) (1.8973; −0.3005)
0.175545
641.5
(1.0000;-2.2205e-14)
0.548026
2 (c=0.05) (n=2)
80.7500
(1.8513; −0.4021)(1.5975; −0.2874)
0.548172
262.3
(1.8513; −0.4020)
0.726323
3 (n=2)
67.9796
(0; 0)
0.135797
564
(0; 0)
1.017142
4 (n=2)
84.2449
(0.0898; 0.7127)(−0.0898; −0.7127)
0.162335
551
(0.0898; 0.7127)(−0.0898; −0.7127)
0.453289
5 (n=2)
53.1224
(0; 0)(−2; 0)
0.350461
632
(0; 0)
0.613838
6 (n=2)
64.9796
(0; −1)
0.135588
852.7
(0; −1)
0.356531
7 (n=2)
625.4898
(4.8581; 5.4829)(5.4829; 4.8581)
0.126097
6468
(5.4829; 4.8581)
0.274596
8 (n=4)
357.1429
(4.0000; 4.0001; 4.0000; 4.0001)
0.425600
513
(4.0000; 4.0001; 4.0000; 4.0001)
0.701534
9 (n=2)
107.6939
(1; 1)
0.126054
663
(1; 1)
0.707344
9 (n=3)
90.1429
(1; 1; 1)
0.135507
624.7
(1; 1; 1)
0.212676
9 (n=7)
6028
(1.0000; 1.0000; 1.0001; 1.0001; 1.0001; 1.0001; 1.0003)
1.067376
14678
(1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000)
1.105676
9 (n=10)
6027
(1.0000; 1.0001; 1.0000; 1.0000; 1.0003; 1.0000; 1.0000; 1.0000; 1.0000; 1.0001)
0.123788
31351
(1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000; 1.0000)
0.282408Table 4
The results obtained by the proposed algorithm for solving Problem9 with different dimensions.
No.
r
(
>
)
q
f-mean
f-best
f-std
Ratio (%)
9 (n=7)
1000
6028
7.5895
e
-
008
8.2743
e
-
008
0
100
9 (n=10)
1000
6027
0.0012
8.3180
e
-
007
0.0020
97.10
9 (n=12)
1.0
e
+
5
641.0518
1.5597
e
-
005
2.0935
e
-
010
1.1098
e
-
008
93.47
9 (n=15)
1.0
e
+
6
972.1050
2.4116
e
-
005
1.8709
e
-
013
1.0032
e
-
005
89.78
9 (n=20)
1.0
e
+
9
1321.3011
1.1602
e
-
004
8.2346
e
-
008
5.0653
e
-
006
85.57
9 (n=30)
1.0
e
+
9
2666.1220
0.3012
5.3080
e
-
005
3.0120
e
-
004
89.87The symbols used in Tables2, 3, and 4 are given as follows:No.: the number of the test problems;n: the dimension of the test problems;r: the parameter of the filled function;k: the iteration number;q: the total number of function and gradient evaluations of f(x) and P(x,xk*);xk*: the local minimizer of the objective function in the kth iteration;fk*: the function value at xk*;x*: the global minimizer of the objective function;times: the once running time (second);f-mean: the mean function value, respectively, in the 50 runs;f-best: the best function value, respectively, in the 50 runs;f-std: the standard deviation of function value, respectively, in the 50 runs;ratio: the ratio of the successful runs, that is, the ratio of the runs finding the true optimal solution in the 50 runs.It can be seen from Tables2, 3, and 4 that the proposed algorithm has the following advantages.(1) More Minimizers Are Obtained. In the proposed algorithm, the initial points are randomly and uniformly generated. This is helpful to get more different global minimizers in the 50 runs. For example, for Problems 2, 5, and 7, more optimal solutions are obtained by the proposed algorithm than those obtained by the algorithm in the literature [14].(2) More Effective and Efficient. The optimal solutions of all test problems can be found by the proposed algorithm. This indicates the effectiveness of the proposed algorithm. In addition, it can be seen from Table 3 that both the mean number of function evaluations q and the once running time obtained by the proposed algorithm are smaller than that obtained by the algorithm in [14]. This also indicates the efficiency of the proposed algorithm.(3) More Stability. It can be seen from column ratio in Table 2 that the ratio of the successful runs is more than 95.92%, and most of them are 100%, which shows that the proposed algorithm is stable. In addition, it can be seen from columns f-mean and f-std that difference between f-mean and f-best is small, and f-std is also small. This also indicates that the proposed algorithm is stable and robust to the initial points and parameter variation.(4) Applicable to Multidimensional Problems. In Table 4, Problem 9 with different dimensions is tested, and the numerical results indicate that the proposed algorithm is suitable for solving multidimensional problems.


## 6. Conclusions

The filled function method is an approach to find the global minima of multi-modal functions. The existing filled functions have some drawbacks such as being nondifferentiable at some point in search domain, including the exponential term, containing more than one adjustable parameter, and being discontinuous. In this paper, a filled function with one parameter is designed, which is continuously differentiable, and it can overcome the existing shortcomings. Based on this, a new filled function method with randomly and uniformly local search scheme is proposed, and the algorithm is numerically stable. The results of the computer simulations indicate that the proposed filled function method is effective and efficient.



---

*Source: 532325-2013-06-12.xml*