# Modified T-F Function Method for Finding Global Minimizer on Unconstrained Optimization

Authors: Youlin Shang; Weixiang Wang; Liansheng Zhang
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

This paper indicates that the filled function which appeared in one of the papers by Y. L. Shang et al. (2007) is also a tunneling function; that is, we prove that
under some general assumptions this function has the characters of both tunneling
function and filled function. A solution algorithm based on this T-F function is given
and numerical tests from test functions show that our T-F function method is very
effective in finding better minima.


---

## Body

## 1. Introduction

Because of the advances in science, economics, and engineering, studies on global optimization for the multiminimum nonlinear programming problem have become a topic of great concern. The existence of multiple local minima of a general nonconvex objective function makes global optimization a great challenge [1–3].  Many deterministic methods using an auxiliary function have been proposed to search for a globally optimal solution of a given function of several variables, including filled function method [4] and tunneling method [5].The filled function method was first introduced by Ge in the paper in [4]. The key idea of the filled function method is to leave from a local minimizer x1* to a better minimizer of f(x) with the auxiliary function P(x) constructed at the local minimizer x1* of f(x). Geometrically, P(x) flattens in the higher basin of f(x) than B1*. So a local minimizer x¯ of P(x) can be found, which lies in the lower basin of f(x) than B1*. To minimize f(x) with initial point x¯, one can find a lower minimizer x2* of f(x). with x2* replacing x1*, one can construct a new filled function and then find a much lower minimizer of f(x) in the same way. Repeating the above process, one can finally find the global minimizer xg* of f(x).The basin off(x) at an isolated minimizer of f(x), x*, is defined in the paper in [4] as a connected domain B* which contains x* and in which the steepest descent trajectory of f(x) converges to x* from any initial point. The hill of f(x) at x1* is the basin of -f(x) at its isolated minimizer x1*.The concept of the filled function is introduced in the paper in [4]. Assume that x* is a local minimizer of f(x). A function P(x) is called a filled function of f(x) at x* if P(x) has the following properties.(P1)
x* is a maximizer of P(x) and the whole basin B* of f(x) at x* becomes a part of a hill of P(x).(P2)
P(x) has no minimizers or saddle points in any higher basin of f(x) than B*.(P3)
iff(x) has a lower basin than B*, then there is a point x' in such a basin that minimizes P(x) on the line through x and x*.The form of the filled function proposed in paper [4] is as follows: (1.1)P(x,x*,r,q)=1r+f(x)exp(-∥x-x*∥2q2),
where r and q are two adjustable parameters.However, this function still has some unexpected features.First, this function has only a finite number of local minimizers.Second, the efficiency of the algorithm strongly depends on two parameters:r and q. They are not so easy to be adjusted to make them satisfy the needed conditions.Thirdly, when the domain is large orq is small, the factor exp(-∥x-x*∥/q2) will be approximately zero; that is, when the domain is large, this function will become very flat. This makes the efficiency of the algorithm decrease.The tunneling function method was first introduced by Levy and Montalvo in the paper in [5]. The definition of the tunneling function in the paper in [5] is as follows.Letx* be a current minimizer of f(x). A function P(x,x*) is called a tunneling function of f(x) at a local minimizer x* if, for any x0∈Rn, P(x0,x*)=0 if and only if f(x0)-f(x*)=0.Although some other filled functions were proposed later [6–9], they are not satisfactory for global optimization problem, all of them have the same disadvantages mentioned above. Paper [10] proposes a new definition of the filled function and gives a new filled function form which overcomes these disadvantages.This paper is organized as follows. In Section2, some assumptions and some new definitions are proposed; the definition of the filled function given in this paper is different from the paper in [4]. A T-F function satisfying the new definition of the T-F function is given in Section 3. This function has the properties of both the filled function and the tunneling function. Next, in Section 4, a T-F function algorithm is presented. A global minimum of an unconstrained optimization problem can be obtained by using these methods. The results of numerical experiments for testing functions are reported in Section 5. Finally, conclusions are included in Section 6.


