Applied Mathematics, 2011, 2, 779782 doi:10.4236/am.2011.26104 Published Online June 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM Modified LS Method for Unconstrained Optimization* Jinkui Liu1, Li Zheng2 1College of Mathematics and Computer Science, Chongqing Three Gorges University, Chongqing, China 2Chongqing Energy Coll e ge , Chongqing, China Email: liujinkui2006@126.com Received December 28, 2010; revised May 6, 2011; acce pted May 9, 2011 Abstract In this paper, a new conjugate gradient formula and its algorithm for solving unconstrained optimiza tion problems are proposed. The given formula satisfies with k satisfying the descent condition. Under the GrippoLucidi line search, the global convergence property of the given method is dis cussed. The numerical results show that the new method is efficient for the given test problems. VLS k VLS k 0 VLS k d Keywords: Unconstrained Optimization, Conjugate Gradient Method, GrippoLucidi Line Search, Global Convergence 1. Introduction The primary objective of this paper is to study the global convergence properties and practical computational per formance of a new conjugate gradient method for nonlinear optimization without restarts, and with suitable conditions. Consider the following unconstrained optimization prob lem: min n xR x , where :n RR is smooth and its gradient is available. LS conjugate gradient method for solving un constrained optimization problem is iterative formulas of the form 1kkkk xd , (1.1) 1 ,for , for2, k kkkk gk dgd k 1; (1.2) where k is the current iterate, k is a positive scalar and called the steplength which is determined by some line search, k is the search direction; dk is the gra dient of at k , and k is a scalar and T 1 T 11 kk k LS k kk gg g dg , (LiuStorey (LS) [1]), [2] proved the global convergence of the LS method with GrippoLucidi line search. And the GrippoLucidi line search is to compute T 2 max,0,1,2, kk j k k gd j d (1.3) satisfying : 2 2 δ kkk kkk xdfx d , (1.4) 22 T 2111 11kkk k cggd cg , (1.5) where , δ00 , 0, 1 and 01. 12 It is well known that some other people have studied many of the variants of the LS method, for example [34]. In this paper, a kind of the LS method is proposed: cc T 1 VLS T 11 kkkk k kk gg tg dg , (1.6) where 1 k kk tg ,and is the Euclidean norm. In the next section, we prove the global convergence of the new method for nonconvex functions with the GrippoLucidi line search. In Section 3, numerical ex periments are given. 2. Global Convergence of the New Method In order to prove the global convergence of the new method, we assume that the objective function satisfies *This work was supported by The Nature Science Foundation o Chongqing Education Committee (KJ091104, KJ101108).
J. K. LIU ET AL. 780 the following assumption. Assumption (H): 1) The level set 1 N xfx fx is bounded, where 1 is the starting point. 2) In some neighborhood W of , the objective function is continuously differentiable, and its gradient is Lipschitz continuous, i.e., there exists a constant such that N 0L , xgy Lxy for all , yW. (2.1) Lemma 2.1 [5]. Suppose Assumption (H) holds. Con sider any iteration in the form (1.1) and (1.2), where k satisfies for d T0 kk gd kN and k satisfies Grip poLucidi line search. Then 2 2 1 cos kk k g . (2.2) where T cos kkkkk dgd and k is the an gle between k and . k d The following Lemma shows that the Grippolucidi line search is suitable for the new formula. Lemma 2.2. Suppose that Assumption (H) holds. Consider the method of form (1.1) and (1.2), where VLS kk , and where k satisfies GrippoLucidi line search. Then k , there exists a constant such 0c that T 2 kk k k d cd . Proof. Since 11 dg , (1.5) holds for 1k . Sup pose that (1.5) holds for . 1k Denote 12 3 min 1,10 2 cc cL . (2.3) By (1.2), Lipschitz condition (2.1) and (1.5), for any T 32 0, kk k k d cd , we have 2 T 111 211 1 TT T 1111 11 TT 22 11 1 11 1 TT 222 11 1 T () 22 kkkk kkkkkk VLS kkkk kkkk kk kk kkkkkk k kkkkkk kk kk kkkkkkk kk gg tgk gggtgd gd ggdgd dg dg gggggd ggggtgd dg dg gggdgLd dg 2 12 1 Tmin 1,1. k kk cc g dg So (1.5) holds, for any T 32 0, kk k k d cd . On the other hand, by the mean value theorem and Lipschitz condition (2.1), we have 1T 0 1T T 0 2 T2 d d 1. 2 kkk k kkk kk kkkkk kkkk kkkkk fxd fx gxt ddt dgxdg d gdL d t We can test (1.4) holds, for T 2 2 0, 2δ kk k k d Ld . The existence of k satisfying (1.4) and (1.5) has bean proved. Furthermore, the conclusion holds for 3 2 min, ,2δ cc L . VLS kk , and where k satisfies GrippoLucidi line search. Then + lim i0g. nf k k Proof. By Lipschitz condition (), (1.3), (1.5) and (2.1), we can obtain 1.2 VLS kkk dg d 1 1 1 11 11 1 T 11 2 1 1 T 11 1 () 1 2 1 12. k kkk kk T kk kkk kk k kk k kk kk k gt g gd dg ggg gd gdg L gd dg Lg (2.4) By the Assumption (H), we know that Lemma 3. holds. From (1.5), (2.2) and (2.4), we have 1 Theorem 2.1. Suppose that Assumption (H) holds. Consider the method of form (1.1) and (1.2), where Copyright © 2011 SciRes. AM
J. K. LIU ET AL.781 ethod, LS method and VLS method. VLS Table 1. The performance of DY m Problem Dim DY LS Beale 2 75/64 185 2 186/1/65/55/72/64 Box Thrnsional 1727/043 855 658 eeDime3 1/1/1 1/1/1 1/1/1 Penalty1 50 2117/2/426/31/112/9 100 31/157/121 18/120/83 22/146/119 200 26/160/121 28/157/114 20/124/93 2 T 2 2 2 11 2 2 2 1 1 cos 12. kk kk kk k k k gd gd cL g This result implies + lim inf0 k kg . 3. Numerical Reusults w algorithm. Algorithm 3.1: In this section, we give the ne Step 1: Data: 1 n R, 0 . Set 1 d1 , if g 1 g , then stop. Step 2: Compute k bGrippline sy the oLucidi ear ches. Step 3: Let 1kkkk xd , 11kk ggx , if 1k g , then stop. pute Step 4: Com1k by (1rate .6), and gene1k d by (1.2). g the Algorithm 3.1 on the following problems, ants perforof the DY method an Step 5: Set kk o to step 2. We test 1, d compare imance to that d LS method with the strong Wolfe line searches where k is computed by T kkk k xd fx δkk f gd, k (3.1) TT kkkk kk xdd g .d In algorithm, the parameters: (3.2) 1.5 , 0.5 , 10.25c, , 21.5cδ0.01, 0.1 . The termina tion condition is 6 10 k g , orItm e mof iterations. The numerical rur tests are reported in Ta ble 1. The column “Problem” represents th Itmax > 9999. ax Maximu number esults of o e problem’s na denotes th me; “Dim” denotes the dimension of the tested prob lems. The detailed numerical results are listed in the form NI/NF/NG, where NI, NF, NG denote the number of iterations, function evaluations, and gradient evalua tions, respectively. VLS method: VLS kk , k by the GrippoLucidi line searches LS method: LS kk , k by the stre line searches. ong Wolf DY method: k by the strong Wolfe line searches, k is computed by 2 LS T 11 k g g . k kk k dg 1) Beale Test Function： the initial point 2) Box Threensional Test Function: , In the following, we give the tested functions: 2 22 1212 2 1.5 12.25 1 , fx xxxx x 1 2.6251x 2 3 T 1,1. Dime 12 32 0.1 0.10.1 3 1 ee ee ix ixii fx x i th 3) Penalty th From the nu, we know that the new method is efficient for the given problems uner the GrippoLucidi line searches. 4. us referees and editors for comments on this paper. . References ate Gradient Algorithms. Part 1: Theory,” Journal of Opti ry and Applications, Vol. 69, No. 1, 1992, i:10.1007/BF00940464 e initial point T 0,10,20. Test Function I: 2 2 52 11 1010.25 , nn ii ii fx xx e initial point T 1, 2,, m. merical results d Acknowledgements We are grateful to anonymo their useful suggestions and 5 [1] Y. Liu and C. Storey, “Efficient Generalized Conjug mization Theo pp. 129137. do [2] Z. F. Li, J. Chen and N. Y. Deng, “A New Conjugate Gradient Method and Its Global Convergence Proper ties,” Mathematical Programming, Vol. 78, 1997, pp. 375391. doi:10.1007/BF02614362 Copyright © 2011 SciRes. AM
J. K. LIU ET AL. 782 36643. [3] G. H. Yu, Y. L. Zhao and Z. X. Wei, “A Descent Nonlin ear Conjugate Gradient Method for LargeScale Uncon strained Optimization,” Applied Mathematics and Com putation, Vol. 187, No. 2, 2007, pp. 6 doi:10.1016/j.amc.2006.08.087 [4] J. K. Liu, X. L. Du and K. R. Wang, “Convergence of Descent Methods with Variable Parameters,” Acta Mathematicae Applicatae Sinica, Vol. 33, No. 2, 2010, pp. 222232. [5] Z. F. Li, J. Chen and N. Y. Deng, “Convergence Proper ties of Conjugate Gradient Methods with Goldstein Line Searches,” Journal of China Agricultural University, Vol. 1, No. 4, 1996, pp. 1518. Copyright © 2011 SciRes. AM
