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 Free Access

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), no. 1, 121–124. MR 777963, https://doi.org/10.1093/imanum/5.1.121
  • 2. A. Buckley and A. Lenir, QN-like variable storage conjugate gradients, Math. Programming 27 (1983), no. 2, 155–175. MR 718057, https://doi.org/10.1007/BF02591943
  • 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. 16 (1996), no. 2, 155–164. MR 1382713, https://doi.org/10.1093/imanum/16.2.155
  • 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. Ya-xiang Yuan (ed.), Advances in nonlinear programming, Applied Optimization, vol. 14, Kluwer Academic Publishers, Dordrecht, 1998. MR 1639715
  • 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. James W. Daniel, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal. 4 (1967), 10–26. MR 0217987, https://doi.org/10.1137/0704002
  • 14. R. Fletcher, Practical methods of optimization. Vol. 1, John Wiley & Sons, Ltd., Chichester, 1980. Unconstrained optimization; A Wiley-Interscience Publication. MR 585160
    R. Fletcher, Practical methods of optimization. Vol. 2, John Wiley & Sons, Ltd., Chichester, 1981. Constrained optimization; A Wiley-Interscience Publication. MR 633058
  • 15. R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, Comput. J. 7 (1964), 149–154. MR 0187375, https://doi.org/10.1093/comjnl/7.2.149
  • 16. Jean Charles Gilbert and Jorge Nocedal, Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim. 2 (1992), no. 1, 21–42. MR 1147881, https://doi.org/10.1137/0802003
  • 17. L. Grippo and S. Lucidi, A globally convergent version of the Polak-Ribière conjugate gradient method, Math. Programming 78 (1997), no. 3, Ser. A, 375–391. MR 1466138, https://doi.org/10.1016/S0025-5610(97)00002-6
  • 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. 71 (1991), no. 2, 399–405. MR 1131466, https://doi.org/10.1007/BF00939927
  • 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. Guang Hui Liu, Ji Ye Han, and Hong Xia Yin, Global convergence of the Fletcher-Reeves algorithm with inexact linesearch, Appl. Math. J. Chinese Univ. Ser. B 10 (1995), no. 1, 75–82. A Chinese summary appears in Gaoxiao Yingyong Shuxue Xuebao Ser. A 10 (1995), no. 1, 126. MR 1335968, https://doi.org/10.1007/BF02663897
  • 22. Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms. I. Theory, J. Optim. Theory Appl. 69 (1991), no. 1, 129–137. MR 1104590, https://doi.org/10.1007/BF00940464
  • 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 for the conjugate gradient method, Math. Programming 12 (1977), no. 2, 241–254. MR 0478622, https://doi.org/10.1007/BF01593790
  • 25. M. J. D. Powell, Nonconvex minimization calculations and the conjugate gradient method, Numerical analysis (Dundee, 1983) Lecture Notes in Math., vol. 1066, Springer, Berlin, 1984, pp. 122–141. MR 760460, https://doi.org/10.1007/BFb0099521
  • 26. E. Polak and G. Ribière, Note sur la convergence de méthodes de directions conjuguées, Rev. Française Informat. Recherche Opérationnelle 3 (1969), no. 16, 35–43 (French, with Loose English summary). MR 0255025
  • 27. B. T. Poljak, A method of conjugate gradients in extremum problems, Ž. Vyčisl. Mat. i Mat. Fiz. 9 (1969), 807–821 (Russian). MR 0258252
  • 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. David F. Shanno, Conjugate gradient methods with inexact searches, Math. Oper. Res. 3 (1978), no. 3, 244–256. MR 506662, https://doi.org/10.1287/moor.3.3.244
  • 30. D. Touati-Ahmed and C. Storey, Efficient hybrid conjugate gradient techniques, J. Optim. Theory Appl. 64 (1990), no. 2, 379–397. MR 1042002, https://doi.org/10.1007/BF00939455
  • 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