## 2. Some Assumptions and Some Definitions

Consider the following unconstrained global optimization problem:(2.1)(P)*:minf(x),subjecttox∈Rn.
Throughout this paper, similar to the paper in [10], we assume that the following conditions are satisfied.Assumption.
f(x) is Lipschitz continuously differentiable on Rn; that is, there exists a constant L>0 such that |f(x)-f(y)|≤L∥x-y∥ holds for all x,y∈Rn.Assumption.
f(x) is a coercive function, that is, f(x)→+∞ as ∥x∥→+∞.Notice that Assumption2.2 implies that there exists a bounded and closed set Ω⊂Rn whose interior contains all minimizers of f(x). One assumes that the value of f(x) for x on the boundary of Ω is greater than the value of f(x) for any x inside Ω. Then the original problem (P)* is equivalent to the following problem:
(2.2)(P):minf(x),subjecttox∈Ω.Assumption.
The setF={f(x*)∣x*∈L(P)} is finite, where L(P) is the set of all minimizers of problem (P).Note that Assumption2.3 only requires that the number of local minimal values of problem (2.2) be finite. The number of local minimizers can be infinite.To overcome the disadvantages mentioned in Section1, a new definition of the filled function was proposed in the paper in [10] in the following. Throughout this paper, we let x* be the current local minimizer of f(x).Definition 2.4 (see [10]).
P(x,x*) is called a filled function of f(x) at a local minimizer x* if P(x,x*) has the following properties.(i)
x* is a local maximizer of P(x,x*).(ii)
Iff(x)≥f(x*) and x≠x*, then ∇P(x,x*)≠θ.(iii)
If there is a local minimizerx1* of f(x) satisfying f(x1*)<f(x*), then P(x,x*) does have a minimizer x¯1*∈B(x1*,δ) and f(x¯1*)<f(x*).
These properties of this filled function ensure that, when a descent method, for example, a quasi-Newton method, is employed to minimize the constructed filled function, the sequence of iteration point will not terminate at any point in which the value off(x) is larger than f(x*) and that, when there exist basins of f(x) lower than B*, there exists a minimizer of the filled function such that the value of f(x) at this point is less than f(x*); that is, any local minimizer of P(x,x*) belongs to the set S={x∈Rn:f(x)<f(x*)}. Consequently, we can obtain the better local minimizer of f(x) starting from any point in the S.
We give a modified definition of the tunneling function off(x) as follows.Definition 2.5.
P(x,x*) is called a tunneling function of f(x) at a local minimizer x* if, for any x0∈Rn with r>0, P(x0,x*)=0 if and only if f(x0)-f(x*)+r≤0.
The properties of this new tunneling function ensure that a function must satisfy [5, Definition 1.2] when it satisfies Definition 2.5,  so it is a modified tunneling function. Consequently, we can obtain the better local minimizer of f(x) by using the tunneling function method given in the paper in [5].
We give a modified definition of the T-F function off(x) as follows.Definition 2.6.
P(x,x*) is called a modified T-F function of f(x) at a local minimizer x* if it is both a tunneling function and a filled function; that is, it satisfies Definitions 2.4 and 2.5 at the same time.


## 3. Modified T-F Function and Its Properties

