Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

A family of hybrid conjugate gradient methods for unconstrained optimization


Author: Yu-Hong Dai
Journal: Math. Comp. 72 (2003), 1317-1328
MSC (2000): Primary 49M37, 65K05, 90C30
DOI: https://doi.org/10.1090/S0025-5718-03-01491-1
Published electronically: February 3, 2003
MathSciNet review: 1972738
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Conjugate gradient methods are an important class of methods for unconstrained optimization, especially for large-scale problems. Recently, they have been much studied. This paper proposes a three-parameter family of hybrid conjugate gradient methods. Two important features of the family are that (i) it can avoid the propensity of small steps, namely, if a small step is generated away from the solution point, the next search direction will be close to the negative gradient direction; and (ii) its descent property and global convergence are likely to be achieved provided that the line search satisfies the Wolfe conditions. Some numerical results with the family are also presented.


References [Enhancements On Off] (What's this?)

  • 1. C. G. Broyden, The convergence of a class of double-rank minimization algorithms 1. general considerations , J. Inst. Math. Appl. 6 (1970) 76-90. MR 55:6841
  • 2. R. Byrd, J. Nocedal and Y. Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM J. Numer. Anal. 24 (1987), 1171-1190. MR 88m:65100
  • 3. Y. H. Dai, Convergence properties of nonlinear conjugate gradient methods (II), Research report AMSS-1999-082, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, 1999.
  • 4. Y. H. Dai, New Properties of A Nonlinear Conjugate Gradient Method, Numerische Mathematics 89 : 1 (2001), pp. 83-98. MR 2002f:90118
  • 5. Y. H. Dai, J. Y. Han, G. H. Liu, D. F. Sun, H. X. Yin, and Y. Yuan, Convergence properties of nonlinear conjugate gradient methods, SIAM Journal on Optimization 10 : 2 (1999), pp. 345-358. MR 2001a:90059
  • 6. Y. H. Dai and Y. Yuan, Convergence properties of the Fletcher-Reeves method, IMA Journal of Numerical Analysis 16 : 2 (1996), pp. 155-164. MR 97i:65099
  • 7. Y. H. Dai and Y. Yuan, A class of globally convergent conjugate gradient methods, 1998 (to appear in: Sciences in China, Series A).
  • 8. Y. H. Dai and Y. Yuan, An extended class of nonlinear conjugate gradient methods. In: (D. Li, ed.) Proceedings of the 5th International Conference on Optimization: Techniques and Applications (December 2001, Hong Kong), pp. 778-785.
  • 9. Y. H. Dai and Y. Yuan, A three-parameter family of conjugate gradient methods, Math. Comp. 70 (2001), 1155-1167. MR 2002b:90128
  • 10. Y. H. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM Journal on Optimization 10 : 1 (1999), pp. 177-182. MR 2000i:90074
  • 11. Y. H. Dai and Y. Yuan, An efficient hybrid conjugate gradient method for unconstrained optimization, Ann. Oper. Res. 103 (2001), 33-47.
  • 12. R. Fletcher, Practical Methods of Optimization vol. 1: Unconstrained optimization, John Wiley & Sons (New York), 1987. MR 89j:65050
  • 13. R. Fletcher and C. Reeves, Function minimization by conjugate gradients, Comput. J. 7 (1964), pp. 149-154. MR 32:4827
  • 14. J. C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optimization 2:1 (1992), pp. 21-42. MR 92k:90089
  • 15. M. R. Hestenes and E. L. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards Sect. 5, 49 (1952), 409-436. MR 15:651a
  • 16. Y. Liu and C. Storey, Efficient Generalized Conjugate Gradient Algorithms, Part 1: Theory, Journal of Optimization Theory and Applications, Vol. 69 (1991), 129-137. MR 92e:90077
  • 17. J. J. Moré, B. S. Garbow, and K. E. Hillstrom, Testing unconstrained optimization software, ACM Transactions on Mathematical Software 7 (1981) 17-41. MR 83b:90144
  • 18. L. Nazareth, Conjugate-gradient methods, Encyclopedia of Optimization (C. Floudas and P. Pardalos, eds.), Vol. I, Kluwer, Dordrecht, 2001. MR 2002h:00006
  • 19. M. J. D. Powell, Restart procedures for the conjugate gradient method, Math. Program. 2 (1977), 241-254. MR 57:18099
  • 20. M. J. D. Powell, Nonconvex minimization calculations and the conjugate gradient method, in: Lecture Notes in Mathematics vol. 1066, Springer-Verlag (Berlin) (1984), pp. 122-141. MR 85g:49035
  • 21. E. Polak and G. Ribi$\grave e$re, Note sur la convergence de directions conjug$\acute e$es, Rev. Francaise Informat Recherche Opertionelle, 3e Ann$\acute e$e 16 (1969), pp. 35-43. MR 40:8232
  • 22. B. T. Polyak, The conjugate gradient method in extreme problems, USSR Comp. Math. and Math. Phys. 9 (1969), pp. 94-112. MR 41:2899
  • 23. D. Touati-Ahmed and C. Storey, Efficient hybrid conjugate gradient techniques, J. Optim. Theory Appl. 64 (1990), pp. 379-397. MR 91c:65046
  • 24. G. Zoutendijk, Nonlinear Programming, Computational Methods, in: Integer and Nonlinear Programming (J. Abadie, ed.), 1970, pp. 37-86. MR 55:10015

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 49M37, 65K05, 90C30

Retrieve articles in all journals with MSC (2000): 49M37, 65K05, 90C30


Additional Information

Yu-Hong Dai
Affiliation: State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, P. O. Box 2719, Beijing 100080, Peoples Republic of China
Email: dyh@lsec.cc.ac.cn

DOI: https://doi.org/10.1090/S0025-5718-03-01491-1
Keywords: Unconstrained optimization, conjugate gradient method, line search, descent property, global convergence
Received by editor(s): May 19, 2000
Received by editor(s) in revised form: November 9, 2001
Published electronically: February 3, 2003
Additional Notes: Research partly supported by the Chinese NSF grants 19801033, 10171104 and a Youth Innovation Fund of the Chinese Academy of Sciences
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society