An Improved Line Search and Trust Region Algorithm

Copyright © 2013 SciRes. JSEA

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.