Back
 NS  Vol.3 No.1 , January 2011
A hybrid conjugate gradient method for optimization problems
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 properties: i) This method inherits an important property of the well known PRP method: 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 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 problems.
Cite this paper: Li, X. and Zhao, X. (2011) A hybrid conjugate gradient method for optimization problems. Natural Science, 3, 85-90. doi: 10.4236/ns.2011.31012.
References

[1]   Ahmed, T. and Storey, D. (1990) Efficient hybrid conjugate gradient techniques. Journal of Optimization Theory and Applications, 64, 379-394. doi:10.1007/BF00939455

[2]   Al-Baali, A. (1985) Descent property and global convergence of the Flecher-Reeves method with inexact line search. IMA Journal of Numerical Analysis, 5, 121-124. doi:10.1093/imanum/5.1.121

[3]   Bongartz, K.E., Conn, A.R., Gould, N.I.M. and Toint, P.L. (1995) CUTE: Constrained and unconstrained testing environments. ACM Transactions on Mathematical Software, 21, 123-160. doi:10.1145/200979.201043

[4]   Dai, Y. (2002) A nonmonotone conjugate gradient algorithm for unconstrained optimization. Journal of Systems Science and Complexity, 15, 139-145.

[5]   Dai, Y. and Yuan, Y. (2000) A nonlinear conjugate gradient with a strong global convergence properties. SIAM Journal on Optimization, 10, 177-182. doi:10.1137/S1052623497318992

[6]   Dai, Y. and Yuan, Y. (1998) Nonlinear conjugate gradient methods. Shanghai Scientific and Technical Publishers, Shanghai.

[7]   Dolan, E.D. and Moré, J.J. (2002) Benchmarking optimization software with performance profiles. Mathematical Programming, 91, 201-213. doi:10.1007/s101070100263

[8]   Fletcher, R. (1997) Practical Method of Optimization, Vol I: Unconstrained Optimization. 2nd Edition, Wiley, New York.

[9]   Fletcher, R. and Reeves, C. (1964) Function minimization bu conjugate gradients. Computer Journal, 7, 149-154. doi:10.1093/comjnl/7.2.149

[10]   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

[11]   Grippo, L. and Lucidi, S. (1997) A globally convergent version of the Polak-Ribière gradient method. Mathematical Programming, 78, 375-391. doi:10.1007/BF02614362

[12]   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

[13]   Hestenes, M.R. and Stiefel, E. (1952) Method of conjugate gradient for solving linear equations. Journal of Research National Bureau of Standards, 49, 409-436.

[14]   Hu, Y.F. and Storey, C. (1991) Global convergence result for conjugate method. Journal of Optimization Theory and Applications, 71, 399-405. doi:10.1007/BF00939927

[15]   Li, G., Tang, C. and Wei, Z. (2007) New conjugacy condition 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

[16]   Liu, Y. and Storey, C. (1992) Effcient generalized conjugate gradient algorithms, part 1: theory. Journal of Optimization Theory and Applications, 69, 17-41.

[17]   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

[18]   Polak, E. and Ribiere, G. (1969) Note sur la xonvergence de directions conjugees. Rev. Francaise informat Recherche Operatinelle, 3e Annee, 16, 35-43.

[19]   Powell, M.J.D. (1984) Nonconvex minimization calculations and the conjugate gradient method. Lecture Notes in Mathematics, 1066, 122-141.

[20]   Wei, Z., Li, G. and Qi, L. (2006) New nonlinear conjugate gradient formulas for large-scale unconstrained optimization problems. Applied Mathematics and Computation, 179, 407-430. doi:10.1016/j.amc.2005.11.150

[21]   Wei, Z., Yao, S. and Liu, L. (2006) The convergence properties of some new conjugate gradient methods. Applied Mathematics and Computation, 183, 1341-1350. doi:10.1016/j.amc.2006.05.150

[22]   Yu, G.H. (2007) Nonlinear self-scaling conjugate gradient methods for large-scale optimization problems. Thesis of Doctor’s Degree, Sun Yat-Sen University.

[23]   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

[24]   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.

[25]   Yuan, G.L. and Lu, X.W. (2009) A modified PRP conjugate gradient method. Annals of Operations Research, 166, 73-90. doi:10.1007/s10479-008-0420-4

[26]   Yuan, G.L., Lu, X.W. and Wei, Z.X. (2007) New two-point stepsize gradient methods for solving unconstrained optimization problems. Natural Science Journal of Xiangtan University, 29, 13-15.

[27]   Yuan, Y. and Sun, W. (1999) Theory and Methods of Optimization. Science Press of China, Beijing.

[28]   Yuan, G.L. and Wei, Z.X. (2009) New line search methods for unconstrained optimization. Journal of the Korean Statistical Society, 38, 29-39. doi:10.1016/j.jkss.2008.05.004

[29]   Yuan, G.L. and Wei, Z.X. (2008) The superlinear convergence analysis of a nonmonotone BFGS algorithm on convex objective functions. Acta Mathematica Sinica, 24, 35-42. doi:10.1007/s10114-007-1012-y

[30]   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

[31]   Yuan, G.L. and Wei, Z.X. (2009) A Rank-One fitting method for unconstrained optimization problems. Mathematica Applicata, 22, 118-122.

[32]   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

[33]   Zhang, L., Zhou, W. and Li, D. (2006) A descent modified Polak-Ribiére-Polyak conjugate method and its global convergence. IMA Journal on Numerical Analysis, 26, 629-649. doi:10.1093/imanum/drl016

[34]   Zoutendijk, G. (1970) Nonlinear programming computational methods. In: Abadie, J. Ed., Integer and Nonlinear Programming, NorthHolllad, Amsterdam, 37-86.

 
 
Top