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