 Vol.3, No.1, 85-90 (2011) Natural Science http://dx.doi.org/10.4236/ns.2011.31012 Copyright © 2011 SciRes. OPEN ACCESS A hybrid conjugate gradient method for optimization problems* Xiangrong Li, Xupei Zhao Department of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, China; xrli68@163.com Received 14 October 2010; revised 18 November 2010; accepted 22 November 2010. ABSTRACT A hybrid method of the Polak-Ribière-Polyak (PRP) method and the Wei-Yao-Liu (WYL) method is proposed for unconstrained optimization pro- blems, which possesses the following proper-ties: i) This method inherits an important prop-erty of the well known PRP method: the ten-dency to turn towards the steepest descent di-rection if a small step is generated away from the solution, preventing a sequence of tiny steps from happening; ii) The scalar 0kβ holds automatically; iii) The global convergence with some line search rule is established for nonconvex functions. Numerical results show that the method is effective for the test prob-lems. Keywords: Line Search; Unconstrained Optimization; Conjugate Gradient Method; Global Convergence 1. INTRODUCTION We are interested to consider the unconstrained opti-mization problem min ,nxfx (1.1) where :nf is continuously differentiable. It is well known that there are many methods for solving optimization problems (see [24,26,28-32,34] etc.), where the conjugate gradient(CG) method is a powerful line search method because of its simplicity and its very low memory requirement, especially for the large scale opti-mization problems [22,23,27], which can avoid, like steepest descent method, the computation and storage of some matrices associated with the Hessian of objective functions. The following iterative formula is often used by the nonlinear CG method 1,0,1,2,kkkkxx dk (1.2) for (1.1), where kx is the current iterate point, 0k is a steplength, and kd is the search direction designed by 1, if k1,, if k= 0 kkkkkgddg  (1.3) where k is a scalar which determines the differ-ent conjugate gradient methods [4,5,8,9,12,13,15,16,18, 20,21,25,33] etc., and kg is the gradient of ()fx at the point kx. The well-known formula for k from the computation point of view is the following PRP method 112,Tkk kPRPkkgg gg (1.4) where kg and 1kg are the gradients kfxand 1kfx of ()fx at the point kx and 1kx, respec-tively, and  denotes the Euclidian norm of vectors. Throughout this paper, we also denote kfx by kf. Polak and Ribèire  proved that this method with the exact line search is globally convergent when the objec-tive function is convex. Powell  gave a counter ex-ample to show that there exist nonconvex functions on which the PRP method does not converge globally even the exact line search is used. He suggested that k should not be less than zero. Considering this suggestion, Gilbert and Nocedal  proved that the modified PRP method max 0,PRPkk is globally convergent with the weak Wolfe-Powell (WWP ) line search tech-nique and the assumption of sufficient descent condition. However, the global convergence of the PRP method is still open under the WWP line search rule. Recently, Wei, Yao, and Liu(WYL)  propose a new conjugate gradient formula 1112kTkk kkWYLkkgggggg (1.5) It is not difficult to deduce that *This work is supported by China NSF grands 10761001 and Guangxi SF grands 0991028. X. R. Li et al. / Natural Science 3 (2011) 85-90 Copyright © 2011 SciRes. OPEN ACCESS 86 21111 1122 0kTkkkk kk kkkWYLkkkgggg gggggggg  is true. The numerical results show that this method is competitive to the PRP method for the test problems of . Under the sufficient descent condition, this method is globally convergent with the WWP line search. These observations make us know that the sufficient descent condition 2,0Tkk kgdcg c is a constant holds for all 0k (1.6) is very important to ensure the global convergence [1,2,10,14], and the scalar 0k also plays a very important role [10,19]. This motivates us to propose a hybrid method combining the PRP method and the WYL method. The hybrid method will possess some better properties of the PRP method and the WYL method: (i) the tendency to turn towards the steepest descent direction if a small step is generated away from the solution, preventing a sequence of tiny steps from happening; (ii) The scalar 0k holds automatically. The global convergence with the WWP line search of the presented method is established for nonconvex ob-jective function. Numerical results show that this given method is competitive to the PRP method and the WYL method. This paper is organized as follows. In the next section, the algorithm is stated. The global convergence is proved in Section 3, and the numerical results are re-ported in Section 4. The last section gives one conclu-sion. 2. ALGORITHM Now we describe the given algorithm as follows. Here we call it Algorithm 1. Algorithm 1 (The hybrid algorithm of the PRP method and the WYL method) Step 0: Choose an initial point 0,0,1.nx  Set 00 0, :0.dg fxk Step 1: If ,kg then stop; Otherwise go to the next step. Step 2: Compute step size k by some line search rules. Step 3: Let 1.kkkkxxd If 1,kg then stop. Step 4: Calculate the search direction 11 ,PWkkkkdg d  (2.1) where max , .P WPRPWYLkkk Step 5: Set :1kk, and go to Step 2. Remark i) If 1,kkxx we have 1kkgg and 1kkgg which imply that 0,PRPk and 0,WYLk which means that 0PWk if a small step is gener-ated for all 0k. Thus the given method inherits the better property of the PRP method: the directions will turn out to be the steepest descent directions if the tiny steps from happening. ii) By the definition of the new formula ,PWk we have 21112max , 0P WPRPWYLWYLkkkkkkk kkkgggggg 3. THE GLOBAL CONVERGENCE The following assumptions are often needed to prove the convergence of the nonlinear conjugate gradient methods (see [5,9,10,20,21] etc.). Assumption 3.1 i) The function fx has a lower bound on the level set 0nxfx fx , where 0x is a given point and  is bounded. ii) In an open convex set 0 that contains , J is differentiable and its gradient g is Lipschitz continuous, namely, there exists a constants 0L such that 0, , .gxgyLx yxy (3.1) 3.1. The global Convergence with the Weak Wolfe-Powell Line Search The weak Wolfe-Powell (WWP) search rule is to find a step length k such that Tkkk kkkkfxdfgd (3.2) and ,TTkkkk kgxddg (3.3) where 0,12, ,1. This line search tech-nique is often used to study the convergence of conju-gate gradient algorithms [6,27,34]. At present, the global convergence of the PRP method with the WWP line search is still open. Lemma 3.1 Suppose that Assumption 3.1 holds. Let the sequence kg and kd be generated by Algo-rithm 1, 0,Tkkgd and the stepsize k be determined X. R. Li et al. / Natural Science 3 (2011) 85-90 Copyright © 2011 SciRes. OPEN ACCESS 8787by the WWP line search (3.2) and (3.3) Then the zoutendijk condition  220Tkkkkgdd (3.4) holds. Proof. By (3.3) and Assumption 3.1 ii), we have 211,TTkkkkkk kgdgg dLd this means that 21,Tkkkkgd Ld  which to-gether with 0,Tkkgd  and (3.2) implies that 2121,TkkkkkgdffLd summing up this inequality from 0k to , and us-ing Assumption 3.1 i), we can obtain this lemma. This completes the proof. We will prove the global convergence of Algorithm 1 by contradiction. Then we assume that there exists a positive constant 0 such that , 0.kgk (3.5) Using (3.5) deduces a contradiction to obtain our con-clusion. Similar to Lemma 3.3.1 in , based on Assumption 3.1, Lemma 3.1, the fact 0,PWk and (3.5), we can get the following lemma. Lemma 3.2 Let Assumption 3.1 hold and the se-quences kg and kd be generated by Algorithm 1. The sufficient descent condition (1.6) holds, and the stepsize k is determined by (3.2) and (3 .3). Suppose that the inequalities (3.5) is true. Then we have 0kd and 210,kkkuu where kkkdud. Proof. These two inequalities (1.6) and (3.5) imply that 0kd is true, for otherwise 0,kg then kkkudd is reasonable. Denote 1111, kPWkkkkkkdgrdd  By (2.1), for 0k, we have 11 ,kk kkur u this combining with 11kkuu shows that 11 1kkkkkkkru uuu   (3.6) The inequality 0PWk implies that0k is true, then it follows that from (3.6) and triangular inequality  11111112.kkkk kkkkkkkkkuuuuuuuur   (3.7) By (1.6) and (3.4), we get 4221112011kkkkkkgrgd Which together with (3.5), we obtain 210kkr By the above inequality and (3.7), we get this lemma. The proof is complete. The following property (*) was introduced by Gilbert and Nocedal , which pertains to the k under the sufficient descent condition. The WYL formula also has this property. Now we show that this property (*) per-tains to our method. Property (*). Suppose that 120.krg r (3.8) We say that the method has Property (*), if for all k, there exists constants 1b and 0 such that kb and 12kksb Lemma 3.3 Let Assumption 3.1 hold and the se-quences kg and kd be generated by Algorithm 1. Then the new formula PWk possesses property (*). Proof. The result of this lemma is proved by the fol-lowing two cases. Case i: we consider PRPk By (3.1), we have 11122..Tkkkk kPRPkkkLg sgg ggg (3.9) From Assumption 3.1 i), then there exists a constant 10M such that 1.ksM (3.10) Let 221 1max 2,1bLrrM and 2122bL, it follows that PRPkb and X. R. Li et al. / Natural Science 3 (2011) 85-90 Copyright © 2011 SciRes. OPEN ACCESS 88 12222 211.221.2kkPRPkkkLg sLLsbg Then the PRP formula PRPk has this property (*). Case ii: let us consider WYLk. Denote 1kkYg 1,kkkggg by (3.1), we get 11111111 2,kkkkkkkkk kkkk kkkkkkkgYg gggggg gggg ggggggLs (3.11) By (1.5), (3.11), (3.10) and (3.8) we have 1212221.2 ,Tkk kWYLkkkkkgYLsgYgg (3.12) let 221 1max2, 2bLM and 21222 ,bL it follows that (3.12) and the definition of b and  that 1b 222411221, and 2WYL WYLkk kLLbsb  Thus, the formula WYLkalso has the property (*). Using the definition of the max ,PWWYL PRPkkk, we conclude that the formula PWk possesses the property (*). The proof is complete. By Lemma 3.3, similar to Lemma 3.3.2 in , it is not difficult to prove the following result. Here we only state it as follows, but omit the proof. Lemma 3.4 (Lemma 3.3.2 in ) Let the sequences kg and kd be generated by Algorithm 1 and the conditions in Lemma 3.3 hold. If 0PWk and has property (*), then there exists a constant 0 such that, for any N and any index 0k there is an in-dex 0kk satisfying ,,2kk where,:1,,kikiNkik s N de-notes the set of positive integers, and ,kk denotes the numbers of elements in ,kk. Finally, by Lemma 3.2 and Lemma 3.4, we present the global convergence theorem of Algorithm 1 with the WWP line search. Similar to Theorem 3.3.3 in , it is not difficult to prove the result, here we also give the process of the proof. Theorem 3.1 Let the sequence ,kkgd be gener-ated by Algorithm 1 with the weak Wolfe-Powell line search and the conditions in Lemma 3.3 hold. Then lim inf0kkg. Proof. We will get this theorem by contradiction. Suppose that (3.5) is true, then the conditions in Lemma 3.2 and 3.3 hold. By Assumption 3.1 i), then there exists a constant 00 such that 0,xx (3.13) We also denote ,iiiudd then for all integers ,lk lk, we have 11111 1 .llki iiklliki kik ikxx susuu u Taking the norm in both sides of the above equality, and using (3.13) we get 10 1112lliiikik ikssuu  Let 08 be the smallest integer where  does not less than 08. By Lemma 3.2, there exists an index 0k such that 2114iiikuu (3.14) On the other hand, by Lemma 3.3, there exists 0kk satisfying ,2kk (3.15) For all ,1ikk , by Cauchy-Schwarz inequal-ity and (3.14), we obtain 111 111122211122 11 .42iik jjjkijjjkuu uuikuu     By the above inequality, (3.15) and (3.13), we have 101,12,224kikiksk Thus 08, this contradicts with the definition of . Therefore, the conclusion of this theorem is right. This completes the proof. 4. NUMERICAL RESULTS In this section, we report some numerical experiments. X. R. Li et al. / Natural Science 3 (2011) 85-90 Copyright © 2011 SciRes. OPEN ACCESS 8989The unconstrained optimization problems with the given initial points can be found at: www.ici.ro/camo/neculai/SCALCG/testuo.pdf, which were collected by Neculai Andrei. Since this new method is the hybrid method of the PRP method and the WYL method, we test Algorithm 1 with the WWP line search and compare its performance with those of the WYL  and the PRP  methods. The stop criteri-ons are given below: we stop the program if the inequal-ity kgx is satisfied or the inequality  1kkgxf x is satisfied, where 1.0 5.D All the codes were written in Fortran and run on PC with 2.60 GHz CPU processor and 256 MB memory and Windows XP op-eration system. In the experiments, the parameters were chosen as 1.0 2, 1.0 1DD. The dimension of the test problems is from 500 to 5000. The detailed numerical results are listed on the web site http://210.36.18.9:8018/publication.asp?id=35392. In Figure 1, “WYL”, “PRP”, and “MPRP-WYL” stand for the WYL method, the PRP method, and the new method, respectively. Figure 1 shows the performance of these methods relative to the iterative number of the function and gra-dient(NFN), which were evaluated using the profiles of Dolan and Moré . It is easy to see that the MPRP-WYL is predominant among these three methods and the new method can solve about 99% of the test problems successfully. The PRP method is better than the WY L method for 11.2t and the WYL method is better than the PRP method for 1.26t. Moreover, the PRP method solves about 98% of the test problems and the WYL method solve about 99% of the test prob-lems successfully, respectively. In a word, the given Figure 1. Performance profiles of conjugate gradient me- thods in Table 1 (NFN). method is competitive to the other two methods and the hybrid formula is notable. 5. CONCLUSION This paper gives a hybrid conjugate gradient method for solving unconstrained optimization. The global con-vergence for nonconvex functions with the WWP line search is established. The numerical results show that the given method is competitive to the other standard conjugate gradient methods for the test problems. For further research, we should study the convergence of the new algorithm under other line search rules. Moreover, more numerical experiments and testing en-vironments (such that ) for large practical problems should be done in the future. REFERENCES  Ahmed, T. and Storey, D. (1990) Efficient hybrid conju-gate gradient techniques. Journal of Optimization Theory and Applications, 64, 379-394. doi:10.1007/BF00939455  Al-Baali, A. (1985) Descent property and global conver-gence of the Flecher-Reeves method with inexact line search. IMA Journal of Numerical Analysis, 5, 121-124. doi:10.1093/imanum/5.1.121  Bongartz, K.E., Conn, A.R., Gould, N.I.M. and Toint, P.L. (1995) CUTE: Constrained and unconstrained test-ing environments. ACM Transactions on Mathematical Software, 21, 123-160. doi:10.1145/200979.201043  Dai, Y. (2002) A nonmonotone conjugate gradient algo-rithm for unconstrained optimization. Journal of Systems Science and Complexity, 15, 139-145.  Dai, Y. and Yuan, Y. (2000) A nonlinear conjugate gra-dient with a strong global convergence properties. SIAM Journal on Optimization, 10, 177-182. doi:10.1137/S1052623497318992  Dai, Y. and Yuan, Y. (1998) Nonlinear conjugate gradi-ent methods. Shanghai Scientific and Technical Publish-ers, Shanghai.  Dolan, E.D. and Moré, J.J. (2002) Benchmarking opti-mization software with performance profiles. Mathe-matical Programming, 91, 201-213. doi:10.1007/s101070100263  Fletcher, R. (1997) Practical Method of Optimization, Vol I: Unconstrained Optimization. 2nd Edition, Wiley, New York.  Fletcher, R. and Reeves, C. (1964) Function minimiza-tion bu conjugate gradients. Computer Journal, 7, 149-154. doi:10.1093/comjnl/7.2.149  Gibert, J.C. and Nocedal, J. (1992) Global convergence properties of conugate gradient methods for optimization. SIAM Journal on Optimization, 2, 21-42. doi:10.1137/0802003  Grippo, L. and Lucidi, S. (1997) A globally convergent version of the Polak-Ribière gradient method. Mathe- X. R. Li et al. / Natural Science 3 (2011) 85-90 Copyright © 2011 SciRes. OPEN ACCESS 90 matical Programming, 78, 375-391. doi:10.1007/BF02614362  Hager, W.W. and Zhang, H.C. (2005) A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM Journal on Optimization, 16, 170-192. doi:10.1137/030601880  Hestenes, M.R. and Stiefel, E. (1952) Method of conju-gate gradient for solving linear equations. Journal of Re-search National Bureau of Standards, 49, 409-436.  Hu, Y.F. and Storey, C. (1991) Global convergence re-sult for conjugate method. Journal of Optimization The-ory and Applications, 71, 399-405. doi:10.1007/BF00939927  Li, G., Tang, C. and Wei, Z. (2007) New conjugacy con-dition and related new conjugate gradient methods for unconstrained optimization. Journal of Computational and Applied Mathematics, 2, 523-539. doi:10.1016/j.cam.2006.03.005  Liu, Y. and Storey, C. (1992) Effcient generalized con-jugate gradient algorithms, part 1: theory. Journal of Op-timization Theory and Applications, 69, 17-41.  Moré, J.J., Garbow, B.S. and Hillstrome, K.E. (1981) Testing unconstrained optimization software. ACM Transactions on Mathematical Software, 7, 17-41. doi:10.1145/355934.355936  Polak, E. and Ribiere, G. (1969) Note sur la xonvergence de directions conjugees. Rev. Francaise informat Re-cherche Operatinelle, 3e Annee, 16, 35-43.  Powell, M.J.D. (1984) Nonconvex minimization calcula-tions and the conjugate gradient method. Lecture Notes in Mathematics, 1066, 122-141.  Wei, Z., Li, G. and Qi, L. (2006) New nonlinear conju-gate gradient formulas for large-scale unconstrained op-timization problems. Applied Mathematics and Compu-tation, 179, 407-430. doi:10.1016/j.amc.2005.11.150  Wei, Z., Yao, S. and Liu, L. (2006) The convergence properties of some new conjugate gradient methods. Ap-plied Mathematics and Computation, 183, 1341-1350. doi:10.1016/j.amc.2006.05.150  Yu, G.H. (2007) Nonlinear self-scaling conjugate gradi-ent methods for large-scale optimization problems. The-sis of Doctor’s Degree, Sun Yat-Sen University.  Yuan, G.L. (2009) Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems. Optimization Letters, 3, 11-21. doi:10.1007/s11590-008-0086-5  Yuan, G.L. and Lu, X.W. (2008) A new line search method with trust region for unconstrained optimization. Communications on Applied Nonlinear Analysis, 15, 35-49.  Yuan, G.L. and Lu, X.W. (2009) A modified PRP con-jugate gradient method. Annals of Operations Research, 166, 73-90. doi:10.1007/s10479-008-0420-4  Yuan, G.L., Lu, X.W. and Wei, Z.X. (2007) New two-point stepsize gradient methods for solving uncon-strained optimization problems. Natural Science Journal of Xiangtan University, 29, 13-15.  Yuan, Y. and Sun, W. (1999) Theory and Methods of Optimization. Science Press of China, Beijing.  Yuan, G.L. and Wei, Z.X. (2009) New line search meth-ods for unconstrained optimization. Journal of the Ko-rean Statistical Society, 38, 29-39. doi:10.1016/j.jkss.2008.05.004  Yuan, G.L. and Wei, Z.X. (2008) The superlinear con-vergence analysis of a nonmonotone BFGS algorithm on convex objective functions. Acta Mathematica Sinica, 24, 35-42. doi:10.1007/s10114-007-1012-y  Yuan, G.L. and Wei, Z.X. (2010) Convergence analysis of a modified BFGS method on convex minimizations. Computational Optimization and Applications, 47, 237-255. doi:10.1007/s10589-008-9219-0  Yuan, G.L. and Wei, Z.X. (2009) A Rank-One fitting method for unconstrained optimization problems. Mathe-matica Applicata, 22, 118-122.  Zhang, H.C. and Hager, W.W. (2004) A nonmonotone line search technique and its application to unconstrained optimization. SIAM Journal on Optimization, 14, 1043-1056. doi:10.1137/S1052623403428208  Zhang, L., Zhou, W. and Li, D. (2006) A descent modi-fied Polak-Ribiére-Polyak conjugate method and its global convergence. IMA Journal on Numerical Analysis, 26, 629-649. doi:10.1093/imanum/drl016  Zoutendijk, G. (1970) Nonlinear programming computa-tional methods. In: Abadie, J. Ed., Integer and Nonlinear Programming, NorthHolllad, Amsterdam, 37-86.