Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

A three-parameter family of nonlinear conjugate gradient methods


Authors: Y. H. Dai and Y. Yuan
Journal: Math. Comp. 70 (2001), 1155-1167
MSC (2000): Primary 49M37, 65K05, 90C30
DOI: https://doi.org/10.1090/S0025-5718-00-01253-9
Published electronically: March 28, 2000
MathSciNet review: 1826579
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract:

In this paper, we propose a three-parameter family of conjugate gradient methods for unconstrained optimization. The three-parameter family of methods not only includes the already existing six practical nonlinear conjugate gradient methods, but subsumes some other families of nonlinear conjugate gradient methods as its subfamilies. With Powell's restart criterion, the three-parameter family of methods with the strong Wolfe line search is shown to ensure the descent property of each search direction. Some general convergence results are also established for the three-parameter family of methods. This paper can also be regarded as a brief review on nonlinear conjugate gradient methods.


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

  • 1. M. Al-Baali, Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA J. Numer. Anal. 5 (1985), pp. 121-124. MR 86d:49043
  • 2. A. Buckley and A. Lenir, QN-like variable storage conjugate gradients, Math. Prog. 27 (1983), 155-175. MR 85a:49043
  • 3. Y. H. Dai, Analyses of nonlinear conjugate gradient method, Ph.D. thesis, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1997.
  • 4. Y. H. Dai, Some new properties of a nonlinear conjugate gradient method, Research report ICM-98-010, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1998.
  • 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, Research report ICM-98-024, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1998 (accepted by SIAM J. Optimization).
  • 6. Y. H. Dai and Y. Yuan, A Nonlinear Conjugate Gradient Method with Nice Global Convergence Properties, Research report ICM-95-038, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1995 (accepted by SIAM J. Optimization).
  • 7. Y. H. Dai and Y. Yuan, Convergence properties of the Fletcher-Reeves method, IMA J. Numer. Anal. Vol. 16 No. 2 (1996), 155-164. MR 97i:65099
  • 8. Y. H. Dai and Y. Yuan, Convergence properties of the conjugate descent method, Mathematical Advances Vol. 25 No. 6 (1996), 552-562. CMP 97:13
  • 9. Y. H. Dai and Y. Yuan, Some properties of a new conjugate gradient method, in: Y. Yuan ed., Advances in Nonlinear Programming (Kluwer, Boston, 1998), pp. 251-262. MR 99b:90004
  • 10. Y. H. Dai and Y. Yuan, Convergence properties of Beale-Powell restart method, Sciences in China (series A), Vol. 28, No. 5, pp. 424-432.
  • 11. Y. H. Dai and Y. Yuan, A class of globally convergent conjugate gradient methods, Research report ICM-98-030, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1998.
  • 12. Y. H. Dai and Y. Yuan, Extension of a class of conjugate gradient methods, Research report ICM-98-049, Institute of Computational Mathematics and Scientific/Engineering Computing, Chinese Academy of Sciences, 1998.
  • 13. J. W. Daniel, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal., 4 (1967), 10-26. MR 36:1076
  • 14. R. Fletcher, Practical Methods of Optimization vol. 1: Unconstrained optimization, John Wiley & Sons (New York), 1987. MR 83i:65055a
  • 15. R. Fletcher and C. Reeves, Function minimization by conjugate gradients, Comput. J. 7 (1964), pp. 149-154. MR 32:4827
  • 16. J. C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization, SIAM. J. Optimization. Vol. 2 No. 1 (1992), pp. 21-42. MR 92k:90089
  • 17. L. Grippo and S. Lucidi, A globally convergent version of the Polak-Ribi$\grave e$re conjugate gradient method, Math. Prog. 78 (1997), pp. 375-391. MR 98k:90080
  • 18. 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
  • 19. Y. F. Hu and C. Storey, Global convergence result for conjugate gradient methods, J. Optim. Theory Appl. Vol. 71 No. 2 (1991) 399-405. MR 92i:90095
  • 20. K. M. Khoda, Y. Liu, and C. Storey, Generalized Polak-Ribire Algorithm, Journal of Optimization Theory and Applications, Vol. 75, No. 2 (1992), 345-354. CMP 93:04
  • 21. G. H. Liu, J. Y. Han, and H. X. Yin, Global convergence of the Fletcher-Reeves algorithm with an inexact line search, Appl. Math. J. Chinese Univ. Ser. B, 10 (1995), 75-82. MR 96b:90086
  • 22. 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
  • 23. L. Nazareth, Conjugate-gradient methods, to appear in: Encyclopedia of Optimization (C. Floudas and P. Pardalos, eds.), Kluwer Academic Publishers, Boston, USA and Dordrecht, The Netherlands (1999).
  • 24. M. J. D. Powell, Restart procedures of the conjugate gradient method, Math. Program. 2 (1977), pp. 241-254. MR 57:18099
  • 25. 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
  • 26. E. Polak and G. Ribi$\grave e$re, Note sur la convergence de directions conjug$\acute e$es, Rev. Francaise Informat Recherche Operationelle, 3e Ann$\acute e$e 16 (1969), pp. 35-43. MR 40:8232
  • 27. B. T. Polyak, The conjugate gradient method in extreme problems, USSR Comp. Math. and Math. Phys. 9 (1969), pp. 94-112. MR 41:2899
  • 28. H. D. Qi, J. Y. Han and G. H. Liu, A modified Hestenes-Stiefel conjugate gradient algorithm, Chinese Annals of Mathematics 17A : 3 (1996), 277-284. (in Chinese) CMP 97:07
  • 29. D. F. Shanno, Conjugate gradient methods with inexact searches, Math. Oper. Res. 3 (1978), 244-256. MR 80d:65082
  • 30. D. Touati-Ahmed and C. Storey, Efficient hybrid conjugate gradient techniques, J. Optimization Theory Appl. 64 (1990) 379-397. MR 91c:65046
  • 31. C. Y. Wang and Y. Z. Zhang, Global convergence properties of $s$-related conjugate gradient methods, Report, Qufu Normal University, 1996.

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

Y. H. Dai
Affiliation: State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, P. O. Box 2719, Beijing 100080, China
Email: dyh@lsec.cc.ac.cn

Y. Yuan
Affiliation: State Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, P. O. Box 2719, Beijing 100080, China
Email: yyx@lsec.cc.ac.cn

DOI: https://doi.org/10.1090/S0025-5718-00-01253-9
Keywords: Unconstrained optimization, conjugate gradient methods, line search, global convergence.
Received by editor(s): January 22, 1999
Received by editor(s) in revised form: September 7, 1999
Published electronically: March 28, 2000
Additional Notes: Research partly supported by Chinese NSF grants 19525101, 19731010 and 19801033.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society