We propose an auxiliary function off(x) for problem (P) as follows: (3.1)P(x,x*,r,q)=ln(1+q|f(x)-f(x*)+r|)1+q∥x-x*∥,
where r>0 and q>0 are two parameters and r satisfies (3.2)0<r<minx1*∈L(P)(f(x*)-f(x1*)),f(x1*)<f(x*).The following Theorems,3.2–3.6, already show that P(x,x*,r,q) is a filled function of f(x) satisfying Definition 2.4 under some conditions in the paper in [10]. Theorem 3.1 also proves that this function satisfies Definition 2.5; that is, this function is a modified T-F function.Theorem 3.1.
Letx* be the current local minimizer of f(x). Then, for any x0∈Rn with q,r>0, P(x0,x*,r,q)=0 if and only if f(x0)-f(x*)+r≤0; that is, P(x,x*,r,q) is a modified tunneling function of f(x).Proof.
For anyx0∈Rn with r>0,
(3.3)P(x0,x*,r,q)=ln(1+q|f(x0)-f(x*)+r|)1+q∥x0-x*∥=0,
if and only if
(3.4)ln(1+q|f(x0)-f(x*)+r|)=0,
if and only if
(3.5)f(x0)-f(x*)+r=0.
Hence P(x,x*,r,q) is a modified tunneling function of f(x).Theorem 3.2 (see [10]).
x* is a strictly local maximizer of P(x,x*,r,q) when q is sufficiently large and r satisfies formula (3.2).Proof.
Onehasthat(3.6)P(x,x*,r,q)=ln(1+q|f(x)-f(x*)+r|)1+q∥x-x*∥≤ln(1+q(L∥x-x*∥+r))1+q∥x-x*∥,P(x*,x*,r,q)=ln(1+qr).
Let F(x)=ln(1+q(L∥x-x*∥+r)) and x≠x*.
It follows from the mean value theorem that(3.7)F(x)=F(x*)+∇FT(x*+λ(x-x*))(x-x*),x∈B(x*,σ),σ>0,λ∈(0,1).
that is,
(3.8)ln(1+q(L∥x-x*∥+r))=ln(1+qr)+qL(x-x*)T(x-x*)(1+q(Lλ∥x-x*∥+r))∥x-x*∥,ln(1+q(L∥x-x*∥+r))1+q∥x-x*∥=ln(1+qr)1+q∥x-x*∥+qL∥x-x*∥(1+q∥x-x*∥)(1+q(Lλ∥x-x*∥+r))≤ln(1+qr)1+q∥x-x*∥+qL∥x-x*∥(1+q∥x-x*∥)(1+qr).
When q is sufficiently large, we have
(3.9)-(1+qr)ln(1+qr)+L<0.
That is,
(3.10)-ln(1+qr)+L1+qr<0.
It follows from (3.10) that
(3.11)ln(1+qr)(11+q∥x-x*∥-1)+qL∥x-x*∥(1+q∥x-x*∥)(1+qr)=ln(1+qr)(-q∥x-x*∥1+q∥x-x*∥)+qL∥x-x*∥(1+q∥x-x*∥)(1+qr)=q∥x-x*∥1+q∥x-x*∥(-ln(1+qr)+L1+qr)<0.
That is,
(3.12)ln(1+qr)1+q∥x-x*∥+qL∥x-x*∥(1+q∥x-x*∥)(1+qr)<ln(1+qr).
Therefore, P(x*,x*,r,q)>P(x,x*,r,q) holds for all x∈B(x*,σ) and x≠x*. Hence x* is a strictly local maximizer of P(x,x*,r,q).Theorem 3.3 (see [10]).
Ifx≠x* and satisfies condition f(x)≥f(x*), when r>0 and q>0 satisfy the following inequality:
(3.13)(1+qW0)∇f0-(1+qr)ln(1+qr)<0,
Then one has  ∇P(x,x*,r,q)≠θ, where W0=maxx∈Ω∥x-x*∥ and ∇f0=maxx∈Ω∥∇f(x)∥.Proof.
Sincef(x)≥f(x*), we have
(3.14)P(x,x*,r,q)=ln(1+q(f(x)-f(x*)+r))1+q∥x-x*∥,∇P(x,x*,r,q)T·x-x*∥x-x*∥=q(1+q∥x-x*∥)2(1+q(f(x)-f(x*)+r))·{(1+q∥x-x*∥)∇f(x)Tx-x*∥x-x*∥-(1+q(f(x)-f(x*)+r))ln(1+q(f(x)-f(x*)+r))x-x*∥x-x*∥}≤q(1+q∥x-x*∥)2(1+q(f(x)-f(x*)+r))·{(1+qW0)∇f0-(1+qr)ln(1+qr)}.
It follows from (3.13) that
(3.15)∇P(x,x*,r,q)T·x-x*∥x-x*∥<0.
Therefore
(3.16)∇P(x,x*,r,q)≠θ.Theorem 3.4.
If there is a local minimizerx1* of f(x) satisfying f(x1*)<f(x*), then P(x,x*) does have a minimizer x¯1*∈B(x1*,δ) and f(x¯1*)<f(x*).Theorems3.2, 3.3, and 3.4 show that under some assumptions the function (3.1) is a filled function satisfying Definition 2.4. The following two theorems further show that the function (3.1) has some properties which classical filled function have.Theorem 3.5.
Suppose thatx1,x2∈Ω and satisfy ∥x1-x*∥>∥x2-x*∥>0, f(x1)≥f(x*), and f(x2)≥f(x*). If q is sufficiently large, then one has P(x1,x*,r,q)<P(x2,x*,r,q).Theorem 3.6.
Suppose thatx1,x2∈Ω and satisfy ∥x1-x*∥>∥x2-x*∥>0. If f(x2)≥f(x*)>f(x1) and f(x1)-f(x*)+r>0, then one has P(x1,x*,r,q)<P(x2,x*,r,q).


