A Journal of Software Engineering and Applications, 2013, 6, 49-52
doi:10.4236/jsea.2013.65B010 Published Online May 2013 (http://www.scirp.org/journal/jsea) 49
An Improved Line Search and Trust Region Algorithm
Qinghua Zhou, Yarui Zhang, Xiaoli Zhang
College of Mathematics & Computer Science, Hebei University, Baoding, 071002, China.
Received 2013
ABSTRACT
In this paper, we present a new line search and trust region algorithm for unconstrained optimization problems. The
trust region center locates at somewhere in the negative gradient direction with the current best iterative point being on
the boundary. By doing these, the trust region subproblems are constructed at a new way different with the traditional
ones. Then, we test the efficiency of the new line search and trust region algorithm on some standard benchmarking.
The computational results reveal that, for most test problems, the number of function and gradient calculations are re-
duced significantly.
Keywords: Trust Region Algorithms; Trust Region Subproblem; Line Search; Unconstrained Optimization
1. Introduction
Trust region algorithm is one of the most often used meth-
ods for solving the unconstrained optimization pro blem


min .
n
xR
f
x
 (1)
Generally, a trial step is calculated by solving the tru st
region subproblem

1
min 2
.. ,
n
TT
kkk
dR
k
g
ddBd d
st d



(2)
Where k

k
g
fx is the gradient at the current ap-
proximate solution, k is a symmetric matrix
which approximates the Hessian of
Bnn
f
at k
x
, k

is
the current trust region radius and here  refers to the
2-norm.
Trust region algorithms are blessed with both strong
theoretical convergence properties and effectiveness in
practice[1-4]. It has been studied by many researchers.
The traditional trust region is normally an area centered
at the current iterate k
x
as indicated in model (2). In
2003, based on the traditional trust region algorithm, Ma
[5] proposed a new trust region algorithm, whose trust
region radius is kk
g
 and whose trust region center is
.
kkk
x
g After carefully studying the idea of traditional
trust region algorithms and Ma [5], Zhou et al [6] also
proposed an improved trust region based on an algorithm
depicted in [7].
The improved trust region is a ball centered at the
point kkkk
x
gg and whose radius is In this paper, .
k

we present another new trust region algorithm, which is
based on the idea of Zhou et al [6] and to investigate the
performance of the algorithms with different trust region
subproblems.
Our aim is to improve the algorithm proposed in [6,7]
and to make it more effective in practical implementation.
The main difference between the algorithm in [7] and our
algorithm is that in the former one the trust region sub-
problem has the model like equation (2), while in our
algorithm the trust region subproblem is reconstructed at
different trust region center and radius.
The paper is organized as follows. In Section 2, we
describe our algorithm for unconstrained optimization
problems which combines the new trust region and line
search algorithm. In Section 3, primary numerical results
are presented. Finally a short discussion about conclusion
and future works is given in section 4.
2. The New Line Search and Trust Region
Algorithm
2.1. Traditional Line Search and Trust Region
Algorithm
In this subsection, we consider the line search and trust
region method for the unconstrained optimization prob-
lem

min ,
n
xR
f
x

where


,
f
x the objective function, is a real-valued
continuously differentiable function. Its solution is ap-
proximated by iteratively solving the subproblem (2).

An Improved Line Search and Trust Region Algorithm
50
Let k be the solution of (2). Th e predicted redu ction
is defined by the reduction of the approximate model,
that is,
d
 
0,
kk kk
pred d  
and the actual reduction is defined by the reduction of the
objective function, that is,
 
.
kk k
aredf xf xd
k
The ratio between the two reductions is defined by
.
k
kk
ared
pred
  (3)
It is well known that the ratio plays a key role in the
traditional trust region algorithm to determine whether
the trial step is acceptable or not and to adjust the new
trust region radius. If the trial step is not successful, we
will reject it, reduce the trust region radius and resolve
the subproblem (2); otherwise, we will accept the trial
step and enlarge the trust region radius.
The next iterate 1k
x
 is determined by the following
formula:
0
1
,
,
kk k
kk
x
dif c
x
x
otherwise






where is a small constant.


00,1c
The trust region radius for the next iteration is chosen
by the following formula:

34
1
1
,
, ,
kk k
k
kk
cd cifc
cotherwis









2
,
e

3
where are positive constants that satisfy

1, 2,3,4
i
ci
cc
14
1c and .

20
,1cc
Next we describe the traditional line search and trust
region algorithm.
Algorithm 1
Step 1 given 1n
x
R and 10


34
cc, choose constants
12 and that satisfy 3
,,ccc 4 c1 01c,
2
0c1;


set . :k1
Step 2 solve (2) inaccurately so that k d
k
, and so
that the model has sufficient reduction.
Step 3 compute

kk
f
xd. If



,
kk k
f
xd fx
go to Step 4; else find the minimum positive integer
such that k
i



;
k
i
kk k
f
xd fx

,
k
i
xxd
compute
1kk
k


11 4
,;
kkkk
xxc

 
go to Step 5.
Step 4 set
 
 
1,
.
0
kkk
kk
kkkk
xxd
If 2kc

 and k dk

, set , else define
1k

k

34 2
1
12
,,
,.
kk k
k
kk kk
cd cifc
cifcandd







k




Step 5 compute 1k
g

and ; set ; go to
Step 2. 1k
B: 1kk
2.2. New Algorithm
In this subsection, we describe the algorithm which co m-
bines the new trust region and line search. Throughout
this paper, we use

to represent the Euclid norm and
denote


k
g
x by k
g
,


k
Bx by k, etc. Vectors are
all column vectors unless a transpose is used.
B
In the traditional trust region, the trust region sub-
problem is (2). In Zhou et al [6], the trust region sub-
problem is as follows.

1
min 2
.. ,
n
TT
kk
dR
kkk
k
g
ddBd d
st dg
g




(4)
where d is the trial step, kkkk
x
gg is the center,
k

is the radius of the trust region.
After studying [6], we have test some other radii, such
as 0.5k

, 0.75 k

and 1.5k

. By doing this, we want to
examine the effect by choosing different trust region ra-
dius at the negative gradient direction. In the numerical
results, we find that the numerical result with parameter
1.5 k

is better than that with and 0.0.5 k 75 k

. So
we select 1.5 k

as the new trust region radius.
Then we give the trust region subprobl em as follows.

1
min 2
1.5
..1.5 ,
n
TT
kkk
dR
kkk
k
g
ddBd d
st dg
g





(5)
where d is the trial step, 1.5
kkkk
x
gg is the cen -
ter, 1.5 k

is the trust region radius. If we let
~2
3kk
k
dd g
g

 ,
then (5) converts to
~
~~ ~~
'
~
1
min 2
.. ,
n
T
T
kk
dR
k
hd dBdd
st d







(6)
k
f
xfxd
d




where 2.
3kkk
kk k
Bg
hg g


At iterations of traditional line search and trust region

An Improved Line Search and Trust Region Algorithm 51
algorithm, a trial step k is generated by solving the
trust region subproblem (2). While in each iteration of
our line search and trust region algorithm, the trial step
k is generated by solving the trust region subproblem
(5) or (6). As in [10], we solve (6) inaccurately subject to
d
d
~
kk
d , then ~
3.
2kk
kk
g
dd
g






Let satisfies
k
d
  
0min,
kkk kkkk
dg gB    , (7)
and


min ,,
T
kkkk kk
dggg B    (8)
where is a constant.

0, 1  
We name our line search and trust region algorithm as
"L-NTR1" for convenience .
For completeness, we describe our improved line
search and trust region algorithm. It is analogous with
Algorithm 1.
Algorithm 2
Step 1 given 1n
x
R and 10


34
cc, choose constants
12 and that satisfy 3
,,ccc 4 c1 01c,
2
0c1;


set . :1k
Step 2 solve (6) inaccurately so that ~
kk
d

, let
~
3.
2kk
kk
g
dd
g








So that (7) and (8) are satisfied.
Step 3 compute

kk
f
xd. If



,
kkk
f
xd fxk
i
go to Step 4; else find the minimum positive integer
such that



k
i
kk

;
k
f
xd
xx
fx

,
k
i
d
compute
1 kk k 


,;xxc 
114kkkk
k

go to Step 5.
Step 4 compute 1kk
x
xd
, and





0
kk
kkkk
k
f
xfxd
d


.
If 2kc

 and k d
kk
, set , else define
1k


34 2
1
12
,,
,.
kk k
k
kk kk
cd cifc
cifcandd







 

k
Step 5 compute 1k
g
 and set go to
Step 2. 1;
k
B:kk1;
3. Numerical Results
In this section, we implement our new line search and
trust region algorithm and compare it both with the tradi-
tional line search and trust region algorithm (L-TTR) and
the improved on e (L-NTR) which is proposed in our ear-
lier work [6].
The test problems are those given by Moré, Garbow
and Hillstrom [8], and we use the same numbering sys-
tem as that in [8]. In all the tests, the trial step is calcu-
lated approximately by the algorithm given by Nocedal
& Yuan in [9]. The algorithm is terminated when the norm
of the gradient k
g
is less than , or when the
8
10 


number of calculations exceeds 30000. Next we give the
results of compared different trust region radii in Table
1. Where "P" represents the problem, "n" represents the
dimension of the problem. "nf" and "ng" represent the
numbers of function calculations and gradient calcula-
tions, respectively.
From the Table 1, we see that the algorithm with trust
region radius of 1.5 k

performs better than the other
two settings. For most of problems, it needs less compu-
tation numbers both on function value and on gradient.
Then, we compare our line search and trust region al-
gorithm (L-NTR1) both with L-TTR and L-NTR. The
detailed results are listed in Table 3. Furthermore, for
depicting the performance of different algorithms, we say
that an algorithm wins only if the number of function
calculations required to solve a test problem is smaller
than or equal to 95% of the one required by another algo-
rithm. For example, the number of L-TTR for calculating
the objective function is 26, and the one of L-NTR1 is 27,
but we say the two algorithms are balance for the prob-
lem 15. The comparison of the experimental results is
given in Table 2.
Table 1. The computational results with different trust re-
gion radii.
0.5 k

0.75 k
 1.5 k

P n nf/ng nf/ng nf/ng
1 3 34(33) 44(30) 46(31)
2 6 31(26) 35(30) 47(37)
3 3 29(24) 25(20) 35(26)
4 2 11(11) 12(12) 15(15)
5 3 43(39) 45(34) 35(29)
6 4 23(21) 19(16) 19(16)
8 2 14(13) 14(14) 12(11)
9 3 33(28) 25(18) 21(15)
10 2 12(11) 13(12) 11(9)
11 4 43(38) 34(32) 27(25)
12 3 31(29) 27(23) 23(21)
13 3 24(20) 21(19) 20(15)
14 2 17(17) 14(14) 13(13)
15 8 44(26) 27(23) 27(21)
16 2 12(11) 13(12) 11(9)
17 4 41(37) 34(31) 35(27)
18 2 15(14) 15(14) 15(14)

An Improved Line Search and Trust Region Algorithm
52
Table 2. The statistic results of experiments.
Algorithms Wins Balances
L-NTR1
L-NTR
10
6
1
1
L-NTR1
L-TTR
10
5
2
2
Table 3. Comparison with different algorithms.
L-TTR L-NTR
L-NTR1 (1.5k

)
P n nf/ng nf/ng nf/ng
1 3 27(25) 32(27) 46(31)
2 6 21(19) 33(24) 47(37)
3 3 24(20) 25(18) 35(26)
4 2 11(11) 13(13) 15(15)
5 3 153(109) 45(41) 35(29)
6 4 22(18) 25(17) 19(16)
8 2 15(13) 13(12) 12(11)
9 3 21(19) 26(20) 21(15)
10 2 14(13) 13(12) 11(9)
11 4 31(26) 25(23) 27(25)
12 3 32(26) 26(23) 23(21)
13 3 28(24) 24(22) 20(15)
14 2 15(15) 14(14) 13(13)
15 8 26(22) 32(20) 27(21)
16 2 14(13) 13(12) 11(9)
17 4 43(37) 33(32) 35(27)
18 2 14(13) 15(14) 15(14)
Clearly, our proposed new algorithm L-NTR1 is better
than L-TTR and L-NTR. The numbers of wins for the
two algorithms L-NTR1 and L-NTR are 10 and 6, re-
spectively. The numbers of wins for the two algorithms
L-NTR1 and L-TTR are 10 and 5, r espectively. Th at is to
say, in the 17 problems, our algorithm L-NTR1 wins 10
times. So our new line search and trust region method
(L-NTR1) performs much better than L-TTR and L-NTR.
(Table 3)
4. Conclusions and Future Works
In this paper, we investigate the performance of a new
algorithm where the trust region subproblem is con-
structed by introducing negative gradient. By introducing
the improvement of the trust region subproblem, the line
search and trust region algorithm is improved. The nu-
merical test results indicate that the number of function
calculations is reduced significantly for most test prob-
lems. In general, we think the new line search and trust
region algorithm may be more effective in practice. In
the near future, we will still devote ourselves to studying
the effect with different choices of the trust region radius
to investigate when the trust region algorithm performs
better.
5. Acknowledgements
We want to thank Prof essor Y. X. Yuan for prov idin g the
original FORTRAN code of the line search and trust re-
gion algorithm. Furthermore, this work is supported by
the National Nature Science Foundation of China (Grant
No. 60903088, 11101115) ，the Natural Science Founda-
tion of Hebei Province (Grant No. A2010000188) and
100-Talent Progr amme of Hebei Province (CPRC002).
REFERENCES
[1] J. J. Moré and D. C. Sorensen, “Computing a Trust Re-
gion Step,” SIAM Journal on Scientific and Statistical
Computing, Vol. 4, No. 3, 1983, pp. 553-572.
doi:10.1137/0904038
[2] M. J. D. Powell, “Convergence Properties of a Class of
Minimization Algorithms,”O. L. Mangasarian, R. R.
Meyer and S. M. Robinson eds., Nonlinear Programming,
Academic Press, New York, 1975, pp. 1-27.
[3] R. Fletcher, “Practical Methods of Optimization, John
Wiley and Sons,” New York, 1987.
[4] A. R. Conn, N. I. M. Gould and Ph. L. Toint,
“Trust-Region Methods,” SIAM, Philadelphia, 2000.
doi:10.1137/1.9780898719857
[5] G. X. Ma, “A Modified Trust Region Methods for Un-
constrained Optimization (in Chinese),” Master's Thesis,
2003.
[6] Q. H. Zhou, Y. R. Zhang, F. X. Xu and Y. Geng, “An
Improved Trust Region Method for Unconstrained Opti-
mization,” accepted by Scie nce China Mathemati cs .
[7] J. Nocedal and Y. Yuan, “Combining Trust Region and
Line Search, Y. Yuan, ed.,” Advances in Nonlinear Pro-
gramming, Kluwer, 1998, pp. 153-175.
[8] J. J. Moré, B. S. Garbow and K. H. Hillstrom, “Testing
Unconstrained Optimization Software,” ACM Transac-
tion Mathematics, Vol. 7, No. 1, 1981, pp. 17-41.