Paper Menu >>
Journal Menu >>
 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. Email: qinghua.z[email protected] 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). Copyright © 2013 SciRes. JSEA  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 . :k1 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 Copyright © 2013 SciRes. JSEA  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 fxk 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:kk1; 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) Copyright © 2013 SciRes. JSEA  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. |