## 4. New T-F Function Algorithm

The theoretical properties of the modified T-F functionP(x,x*,r,q) discussed in the foregoing sections give us a new approach for finding a global minimizer of f(x). Similar to the paper in [10], we present a new T-F function algorithm in the following.(1) Initial Step
Chooseɛ>0 and r>0 as the tolerance parameters for terminating the minimization process of problem (2.2).Chooseq>0 and M>0 and δ, a very small positive number.Choose directionei,i=1,2,…,k, and integer k0>2n, where n is the number of variable.Choose an initial pointx10∈Ω.(2) Main Step
(10) Obtain a local minimizer of the prime problem by implementing a local downhill search procedure starting from the xk0. Let xk* be the local minimizer obtained. Let i=1 and k=1.(20) If i>k0, then stop, xk* is a global minimizer; otherwise, let x¯k*=xk*+δei (where δ is a very small positive number). If f(x¯k*)<f(xk*), then let k=k+1, xk0=x¯k*, and go to (10); otherwise, go to (30).(30) Let
(4.1)P(y,xk*,r,q)=ln(1+q|f(x)-f(xk*)+r|)1+q∥x-xk*∥,
and y0=x¯k*. Turn to Inner Loop.(3) Inner Loop
(10) One has ym+1=φ(ym), where φ is an iteration function. It denotes a local downhill search method from the initial point y0 with respect to P(y,xk*,r,q).(20) If ∥ym+1-x10∥≥M, then let i=i+1 and go to Main Step (20).(30) If f(ym+1)≤f(xk*), then let k=k+1, xk0=ym+1 and go to Main Step (10); otherwise, let m=m+1 and go to Inner Loop (10).


## 5. Numerical Results

### 5.1. Testing Functions

