A family of hybrid conjugate gradient methods for unconstrained optimization

Dai, Yu-Hong

doi:10.1090/S0025-5718-03-01491-1

A family of hybrid conjugate gradient methods for unconstrained optimization
HTML articles powered by AMS MathViewer

by Yu-Hong Dai PDF

Math. Comp. 72 (2003), 1317-1328 Request permission

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

C. G. Broyden, The convergence of a class of double-rank minimization algorithms. II. The new algorithm, J. Inst. Math. Appl. 6 (1970), 222–231. MR 433870
Richard H. Byrd, Jorge Nocedal, and Ya Xiang Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM J. Numer. Anal. 24 (1987), no. 5, 1171–1190. MR 909072, DOI 10.1137/0724077
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.
Yu-Hong Dai, New properties of a nonlinear conjugate gradient method, Numer. Math. 89 (2001), no. 1, 83–98. MR 1846765, DOI 10.1007/PL00005464
Yuhong Dai, Jiye Han, Guanghui Liu, Defeng Sun, Hongxia Yin, and Ya-Xiang Yuan, Convergence properties of nonlinear conjugate gradient methods, SIAM J. Optim. 10 (2000), no. 2, 345–358. MR 1740949, DOI 10.1137/S1052623494268443
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, A class of globally convergent conjugate gradient methods, 1998 (to appear in: Sciences in China, Series A).
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.
Y. H. Dai and Y. Yuan, A three-parameter family of nonlinear conjugate gradient methods, Math. Comp. 70 (2001), no. 235, 1155–1167. MR 1826579, DOI 10.1090/S0025-5718-00-01253-9
Y. H. Dai and Y. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim. 10 (1999), no. 1, 177–182. MR 1740963, DOI 10.1137/S1052623497318992
Y. H. Dai and Y. Yuan, An efficient hybrid conjugate gradient method for unconstrained optimization, Ann. Oper. Res. 103 (2001), 33–47.
R. Fletcher, Practical methods of optimization, 2nd ed., A Wiley-Interscience Publication, John Wiley & Sons, Ltd., Chichester, 1987. MR 955799
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
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. 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
Jorge J. Moré, Burton S. Garbow, and Kenneth E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software 7 (1981), no. 1, 17–41. MR 607350, DOI 10.1145/355934.355936
C. A. Floudas and P. M. Pardalos (eds.), Encyclopedia of optimization. Vol. I–VI, Kluwer Academic Publishers, Dordrecht, 2001. MR 1865755, DOI 10.1007/0-306-48332-7
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
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
G. Zoutendijk, Nonlinear programming, computational methods, Integer and nonlinear programming, North-Holland, Amsterdam, 1970, pp. 37–86. MR 0437081