A three-parameter family of nonlinear conjugate gradient methods

Dai, Y.; Yuan, Y.

doi:10.1090/S0025-5718-00-01253-9

A three-parameter family of nonlinear conjugate gradient methods
HTML articles powered by AMS MathViewer

by Y. H. Dai and Y. Yuan PDF

Math. Comp. 70 (2001), 1155-1167 Request permission

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

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, DOI 10.1093/imanum/5.1.121
A. Buckley and A. Lenir, QN-like variable storage conjugate gradients, Math. Programming 27 (1983), no. 2, 155–175. MR 718057, DOI 10.1007/BF02591943
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.
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.
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).
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).
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, DOI 10.1093/imanum/16.2.155
Y. H. Dai and Y. Yuan, Convergence properties of the conjugate descent method, Mathematical Advances Vol. 25 No. 6 (1996), 552-562.
Ya-xiang Yuan (ed.), Advances in nonlinear programming, Applied Optimization, vol. 14, Kluwer Academic Publishers, Dordrecht, 1998. MR 1639715, DOI 10.1007/978-1-4613-3335-7
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.
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.
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.
James W. Daniel, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal. 4 (1967), 10–26. MR 217987, DOI 10.1137/0704002
R. Fletcher, Practical methods of optimization. Vol. 1, A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1980. Unconstrained optimization. MR 585160
R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, Comput. J. 7 (1964), 149–154. MR 187375, DOI 10.1093/comjnl/7.2.149
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, DOI 10.1137/0802003
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, DOI 10.1016/S0025-5610(97)00002-6
Sam Perlis, Maximal orders in rational cyclic algebras of composite degree, Trans. Amer. Math. Soc. 46 (1939), 82–96. MR 15, DOI 10.1090/S0002-9947-1939-0000015-X
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, DOI 10.1007/BF00939927
K. M. Khoda, Y. Liu, and C. Storey, Generalized Polak-Ribir̀e Algorithm, Journal of Optimization Theory and Applications, Vol. 75, No. 2 (1992), 345-354.
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, DOI 10.1007/BF02663897
Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms. I. Theory, J. Optim. Theory Appl. 69 (1991), no. 1, 129–137. MR 1104590, DOI 10.1007/BF00940464
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).
M. J. D. Powell, Restart procedures for the conjugate gradient method, Math. Programming 12 (1977), no. 2, 241–254. MR 478622, DOI 10.1007/BF01593790
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, DOI 10.1007/BFb0099521
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
B. T. Poljak, A method of conjugate gradients in extremum problems, Ž. Vyčisl. Mat i Mat. Fiz. 9 (1969), 807–821 (Russian). MR 258252
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)
David F. Shanno, Conjugate gradient methods with inexact searches, Math. Oper. Res. 3 (1978), no. 3, 244–256. MR 506662, DOI 10.1287/moor.3.3.244
D. Touati-Ahmed and C. Storey, Efficient hybrid conjugate gradient techniques, J. Optim. Theory Appl. 64 (1990), no. 2, 379–397. MR 1042002, DOI 10.1007/BF00939455
C. Y. Wang and Y. Z. Zhang, Global convergence properties of $s$-related conjugate gradient methods, Report, Qufu Normal University, 1996.