(i)
The 6-hump back camel function [6, 7, 10] is given as(5.1)f(x)=2x12-2.1x14+13x16-x1x2-4x22+4x24,-3≤x1,x2≤3.
The global minimum solutions are x*=(0.0898,0.7127) or (-0.0898,-0.7127) and f*=-1.0316.(ii)
The Goldstein and Price function [6, 10] is given as(5.2)f(x)=[1+(x1+x2+1)2(19-14x1+3x12-14x2+6x1x2+3x22)]×[30+(2x1-3x2)2(18-32x1+12x12+48x2-36x1x2+27x22)],-3≤x1,x2≤3.
The global minimum solution are x*=(0.0000,-1.0000) and f*=3.0000.(iii)
The Treccani function [9, 10] is ginen as(5.3)f(x)=x14+4x13+4x12+x22,-3≤x1,x2≤3.
The global minimum solutions are x*=(0.0000,0.0000) or (-2.0000,0.0000) and f*=0.0000.(iv)
The Rastrigin function [8, 10] is given as(5.4)f(x)=x12+x22-cos(18x1)-cos(18x2),-1≤x1,x2≤1.
The global minimum solutions are x*=(0.0000,0.0000) and f*=-2.0000.(v)
The 2-dimensional function in [8, 10] is given as
(5.5)f(x)=[1-2x2+csin(4πx2)-x1]2+[x2-0.5sin(2πx1)]2,-10≤x1,x2≤10,
where c= 0.2, 0.5, 0.05. The global minimum solution: f*=0.0000 for all c.(vi)
The 2-dimensional Shubert function III [8] is given as(5.6)f(x)={∑i=15icos[(i+1)x1+1]}{∑i=15icos[(i+1)x2+1]},-10≤x1,x2≤10.
The global minimum solutions are x*=(-1.4252,-0.8003) and f*=-186.7309.(vii)
The n-dimensional Sine-square function I [10] is given as(5.7)f(x)=πn{10sin2(πx1)+∑i=1n-1[(xi-1)2(1+10sin2)(πxi+1)]+(xn-1)2},-10≤xi≤10,i=1,2,…,n.The function is tested forn = 2,6,10. The global minimum solution is uniformly expressed as: x*=(1.0000,1.0000,…,1.0000) and f*=0.0000.


### 5.2. Computational Results and a Comparison with Other Papers

In the following, computational results of the test problems using the algorithms in the papers in [5, 10] and this paper, respectively, are summarized in Tables 1 and 2 for each function. The symbols used are described as follows:PROB: The number of the test problems;DIM: the dimension of the test problems;N: The number of evaluations of the functions when T-F function algorithm terminated;N5: The number of evaluations of the functions when the algorithm in the paper in [5] terminated;N10: The number of evaluations of the functions when the algorithm in the paper in [10] terminated;x0: the initial point in our program;T: the CPU time in seconds to obtain the final result using the algorithm in this paper;T5: the CPU time in seconds to obtain the final result using the algorithm in the paper in [5];T10: the CPU time in seconds to obtain the final result using the algorithm in the paper in [10].Table 1
Comparison of the evaluation times of the functions.
PROBDIMNN5N10(i)2263296279(ii)2475698559(iii)2564569488(iv)217582107(v)2161117161526(vi)2191426472280(vii)241244152(vii)6901789369598(vii)101375216283Table 2
Comparison of theCPU times of the algorithms.
PROBx0TT5T10(i)(−2.00,1.00)131015111408(ii)(0.50,0.50)187619061820(iii)(2.00,−1.00)9029981156(iv)(0.80,0.80)411051374585(v)(3.00,3.00)161117161578(vi)(1.00,1.00)396448404160Although the total number of evaluations of the objective function depends on a variety of factors such as the initial point, the termination criterion, and the accuracy required, in dealing with unconstrained global optimization problems, our T-F function algorithm seems as effective and reliable as those of algorithms in the papers in [5, 10]. However, our T-F function algorithm can be used in Rn unconstrained global optimization, so it has more wide applications.


## 5.1. Testing Functions

