 Applied Mathematics, 2011, 2, 303-308 doi:10.4236/am.2011.23035 Published Online March 2011 (http://www.scirp.org/journal/am) Copyright © 2011 SciRes. AM Three New Hybrid Conjugate Gradient Methods for Optimization* Anwa Zhou, Zhibin Zhu, Hao Fan, Qian Qing School of Mathematics and Computational Science, Guilin University of Electronic Technology, Guilin, China E-mail: zhouanwa@126.com Received November 10, 2010; revised January 9, 2011; accepted January 14, 2011 Abstract In this paper, three new hybrid nonlinear conjugate gradient methods are presented, which produce sufﬁcient descent search direction at every iteration. This property is independent of any line search or the convexity of the objective function used. Under suitable conditions, we prove that the proposed methods converge glo-bally for general nonconvex functions. The numerical results show that all these three new hybrid methods are efficient for the given test problems. Keywords: Conjugate Gradient Method, Descent Direction, Global Convergence 1. Introduction In this paper, we consider the unconstrained optimizatio n problem: min, nfxxR (1.1) where :nfRR is continuously differentiable and the gradient of f at x is denoted by gx. Due to its simplicity and its very low memory re-quirement, the conjugate gradient (CG) method plays a very important role for solving (1.1). Especially, when the scale is large, the CG method is very efﬁcient. Let 0nxR be the initial guess of the solution of problem (1.1). A nonlinear conjugate gradient method is usually designed by the iterative fo rm 1,0,1,,kkkkxx dk  (1.2) where kxis the current iterate point, 0k is a step-length which is determined by some line search, and kd is the search direction deﬁned by 1,if0,,if 0,kkkkkgkdgd k  (1.3) where kg denoteskgx, and k is a scalar. There are some well-known formulas for k, which are given as follows: 221,kFRkkgg ; 211,kCDkTkkgdg ; 211,kDYkTkkgdy ; 111,THS kkkTkkgydy ; 121,TPRP kkkkgyg [5,6]; 111,TLS kkkTkkgydg ; where 11kkkygg and  stands for the Eucli-dean norm of vectors. Although the methods above are equivalent [8,9] when f is a strictly convex quadratic function and k is calculated by the exact line search, their behaviors for general objective functions may be far different. Gener-ally, in the convergence analysis of conjugate gradient methods, one hopes the inexact line search such as the Wolfe conditions, the strong Wolfe conditions or the strong *Wolfe conditions,which are showed respectively as follows: 1) The Wolfe line search is to find k such that *This work was supported in part by the NNSF (No. 11061011) of China and Program for Excellent Talents in Guangxi Higher EducationInstitutions (156). A. W. ZHOU ET AL. Copyright © 2011 SciRes. AM 304,,Tkkkk kkkTTkkkk kkfxdfx gddgx ddg  (1.4) with 10,2 and 1. 2) The strong Wolfe line search is to findksuch that ,,Tkkkk kkkTTkkkk kkfxdfx gddgx ddg  (1.5) with 10,2 and 1. 3) The strong *Wolfe line search is to find k such that ,0,Tkkkk kkkTTkkkk kkfxdfx gddg dgxd  (1.6) with 10,2 and 1. For general functions, Zoutendjk  and Al-Baali  had proved the global convergence of the FR me-thod with differen t lin e sear ches. And Powell  gave a counter example which showed that there exist noncon-vex functions such that the PRP method may cycle and does not approach any stationary point even with exact line search.Although one would be satisﬁed with its global convergence, the FR method performs much worse than the PRP (HS, LS) method in real computa-tions. In other words, in practical computation, the PRP method, the HS method, and the LS method are generally believed to be the most efﬁcient conjugate gradient me-thods since these methods essentially perform a restart if a bad direction occurs. A similar case happens to the DY method and the CD method. That is to say the conver-gences of the CD , DY and FR methods are established [1-3], however their numerical results are not so well. Resently, some good results on the nonlinear conjugate gradient method are given. Combining the good numeri-cal performance of the PRP and HS methods and the nice global convergence properties of the FR and DY me-thods, recently,  and  proposed some hybrid me-thods which we call the H1 method and the H2 method, respectively, that is, 1max 0,min,,HPRP FRkkk (1.7) 2max 0,min,.HHSDYkkk (1.8) Gilbert and Nocedal  extended H1 to the case that max,min ,.FRPRP FRkkkk Numerical performances show that the H1 and the H2 methods are better than the PRP method [13,14,16]. As we all know, the FR , DY and CD methods are descent methods, but their descent properties depend on the line se arch su ch as the strong Wo lfe line se arch (1 .5). Similar to the descent three terms PRP method in , Zhang et al. [18,19] proposed a modified FR method which we call the MFR method, that is, 1111112: 1.TFR kkkkkk kTkkTFR FRkkkkkkkgdMFR dgdgdggdgdg   (1.9) And  also gave an equivalent form to the MFR method. Similarly, Zhang  also proposed a modiﬁed DY method called the MDY method, that is, DY 1111DY DY112DY : 1Tkkkkkk kTkkTkkkkkkkgdMdg dgdggdgdg   (1.10) It is easy to see that the MFR and MDY methods have an important property that the search directions satisfy 2,Tkk kgd g which depend s neither on the line search used nor on the convexity of the objective function; moreover these two methods reduce to the FR method and the DY method respectively with exact line search.  has explored the convergence and efﬁciency of the MFR method for nonconvex functions with the Wolfe line search or Armijo line search. Based on the idea of the H1 and the H2 methods, recently, Zhang- Zhou  replaced FRk in (1.9) and DYk in (1.10) with H1kin (1.7) andH2k in (1.8), respectively, and proposed two new hybrid PRP–FR and HS–DY methods called the NH1 method and the NH2 method, respec-tively, that is, H1 H1112N1:1 Tkkkk kkkkgdHdgdg  (1.11) H2 H2112N2:1 Tkkkk kkkkgdHdgdg  (1.12) Obviously, these two new hybrid methods still satisfy 2,Tkk kgd g (1.13) which shows that they are descent and independent of any line search used.  proved the global convergence of these two methods and also showed their efﬁciency in real computations. Similarly,based on the idea of the methods all above, we consider the CD method, and propose three new hy- A. W. ZHOU ET AL. Copyright © 2011 SciRes. AM 305brid conjugate gradient(CG) methods which we call the H3 method, the MCD method and the NH3 method, re-spectively, that is 33:max 0,min,HLSCDkkkH (1.14) 1111112: 1TCD kkkkkkkTkkTCD CDkkkkkkkgdMCD dgdgdggdgdg   (1.15) H3 H3112N3:1 Tkkkk kkkkgdHdgdg  (1.16) From these three methods above, it is not difficult to see that the MCD and the NH3 methods also sat- isfy 2,Tkk kgd g which shows that they are suffi-cient descent methods. In the next section, the new algo-rithms are given. The global convergence of the pro-posed methods are proved in Section 3. We give the nu-merical experiments in Section 4, and in Section 5, the conclusion is presented. 2. Algorithm 2.1. Algorithm 1 (The H3 Algorithm) Step 0: Choose an initial point 0,nxR01, 10,2 and 1. Set 00,:0.dgk Step 1: If ,kgthen stop; Otherwise go to the next step. Step 2: Compute step size k by strong *Wolfe line search rule (1.6). Step 3: Let 1.kkkkxxd If 1,kg then stop. Step 4: Calculate the search direction 3111.Hkkkkdg d  Step 5: Set :1,kkand go to Step 2. 2.2. Algorithm 2 (The MCD (Or the NH3) Algorithm) Step 0: Choose an initial point 0,nxR01, 10,2 and 1. Set 00,:0.dgk Step 1: If ,kgthen stop; otherwise go to the next step. Step 2: Compute step size k by Wolfe line search rule (1.4). Step 3: Let 1.kkkkxxd If 1,kg, then stop. Step 4: Calculate the search direction 1kd by (1.15) (or (1.16)). Step 5: Set :1,kk and go to Step 2. 3. The Global Convergence Assumption A 1) The level set0nxRfx fx is bounded, where 0,nxRis a given point. 2) In an open convex set N that contains , f is continuously differentiable and its gradientgis Lipschitz continuous, namely, there exists a constant 0L such that ,, .gxgyLxyxyN (3.1) Sincekfxis decreasing, it is clear that the se-quencekxgenerated by Algorithm 1 and Algorithm 2 is contained in . In addition, we can get from Assump-tion A that there exists a constant B and 10,such that 1,,.xBgx x (3.2) In the latter part of the paper, we always suppose that the conditions in Assumption A hold. Then there is an useful lemma, which was originally given in [10,21]. Lemma 3.1 Letkxbe generated by (1.2) andkdis a descent direction. If k is determined by the Wolfe line search (1.4), then we have 220.Tkkkkgdd (3.3) From Lemma 3.1 and (1.13) that for the MCD and NH3 methods with the Wolfe line search,we can easily obtain the following condition 420.kkkgd (3.4) We now establish the global convergence theorem for Algorithm 1 and Algorithm 2 . 3.1. The Global Convergence of the H3 Method For simlpicity, here, we list the Theorem 2.3 in  as the following Lemma 3.2 without proof. Lemma 3.2 Suppose that 0xis an initial point, Con-sider the method (1.2) and (1.3), where k is computed by the Wolfe line search(1.4), andkis such that ,1 ,krc where 1,0.1kkDYkrc Then if 0kgfor all 0,kwe have that A. W. ZHOU ET AL. Copyright © 2011 SciRes. AM 3060, 0.Tkkgd k Further, the method converges in the sense that liminf 0.kkg  From the Lemma 3.2 above, similar to Corollary 2.4 in , we give the global convergence of the H3 me-thod(Algorithm 1). Theorem 3.3 Suppose that0xis an initial point, Con-sider the Algorithm1, then we have either0kgfor some 0,k or liminf 0.kkg Proof From the second inequality of (1.6) and the de- finitions of 3,HCDkkand ,DYkit follows that 30.HCD DYkkk Therefore the statement follows lemma 3.2.  3.2. The Global Convergence of the MCD Method Now, we establish the global convergence theorem for the MCD method. Theorem 3.4 Let kxbe generated by the MCD me-thod (Algorithm 2, wherekd satisfies (1.15)), then we have liminf 0.kkg  (3.5) Proof Suppose by contradiction that the desired con-clusion is not true, that is to say, there exists a con-stant 0such that ,0.kgk (3.6) Set 121,TCD kkkkkgdhg and then we have 221.CDTkkk kkkgdh ggFrom (1.15) and (1.13), it follows that 2212222112222 2211222221 2 2 2CDkkkkkCDCD Tkk kkkkkkCD Tkk kkkkkkkkCDkk kkkkddhgdhdghgdhhggdghgdhghg 222212CD Tkk kkkkkdhdghg (3.7) Dividing both sides of (3.7) by2Tkkgd, we get, from (1.13) and the deﬁnition ofCDk, that 2242kkTkkkddggd 222212222 221222 2121242122142212142122022()12111111.kkkCD kkTTTkkkk kkkk kkkTTTkkkkk kkkkkkkkkkkkkkkkiidhghgdgd gdgd hghgdggd gddhhgghdgggdggkg   The last inequality implies 422001,kkkkgkd which contradicts (3.4). The proof is then completed.  3.3. The Global Convergence of the NH3 Method The same as the Theorem 3.4, we can establish the fol-lowing global convergence theorem for the NH3 method. Theorem 3.5 Letkxbe generated by the NH3 me-thod (Algorithm 2, where kd satisfies (1.16) ), then we have liminf 0.kxg  (3.8) Proof Suppose by contradiction that the desired con-clusion is false, that is to say, there exists a con-stant 0such that ,0.kgk (3.9) Similar to (3.7), we get from (1.16) that 222 23212,HTkkk kkkkkddhdghg (3.10) where 3121.THkkkkkgdhg Notice that 3,0.HCDkkk (3.11) Dividing both sides of (3.10) by 2Tkkgd, we get, from (3.11), (1.13) and the deﬁnition of 3,Hk that A. W. ZHOU ET AL. Copyright © 2011 SciRes. AM 3072242kkTkkkddggd   222213222222122222 22122 212202221,kkkHkkTTTkkkk kkkkkCD kkTTTkkkk kkkk kkkTTTkkkkk kkkiidhghgdgd gddhghgdgd gdgd hghgdggd gdkg which contradicts (3.4). This ﬁnishes the proof.  4. Numerical Experiments In this section, we carry out some numerical experiments. These three algorithms have been tested on some prob-lems from . The results are summarized in the fol-lowing three tables: Table 1-3. For each test problem, No. is the number of the test problem in , 0x is the initial point, kx the final point, k the number of times of iteration for each problem. These three tables show the performance of these three methods relative to the iterations, It is easily to see that, for each algorithm, are all very efficient, especially for the problems such as s201, s207, s240, s311 . The results for each problem are accurate, and with less number of times of iteration. 5. Conclusions We have proposed three new hybrid conjugate gradient (CG) methods, that are, the H3 method, the MCD me- Table 1. The detail information of numerical experiments for H3 algorithm. .No 0x kx kg k S201 (8,9) (5.0000000, 6.0000000) 7.08791050e-00725 S205 (1,1) (2.9999973, 0.4999993) 8.17619783e-007 188S207 (–1.2,1) (0.9999993, 0.9999983) 7.08905387e-00761 S240 (100,–1, 2.5) (1.3367494e-007, –1.3367494e-009, 3.3418736e-009) 8.81057842e-00729 S311 (1, 1) (2.9999999, 2.0000000) 3.63497147e-00720 S314 (2,2) (1.8064954, 1.3839575) 9.83714228e-007 339Table 2. The detail information of numerical experiments for MCD algorithm. .No 0x kx kg kS201(8,9) (5.0000001,5.9999999) 9.53649845e-00734S205(1,1) (2.9999968,0.4999992) 9.97179740e-007253S207(–1.2,1) (0.9999992,0.9999979) 8.41893782e-007 151S240 (100,–1,2.5)(–9.909208e-008, 3.1120991e-008, 2.660865e-008) 8.37563602e-007 41S311(1,1) (2.9999999,2.0000000) 7.05200476e-00724S314(2,2) (1.8064954,1.3839575) 9.94928488e-007130 Table 3. The detail information of numerical experiments for NH3 algorithm. .No 0x kx kg kS201(8, 9) (5.0000001,5.9999999) 9.53649845e-00734S205(1,1) (2.9999972,0.4999993) 9.89188900e-007418S207(–1.2,1) (0.9999990,0.99999751) 9.59168006e-007168S240 (100,–1,2.5)(-9.9092086e-008, 3.1120991e-008, 2.6608656e-008) 8.37563602e-007 41S311(1,1) (2.9999999,2.0000000) 5.87169265e-00725S314(2,2) (1.8064954,1.3839575) 9.82136064e-007339 thod and the NH3 method, where the last two methods produce sufﬁcient descent search direction at every itera-tion. This property depends neither on the line search used nor on the convexity of the objective function. Un-der suitable conditions, we proposed the global conver-gence of these three new methods even for nonconvex minimization. And numerical experiments in section 4 showed that the new three algorithms are all efficient for the given test problems. 6. References  R. Fletcher and C. Reeves, “Function Minimization by Conjugate Gradients,” The Computer Journal, Vol. 7, No. 2, 1964, pp. 149-154. doi:10.1093/comjnl/7.2.149  R. Fletcher, “Practical Methods of Optimization, Un-constrained Optimization,” Wiley, New York, 1987.  Y. H. Dai and Y. Yuan, “A Nonlinear Conjugate Gra-dient Method with a Strong Global Convergence Prop-erty,” SIAM Journal on Optimization, Vol. 10, No. 1, 1999, pp. 177-182. doi:10.1137/S1052623497318992  M. R. Hestenes and E. L. Stiefel, “Methods of Conju-gate Gradients for Solving Linear Systems,” Journal of Research of the National Bureau of Standards, Vol. 49, No. 6, 1952, pp. 409-432.  B. Polak and G. Ribiere, “Note Surla Convergence des Méthodes de Directions Conjuguées,” Revue Francaise d’Informatique et de Recherche Opérationnelle, Vol. 16, A. W. ZHOU ET AL. Copyright © 2011 SciRes. AM 308No. 1, 1969, pp. 35-43.  B. T. Polyak, “The Conjugate Gradient Method in Ex-treme Problems,” USSR Computational Mathematics and Mathematical Physics, Vol. 9, No. 4, 1969, pp. 94-112. doi:10.1016/0041-5553(69)90035-4  Y. L. Liu and C. S. Storey, “Efficient Generalized Con-jugate Gradient Algorithms, Part 1: Theory,” Journal of Optimization Theory and Applications, Vol. 69, No. 1, 1991, pp. 129-137. doi:10.1007/BF00940464  Y. Yuan and W. Sun, “Theory and Methods of Optimi-zation,” Science Press of China, Beijing, 1999.  Y. H. Dai and Y. Yuan, “Nonlinear Conjugate Gradient Methods,” Shanghai Scientific and Technical Publishers, Shanghai, 1998.  G. Zoutendijk, “Nonlinear Programming, Computation-al Methods,” In: J. Abadie Ed., Integer and Nonlinear Programming, North-Holland, Amsterdam, 1970, pp. 37-86.  M. Al-Baali, “Descent Property and Global Conver-gence of the Fletcher–Reeves Method with Inexact Line Search,” IMA Journal of Numerical Analysis, Vol. 5, No. 1, 1985, pp.121-124. doi:10.1093/imanum/5.1.121  M. J. D. Powell, “Nonconvex Minimization Calcula-tions and the Conjugate Gradient Method,” Lecture Notes in Mathematics, Vol. 1066, No. 122, 1984, pp. 121-141.  D. Touati-Ahmed and C. Storey, “Efficient Hybrid Conjugate Gradient Techniques,” Journal of Optimiza-tion Theory and Applications, Vol. 64, No. 2, 1990, pp. 379–397. doi:10.1007/BF00939455  Y. H. Dai and Y. Yuan, “An Efficie nt Hybrid Con jugate Gradient Method for Unconstrained Optimization,” Annals of Operatio ns Research, Vol. 103, No. 1-4, 2001, pp. 33-47. doi:10.1023/A:1012930416777  J. C. Gilbert and J. Nocedal, “Global Convergence Properties of Conjugate Gradient Methods for Optimi-zation,” SIAM Journal Optimization, Vol. 2, No. 1, 1992, pp. 21-42. doi:10.1137/0802003  W. W. Hager and H. Zhang, “A New Conjugate Gra-dient Method with Guaranteed Descent and an Efficient Line Search,” SIAM Journal Optimization, Vol. 16, No. 1, 2005, pp. 170-192. doi:10.1137/030601880  L. Zhang, W. J. Zhou and D. H. Li, “A Descent Mod-ified Polak-Ribière-Polyak Conjugate Gradient Method and Its Global Convergence,” IMA Journal of Numeri-cal Analysis, Vol. 26, No. 4, 2006, pp. 629-640. doi:10.1093/imanum/drl016  L. Zhang, W. J. Zhou and D. H. Li, “Global Conver-gence of a Modified Fletcher-Reeves Conjugate Method with Armijo-Type Line Search,” Numerische Mathema-tik, Vol. 104, No. 4, 2006, pp. 561-572. doi:10.1007/s00211-006-0028-z  L. Zhang, “Nonlinear Conjugate Gradient Methods for Optimization Problems,” Ph.D. Thesis, Hunan Univer-sity, 2006.  L. Zhang and W. J. Zhou, “Two Descent Hybrid Con-jugate Gradient Methods for Optimization,” Journal of Computati onal and Applied Mat hematics, Vol. 216, No. 1, 2008, pp. 251-264. doi:10.1016/j.cam.2007.04.028  P. Wolfe, “Convergence Conditions for Ascent Me-thods,” SIAM Review, Vol. 11, No. 2, 1969, pp. 226-235. doi:10.1137/1011036  W. Hock and K. Schittkowski, “Test Examples for Non-linear Programming Codes,” Journal of Optimization Theory and Applications, Vol. 30, No. 1, 1981, pp. 127-129. doi:10.1007/BF00934594