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
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
- MR Author ID: 620453
- Email: dyh@lsec.cc.ac.cn
- 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
- © Copyright 2003 American Mathematical Society
- Journal: Math. Comp. 72 (2003), 1317-1328
- MSC (2000): Primary 49M37, 65K05, 90C30
- DOI: https://doi.org/10.1090/S0025-5718-03-01491-1
- MathSciNet review: 1972738