# A Novel Self-Adaptive Trust Region Algorithm for Unconstrained Optimization

Authors: Yunlong Lu; Wenyu Li; Mingyuan Cao; Yueting Yang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A new self-adaptive rule of trust region radius is introduced, which is given by a piecewise function on the ratio between the actual and predicted reductions of the objective function. A self-adaptive trust region method for unconstrained optimization problems is presented. The convergence properties of the method are established under reasonable assumptions. Preliminary numerical results show that the new method is significant and robust for solving unconstrained optimization problems.


---

## Body

## 1. Introduction

Consider the following unconstrained optimization problem:(1)min⁡x∈ℝnf(x),
where f:ℝn→ℝ is continuously differentiable.The trust region methods calculate a trial stepdk by solving the subproblem at each iteration,
(2)min⁡qk(d)=12dTBkd+gkTds.t.∥d∥≤Δk,
where gk=∇f(xk) and Bk is symmetric matric approximating the Hessian of f(x) at xk, and Δk>0 is the current trust region radius. Throughout this paper, ∥·∥ denotes the l2-norm. We define the ratio,
(3)rk=f(xk)-f(xk+dk)qk(0)-qk(dk),
and the numerator and the denominator are called the actual reduction and the predicted reduction, respectively. For basic trust region (BTR) method, if the sufficient reduction predicted by the model is realized by the objective function, the trial point xk+dk is accepted as the next iterate and the trust region is expanded or kept the same. If the model reduction turns out to be a poor predictor of the actual behavior of the objective function, the trial point is rejected and the trust region is contracted, with the hope that the model provides a better prediction in the smaller region. More formally, basic trust region radius update rule can be usually summarized as follows:
(4)Δk+1={[γ1Δk,γ2Δk]ifrk<η1,[γ2Δk,Δk]ifη1≤rk<η2,[Δk,∞)ifrk≥η2,
where the constants γ1,γ2,η1, and η2 satisfy
(5)0≤η1<η2<1,0<γ1≤γ2<1.The iteration is said to besuccessful if rk≥η1. If not, the iteration isunsuccessful, and the trial point is rejected. If rk≥η2, the iteration is said to bevery successful iteration [1]. If rk is significantly larger than one, that is, rk≥η3>1>η2, the iteration is calledtoo successful iteration [2].Sartenaer [3] developed an elaborate strategy which can automatically determine an initial trust region radius. The basic idea is to determine a maximal initial radius through many repeated trials in the steepest descent direction in order to guarantee a sufficient agreement between the model and the objective function. This strategy requires additional evaluations of the objective function. Zhang et al. [4] presented another strategy of determining the trust region radius. Their basic idea is originated from the following subproblem in an artificial neural network research [5]:
(6)min⁡d∈Rnqk(d)=gkTd+12dTBkds.t.-Δk≤di≤Δk,i=1,2,…,n,
where Δk=cp(∥gk∥/γ), 0<c<1,γ=min⁡(∥Bk∥,1), and p is a nonnegative integer. Therefore, instead of adjusting Δk, one adjusts p at each iteration. Motivated by this technique, they solved the trust region subproblem with
(7)Δk=cp∥gk∥∥B^k-1∥,
where c∈(0,1),p is a nonnegative integer, and B^k=Bk+iI is a positive definite matrix for some i. However, their method needs to estimate ∥Bk∥ or ∥B^-1∥ at each iteration, which leads to some additional cost of computation. As a result, Shi and Guo [6] proposed a simple adaptive trust region method. The new trust region model is more consistent with the objective function at the current iteration. Fu et al. [7] developed an adaptive trust region method based on the conic model by using the above adaptive strategy [4]. Sang and Sun [8] gave a new self-adaptive adjustment strategy to update the trust region radius, which makes full use of the information at the current point. Yu and Li [9] proposed a self-adaptive trust region algorithm for solving this nonsmooth equation. Some authors [1, 10] adopted different values for parameters (5) but seldom questioned the radius update formula (4). In addition, many adaptive nonmonotonic trust region methods have been proposed in [11–18]. Hei [19] proposed a self-adaptive update method, in which trust region radius is a product of a so-called R-function and Δk; that is, Δk+1=R(rk)Δk, where R(·) is the R-function. As the ratio rk is larger than one, R(·) is nondecreasing and bounded. However, as the iteration is very successful, the ratio rk is larger than one; it implies that the local approximation of the objective function by the model function is not good. Walmag and Delhez [2] suggested that it is not overconfident in the model qk(d) at too successful iterations. They presented a self-adaptive update method, in which trust region radius is Δk+1=Λ(rk)Δk, where Λ(·) is the Λ-function. If rk is significantly larger than one, Λ-function is nonincreasing. However, they took Λ(rk)>1 but close to one to match the convergence criteria presented by Conn et al. [1].In our opinion, the agreement between the model and the objective function is not good enough at too successful iterations. We take that the updated trust region radiusΔk+1 is less than Δk and Δk+1 is bounded lower away from zero. It implies that Λ(rk)>1 is not always necessary. This strategy can also match the convergence criteria presented by Conn et al. [1].In the paper, theL-function L(·) is introduced, which is a variant of Λ-function. A new self-adaptive trust region method is proposed, in which the trust region radius is Δk+1=L(rk)Δk. The new method is more efficient at too successful iterations.The rest of the paper is organized as follows. In Section2, we define L-function to introduce new update rules and a new self-adaptive trust region algorithm is presented. In Section 3, the convergence properties of proposed algorithm are investigated. In Section 4, numerical results are given. In Section 5 conclusions are summarized.


## 2.L-Function and the New Self-Adaptive Trust Region Algorithm

To obtain the new trust region radius update rules, we defineL-function L(t),t∈ℝ.Definition 1.
A functionL(t) is called an L-function if it satisfies the following:(1)
L(t) is nondecreasing in (-∞,η2] and nonincreasing in (2-η2,+∞), L(t)=β2, for t∈[η2,2-η2],(2)
lim⁡t→-∞L(t)=c1,(3)
L(0)=c2,(4)
lim⁡t→η2-L(t)=1,(5)
lim⁡t→0+L(t)=β1,(6)
L(t)<1, for t>η3,(7)
andlim⁡t→+∞L(t)=β3,
where the constantsβ1,β2,β3,η2,η3,c1,c2 are positive constants such that
(8)0<c1<c2<β1≤β3<1<β2,η3>2-η2.It is easy to prove that theL-function is a bounded function in ℝ. In the following, we show the differences between the usual empirical rule, the R-function rule, the Λ-function rule, and the L-function rule.The usual empirical rules ([1, 20, 21]) (Figure 1(a)) can be usually summarized as follows:
(9)Δk+1={β1Δk,ifrk<η1,Δk,ifη1≤rk<η2,β2Δk,ifη2≤rk,
where β1,β2,η1, and η2 are predefined constants such that
(10)0≤η1<η2<1,0<β1<1<β2.(a) Step function. (b)R-function R(rk). (c) Λ-function Λ(rk).
(a)
(b)
(c)TheR-function rule and the Λ-function rule can be described as follows:
(11)Δk+1=R(rk)Δk,Δk+1=Λ(rk)Δk,
where the R-function R(rk) (Figure 1(b)) proposed by Hei [19] is chosen as(12)R(rk)={2π(M-1-α1)arctan(rk-η1)+(1+α1),ifrk≥η1;(1-α2-β)exp⁡(rk-η1)+β1-α2-β,otherwise,where α1, α2, β, M, and η are constants, and the Λ-function Λ(rk) (Figure 1(c)) proposed by Walmag and Delhez [2] is chosen as
(13)Λ(rk)={β1,ifrk≤0,β1+(1-β1)(rkη1)2,if0<rk<η1,β3+(β2-β3)exp⁡⁡(-(rk-1η1-1)2),ifrk≥η1,
where β1,β2,β3, and η1 are constants.TheL-function rule can be described as follows:
(14)Δk+1=L(rk)Δk,
where the L-function L(rk) (Figure 2) is chosen as
(15)L(rk)={c1+(c2-c1)exp⁡(rk),ifrk≤0,1-β1exp⁡(η2)1-exp⁡(η2)-(1-β1)exp⁡(η2)1-exp⁡(η2)exp⁡((rk-η2)),if0<rk<η2,β2,ifη2≤rk≤2-η2,β3+(β2-β3)exp⁡(-(rk+η2-2η2-2)2),ifrk>2-η2,Figure 2
L-function L(t).whereβ1, β2, β3, c1, c2, and η2 are constants.TheL-function generalizes the R-function and the Λ-function. It contains some favorable features of the R-function [19] and the Λ-function [2].Now describe the new self-adaptive trust region algorithm with improved update rules.Algorithm 2.
One has the following.
Step
1. Given x0∈ℝn, B0∈ℝn×n, 0<η<η2<1,0<c1<c2<1,0<β1≤β3<1≤β2, and Δ0>0; ɛ≥0; set k:=0.
Step
2. If ∥gk∥≤ɛ or f(xk)-f(xk+1)≤ɛmax⁡{1,|f(xk)|}, stop. Otherwise solve subproblem (2) to get dk.
Step
3. Compute
(16)rk=f(xk)-f(xk+dk)qk(0)-qk(dk).
Computexk+1 as follows:
(17)xk+1={xk+dk,ifrk>η,xk,otherwise.
Update the trust region radius(18)Δk+1=L(rk)Δk,
where L(rk) is defined by (15).Step
4. Compute gk+1 and Bk+1; set k:=k+1; go to step 2.


## 3. Convergence of Algorithm2

In the section, we investigate the convergence properties of Algorithm2. Since it can be considered as a variant of the basic trust region method of Conn et al. [1], we expect similar results and significant similarities in their proofs under the following assumptions.Assumption 3.
Consider the following.(i)
The sequence{Bk} is uniformly bounded in norm; that is ∥Bk∥≤M, for some constant M.(ii)
The functionf is bounded on the level set S={x|f(x)≤f(x0)}.(iii)
The solutiondk of the subproblem (2) satisfies
(19)qk(0)-qk(dk)≥σ∥gk∥min⁡{Δk,∥gk∥∥Bk∥},whereσ∈(0,1].(iv)
The solutiondk of the subproblem (2) satisfies
(20)∥dk∥≤η¯Δk,for positive constantη¯≥1.Lemma 4.
Suppose that Assumption3 holds. Then
(21)|f(xk+dk)-q(dk)|≤12M∥dk∥2+C(∥dk∥)∥dk∥,
where C(∥dk∥) arbitrarily decreases with dk decreasing.Proof.
Since from Taylor theorem, we have that(22)f(xk+dk)=f(xk)+gkTdk+∫01‍[∇f(xk+tdk)-∇f(xk)]Tdkdt,
it follows from the definition of qk(d) in (2) that
(23)|f(xk+dk)-qk(dk)|=|12dkTBkdk-∫01‍[∇f(xk+tdk)-∇f(xk)]Tdkdt|≤12M∥dk∥2+C(∥dk∥)∥dk∥.By Algorithm2, we are capable of showing that the iteration must be very successful but not too successful if the trust region radius is sufficiently small enough and also that the trust region radius has to increase in this case. The following lemma’s proof is a bit different from the proof of Theorem 6.4.2in [1].Lemma 5.
Suppose that Assumption3 holds. If gk≠0 and there exists a constant Δ¯>0 such that
(24)Δk≤Δ¯,
then
(25)Δk+1≥Δk.Proof .
Using Assumption3 and gk≠0 and assuming that there is ɛ>0 such that ∥gk∥≥ɛ, we obtain that
(26)qk(0)-qk(dk)≥σ∥gk∥min⁡{Δk,gk∥Bk∥}≥σɛmin⁡(Δk,ɛM).
Combining (21) and (26), we have
(27)|rk-1|=|f(xk+dk)-q(dk)qk(0)-qk(dk)|≤(1/2)M∥dk∥2+C(∥dk∥)∥dk∥σɛmin⁡{Δk,ɛ/M}≤η¯Δk(Mη¯Δk+2C(∥dk∥))σɛmin⁡{Δk,ɛ/M}.
By (24), we can choose sufficient small Δ¯, such that
(28)Δk≤Δ¯≤ɛM,(29)Mη¯Δk+2C(∥dk∥)≤(1-η2)σɛη¯.
Using (27) and (28), we have |rk-1|≤1-η2; that is, η2≤rk≤2-η2. Since 2-η2≤η3, then η2≤rk≤η3. And so, by Algorithm 2, we have Δk+1≥Δk, where Δk falls below the threshold Δ¯.The proof of Lemma5 efficiently uses the conditions rk≤2-η2≤η3 to explain the case of too successful iteration, as distinguished from the proof of Theorem 6.4.2in [1].Theorem 6.
Suppose that Assumption3 holds. Let the sequence {xk} be generated by Algorithm 2. Then
(30)lim⁡k→∞inf⁡∥gk∥=0.Proof.
Assume, for the purpose of deriving a contradiction, that, for allk,
(31)∥gk∥≥ɛ.
Suppose that there is an infinite iteration subsequence such thatrk≥η2. Using Algorithm 2 and (21), we have
(32)f(xk)-f(xk+1)≥η2[qk(0)-qk(dk)]≥ση2∥gk∥min⁡{Δk,∥gk∥∥Bk∥}≥ση2ɛmin⁡{Δk,ɛβ},
where β=max⁡{1+∥Bk∥}. Since {f(xk)} is bounded below, then
(33)lim⁡k→∞Δk=0,
which contradicts (25). Hence (30) holds.In our strategy of the trust region radius’ adjustment, most of the iterations are indeed very successful but not too successful; the trust region constraint becomes irrelevant in the local subproblem. Therefore, superlinear convergence of trust region algorithm is preserved by the proposed self-adaptive radius update.


## 4. Numerical Experiments

In this section, we present preliminary numerical results to illustrate that the performance of Algorithm2, denoted by LATR, the basic trust region method in [1], denoted by BTR, and the parameters needed in (9) are chosen that β1=0.5,β2=2.0,η1=0.25, and η2=0.75; the adaptive trust region method in [19], denoted by RATR, and the parameters needed in (12) are chosen that α1=α2=0.01,β=0.1,M=5, and η1=0.25; and the adaptive trust region method in [2], denoted by ΛATR, and the parameters needed in (12) are chosen that β1=0.5,β2=2,β3=1.01, and η1=0.95. In Algorithm 2, η=0.01, β1=0.5, β2=2, β3=0.7, c1=0.12, c2=0.14, and η2=0.75. All tests are implemented by using MATLAB R2012a on a PC with CPU 2.67 GHz and 8.00 GB RAM. The first eleven problems are taken from [22]; others are from the CUTEr collection [15, 23]. The discrete Newton method is used to update the approximate Hessian matrix Bk. To stabilize the algorithms, the approximate Hessian matrix Bk can be chosen as follows:
(34)Bk=B¯k+min⁡{1,0.5∥∇f(xk)∥2}I,
where B¯k is obtained by forward difference formula at xk (see [20]) and I is an identity matrix.In all trust region algorithms in this paper, the trial stepdk is computed by CG-Steihaug algorithm in [20]. The iteration is terminated by the following condition:
(35)∥gk∥∞≤10-5,
except for problem Waston, which will exceed 500 iterations. For the problem, the stopping criterion is
(36)|f(xk+1)-f(xk)|≤10-5max⁡{1.0,|f(xk)|}.
In Table 1, we give the dimension (Dim) of each test problem, the number of function evaluations (nf), and the number of gradient evaluations (ng). In many cases, algorithm LATR is superior than algorithms BTR, RATR, and ΛATR, especially for solving problems (1), (7), (8), (13), (19), and (28), although the numbers of gradient evaluations are a bit more than others sometimes. Further result is shown by Figure 3, which is characterized by means of performance profile proposed in [24]. Consider the following performance profile function:
(37)ψs(τ)=1npsize{p:1≤p≤np,log⁡2(rp,s)≤τ},
where τ≥0 and
(38)rp,s=Np,smin⁡{Np,i:1≤i≤ns}
is the performance ratio of a solver s on a problem; np denotes the number of the tested problems, ns the number of the solvers, and Np,i the number of the function evaluations (or the CPU time, the number of gradient evaluations, number of iterations, etc.) required to solve the problem p by the solver i.Table 1
Numerical comparisons of BTR, RATR,ΛATR, and LATR.
Problem
Dim
BTR
RATR
ΛATR
LATR
nf
ng
nf
ng
nf
ng
nf
ng
(1) Trigonometric
200
214
17
205
10
—
—
78
9
(2) Extended Powell singular
200
28
20
26
20
32
21
30
24
(3) Schittkowski function 302
200
239
160
363
275
117
24
83
65
(4) Linear function full rank
200
23
4
21
4
15
3
11
7
(5) Watson
200
30
14
22
10
16
10
18
11
300
39
15
115
78
73
49
67
48
400
84
39
27
12
38
25
107
78
500
95
43
29
14
68
48
39
26
(6) Nearly separable
200
41
21
27
15
23
16
24
17
300
46
25
34
18
24
16
23
16
400
52
25
39
23
33
22
26
19
500
—
—
—
—
—
—
37
26
(7) Yang tridiagonal
200
67
40
61
44
99
32
51
41
300
151
113
72
57
105
38
74
61
400
133
93
141
106
151
68
109
90
500
148
97
120
95
257
149
109
90
(8) Allgower
200
40
23
53
38
57
2
83
69
300
18
1
17
1
24
1
7
1
400
25
15
17
3
56
2
21
17
500
20
3
17
3
52
3
9
2
(9) Linear function rank 1
200
101
42
62
27
285
30
39
24
300
102
40
66
25
300
30
35
16
400
110
45
69
25
319
32
39
20
500
108
42
70
25
317
31
47
32
(10) Linear function rank 1 with zero columns and rows
200
64
3
60
2
21
2
22
2
300
67
3
64
3
21
1
21
1
400
66
1
65
1
29
5
22
1
500
78
6
67
2
24
2
26
4
(11) Discrete integral equation
200
54
19
24
4
39
14
27
18
300
31
5
70
46
42
22
30
28
400
44
12
43
32
32
16
31
29
500
49
15
37
17
45
23
31
29
(12) CRAGGLVY
200
36
9
35
9
22
10
19
9
(13) GENHUMPS
200
26
0
26
0
74
0
9
0
(14) BROYDNBD
200
32
7
20
14
47
0
17
15
(15) PENALTY
200
71
33
69
33
59
33
59
37
300
75
35
74
35
63
38
59
35
400
74
33
76
35
64
36
61
37
500
77
35
80
37
58
36
62
38
(16) PENALTY2
200
46
8
42
8
88
9
25
11
300
149
72
159
129
78
50
150
116
400
434
208
—
—
—
—
465
390
500
—
—
330
228
—
—
—
—
(17) CHEBYQAD
200
75
55
79
70
39
7
83
67
300
28
12
83
70
41
6
89
70
400
95
63
99
85
108
64
104
82
500
32
16
37
22
119
52
103
83
(18) GENROSE
200
194
161
253
248
265
172
241
205
300
308
235
381
373
394
248
357
303
400
405
301
487
479
499
323
468
399
500
—
—
—
—
—
—
—
—
(19) INTEGREQ
200
15
1
14
1
214
0
6
1
300
15
1
14
1
206
0
6
1
400
15
1
14
1
203
0
6
1
500
15
1
14
1
201
0
6
1
(20) FLETCHCR
200
113
88
151
146
157
91
158
132
300
147
122
218
213
224
132
233
195
400
183
157
292
284
295
175
309
258
500
217
190
357
351
362
211
384
321
(21) ARGLINB
200
6
5
6
5
6
5
6
5
300
7
6
7
6
7
6
7
6
400
7
6
7
6
300
5
7
6
500
7
6
7
6
424
5
7
6
(22) NONDIA
200
7
6
7
6
93
6
7
6
300
7
6
7
6
7
6
7
6
400
6
5
6
5
6
5
6
5
500
6
5
6
5
6
5
6
5
(23) EG2
200
14
9
11
9
59
23
10
8
300
14
9
12
9
60
27
6
5
400
9
7
7
6
180
30
8
6
500
12
5
17
13
111
34
14
11
(24) CURLY20
200
13
11
19
17
16
14
11
10
300
13
11
21
18
17
15
13
12
400
10
9
11
11
11
10
9
9
500
10
9
11
11
11
10
9
9
(25) CUBE
200
52
20
39
25
95
16
37
29
300
50
16
77
65
98
20
40
32
400
52
16
45
31
83
16
35
28
500
52
16
52
38
128
14
35
28
(26) EXPLIN1
200
30
2
28
2
12
3
13
4
300
29
1
28
1
33
4
13
4
400
31
2
29
2
23
4
21
16
500
32
2
30
2
15
3
13
4
(27) SINQUAD
200
68
55
18
17
119
14
19
17
300
186
175
16
15
225
20
64
60
400
25
12
21
19
224
25
48
45
500
31
15
43
41
229
40
35
33
(28) LIARWHD
200
29
1
28
1
50
2
14
4
300
32
2
29
2
18
2
12
2
400
30
1
30
1
30
2
12
1
500
30
1
30
1
33
2
11
1
— means that the algorithm reaches 500 iterations.Figure 3
Performance profile comparing the sum of the number of function and gradient evaluations.From Table1, we know that ns=4 and np=91; then performance profile is given on the sum of the number of function and gradient evaluations to solve the problem. As we can see on Figure 3, the new self-adaptive algorithm is superior to the other three algorithms.


## 5. Conclusion

This paper presents a new self-adaptive trust region algorithm according to the new self-adaptive radius update rule. As the iteration istoo successful, we suggest reducing the trust region radius with the new rules. The convergence properties of the method are established under reasonable assumptions. Numerical experiments show that the new algorithm for solving unconstrained optimization problems is significant and robust.For future research, we should investigate how to select an appropriateL-function to conduct numerical experiments.



---

*Source: 610612-2014-04-15.xml*