 Applied Mathematics, 2011, 2, 779-782 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 E-mail: 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 Grippo-Lucidi 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, Grippo-Lucidi 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 , (Liu-Storey (LS) [1]), [2] proved the global convergence of the LS method with Grippo-Lucidi line search. And the Grippo-Lucidi 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 [3-4]. 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 Grippo-Lucidi 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- po-Lucidi 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 Grippo-lucidi 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 Grippo-Lucidi 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 Grippo-Lucidi 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 ee-Dime3 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 o-Lucidi 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 , orIt-m e mof iterations. The numerical rur tests are reported in Ta- ble 1. The column “Problem” represents th It-max > 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 Grippo-Lucidi 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 Grippo-Lucidi 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. 129-137. 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. 375-391. doi:10.1007/BF02614362 Copyright © 2011 SciRes. AM  J. K. LIU ET AL. 782 36-643. [3] G. H. Yu, Y. L. Zhao and Z. X. Wei, “A Descent Nonlin- ear Conjugate Gradient Method for Large-Scale 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. 222-232. [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. 15-18. Copyright © 2011 SciRes. AM
|