(i)
The 6-hump back camel function [6, 7, 10] is given as(5.1)f(x)=2x12-2.1x14+13x16-x1x2-4x22+4x24,-3≤x1,x2≤3.
The global minimum solutions are x*=(0.0898,0.7127) or (-0.0898,-0.7127) and f*=-1.0316.(ii)
The Goldstein and Price function [6, 10] is given as(5.2)f(x)=[1+(x1+x2+1)2(19-14x1+3x12-14x2+6x1x2+3x22)]×[30+(2x1-3x2)2(18-32x1+12x12+48x2-36x1x2+27x22)],-3≤x1,x2≤3.
The global minimum solution are x*=(0.0000,-1.0000) and f*=3.0000.(iii)
The Treccani function [9, 10] is ginen as(5.3)f(x)=x14+4x13+4x12+x22,-3≤x1,x2≤3.
The global minimum solutions are x*=(0.0000,0.0000) or (-2.0000,0.0000) and f*=0.0000.(iv)
The Rastrigin function [8, 10] is given as(5.4)f(x)=x12+x22-cos(18x1)-cos(18x2),-1≤x1,x2≤1.
The global minimum solutions are x*=(0.0000,0.0000) and f*=-2.0000.(v)
The 2-dimensional function in [8, 10] is given as
(5.5)f(x)=[1-2x2+csin(4πx2)-x1]2+[x2-0.5sin(2πx1)]2,-10≤x1,x2≤10,
where c= 0.2, 0.5, 0.05. The global minimum solution: f*=0.0000 for all c.(vi)
The 2-dimensional Shubert function III [8] is given as(5.6)f(x)={∑i=15icos[(i+1)x1+1]}{∑i=15icos[(i+1)x2+1]},-10≤x1,x2≤10.
The global minimum solutions are x*=(-1.4252,-0.8003) and f*=-186.7309.(vii)
The n-dimensional Sine-square function I [10] is given as(5.7)f(x)=πn{10sin2(πx1)+∑i=1n-1[(xi-1)2(1+10sin2)(πxi+1)]+(xn-1)2},-10≤xi≤10,i=1,2,…,n.The function is tested forn = 2,6,10. The global minimum solution is uniformly expressed as: x*=(1.0000,1.0000,…,1.0000) and f*=0.0000.


## 5.2. Computational Results and a Comparison with Other Papers

In the following, computational results of the test problems using the algorithms in the papers in [5, 10] and this paper, respectively, are summarized in Tables 1 and 2 for each function. The symbols used are described as follows:PROB: The number of the test problems;DIM: the dimension of the test problems;N: The number of evaluations of the functions when T-F function algorithm terminated;N5: The number of evaluations of the functions when the algorithm in the paper in [5] terminated;N10: The number of evaluations of the functions when the algorithm in the paper in [10] terminated;x0: the initial point in our program;T: the CPU time in seconds to obtain the final result using the algorithm in this paper;T5: the CPU time in seconds to obtain the final result using the algorithm in the paper in [5];T10: the CPU time in seconds to obtain the final result using the algorithm in the paper in [10].Table 1
Comparison of the evaluation times of the functions.
PROBDIMNN5N10(i)2263296279(ii)2475698559(iii)2564569488(iv)217582107(v)2161117161526(vi)2191426472280(vii)241244152(vii)6901789369598(vii)101375216283Table 2
Comparison of theCPU times of the algorithms.
PROBx0TT5T10(i)(−2.00,1.00)131015111408(ii)(0.50,0.50)187619061820(iii)(2.00,−1.00)9029981156(iv)(0.80,0.80)411051374585(v)(3.00,3.00)161117161578(vi)(1.00,1.00)396448404160Although the total number of evaluations of the objective function depends on a variety of factors such as the initial point, the termination criterion, and the accuracy required, in dealing with unconstrained global optimization problems, our T-F function algorithm seems as effective and reliable as those of algorithms in the papers in [5, 10]. However, our T-F function algorithm can be used in Rn unconstrained global optimization, so it has more wide applications.


## 6. Conclusions

This paper proves that the filled function which appeared in the paper in [10] is also a tunneling function; that is, under some general assumptions, this paper indicates that the function which appeared in the paper in [10] has the characters of both the tunneling function and the filled function. A solution algorithm based on this T-F function is given and numerical tests from test functions show that our T-F function method is very effective in finding better minima on unconstrained global optimization problems.



---

*Source: 602831-2010-09-20.xml*