×

Nonlinear conjugate gradient methods with sufficient descent condition for large-scale unconstrained optimization. (English) Zbl 1184.65066

Summary: Two nonlinear conjugate gradient-type methods for solving unconstrained optimization problems are proposed. An attractive property of the methods, is that, without any line search, the generated directions always descend. Under some mild conditions, global convergence results for both methods are established. Preliminary numerical results show that these proposed methods are promising, and competitive with the well-known PRP method.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming

Software:

SCALCG; CUTEr; CUTE
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Y. H. Dai and Y. Yuan, “A nonlinear conjugate gradient method with a strong global convergence property,” SIAM Journal on Optimization, vol. 10, no. 1, pp. 177-182, 2000. · Zbl 0957.65061 · doi:10.1137/S1052623497318992
[2] R. Fletcher and C. M. Reeves, “Function minimization by conjugate gradients,” The Computer Journal, vol. 7, pp. 149-154, 1964. · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149
[3] M. R. Hestenes and E. Stiefel, “Methods of conjugate gradient for solving linear systems,” Journal of Research of the National Bureau of Standards, vol. 49, pp. 409-436, 1952. · Zbl 0048.09901
[4] E. Polak and G. Ribière, “Note sur la convergence de directions conjugées,” Revue Francaise d’Informatique et de Recherche Operationnelle, vol. 16, pp. 35-43, 1969. · Zbl 0174.48001
[5] M. Al-Baali, “Descent property and global convergence of the Fletcher-Reeves method with inexact line search,” IMA Journal of Numerical Analysis, vol. 5, no. 1, pp. 121-124, 1985. · Zbl 0578.65063 · doi:10.1093/imanum/5.1.121
[6] Y. H. Dai and Y. Yuan, “Convergence properties of the Fletcher-Reeves method,” IMA Journal of Numerical Analysis, vol. 16, no. 2, pp. 155-164, 1996. · Zbl 0851.65049 · doi:10.1093/imanum/16.2.155
[7] W. W. Hager and H. Zhang, “A survey of nonlinear conjugate gradient methods,” Pacific Journal of Optimization, vol. 2, pp. 35-58, 2006. · Zbl 1117.90048
[8] J. C. Gilbert and J. Nocedal, “Global convergence properties of conjugate gradient methods for optimization,” SIAM Journal on Optimization, vol. 2, no. 1, pp. 21-42, 1992. · Zbl 0767.90082 · doi:10.1137/0802003
[9] L. Grippo and S. Lucidi, “A globally convergent version of the Polak-Ribière conjugate gradient method,” Mathematical Programming, vol. 78, no. 3, pp. 375-391, 1997. · Zbl 0887.90157 · doi:10.1007/BF02614362
[10] L. Grippo and S. Lucidi, “Convergence conditions, line search algorithms and trust region implementations for the Polak-Ribière conjugate gradient method,” Optimization Methods & Software, vol. 20, no. 1, pp. 71-98, 2005. · Zbl 1087.90086 · doi:10.1080/1055678042000208570
[11] J. Sun and J. Zhang, “Global convergence of conjugate gradient methods without line search,” Annals of Operations Research, vol. 103, pp. 161-173, 2001. · Zbl 1014.90071 · doi:10.1023/A:1012903105391
[12] Z. Wei, G. Y. Li, and L. Qi, “Global convergence of the Polak-Ribière-Polyak conjugate gradient method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems,” Mathematics of Computation, vol. 77, no. 264, pp. 2173-2193, 2008. · Zbl 1198.65091 · doi:10.1090/S0025-5718-08-02031-0
[13] L. Zhang, W. Zhou, and D. Li, “Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search,” Numerische Mathematik, vol. 104, no. 4, pp. 561-572, 2006. · Zbl 1103.65074 · doi:10.1007/s00211-006-0028-z
[14] M. J. D. Powell, “Nonconvex minimization calculations and the conjugate gradient method,” in Numerical Analysis (Dundee, 1983), vol. 1066 of Lecture Notes in Mathematics, pp. 122-141, Springer, Berlin, Germany, 1984. · Zbl 0531.65035 · doi:10.1007/BFb0099521
[15] N. Andrei, “Scaled conjugate gradient algorithms for unconstrained optimization,” Computational Optimization and Applications, vol. 38, no. 3, pp. 401-416, 2007. · Zbl 1168.90608 · doi:10.1007/s10589-007-9055-7
[16] N. Andrei, “Another nonlinear conjugate gradient algorithm for unconstrained optimization,” Optimization Methods & Software, vol. 24, no. 1, pp. 89-104, 2009. · Zbl 1154.90586 · doi:10.1080/10556780802393326
[17] E. G. Birgin and J. M. Martínez, “A spectral conjugate gradient method for unconstrained optimization,” Applied Mathematics and Optimization, vol. 43, no. 2, pp. 117-128, 2001. · Zbl 0990.90134 · doi:10.1007/s00245-001-0003-0
[18] Y.-H. Dai and L.-Z. Liao, “New conjugacy conditions and related nonlinear conjugate gradient methods,” Applied Mathematics and Optimization, vol. 43, no. 1, pp. 87-101, 2001. · Zbl 0973.65050 · doi:10.1007/s002450010019
[19] W. W. Hager and H. Zhang, “A new conjugate gradient method with guaranteed descent and an efficient line search,” SIAM Journal on Optimization, vol. 16, no. 1, pp. 170-192, 2005. · Zbl 1093.90085 · doi:10.1137/030601880
[20] G. Li, C. Tang, and Z. Wei, “New conjugacy condition and related new conjugate gradient methods for unconstrained optimization,” Journal of Computational and Applied Mathematics, vol. 202, no. 2, pp. 523-539, 2007. · Zbl 1116.65069 · doi:10.1016/j.cam.2006.03.005
[21] Z. Wei, G. Li, and L. Qi, “New quasi-Newton methods for unconstrained optimization problems,” Applied Mathematics and Computation, vol. 175, no. 2, pp. 1156-1188, 2006. · Zbl 1100.65054 · doi:10.1016/j.amc.2005.08.027
[22] L. Zhang, W. Zhou, and D.-H. Li, “A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence,” IMA Journal of Numerical Analysis, vol. 26, no. 4, pp. 629-640, 2006. · Zbl 1106.65056 · doi:10.1093/imanum/drl016
[23] L. Liu, S. Yao, and Z. Wei, “The global and superlinear convergence of a new nonmonotone MBFGS algorithm on convex objective functions,” Journal of Computational and Applied Mathematics, vol. 220, no. 1-2, pp. 422-438, 2008. · Zbl 1152.65068 · doi:10.1016/j.cam.2007.08.017
[24] Z. Wei, G. Yu, G. Yuan, and Z. Lian, “The superlinear convergence of a modified BFGS-type method for unconstrained optimization,” Computational Optimization and Applications, vol. 29, no. 3, pp. 315-332, 2004. · Zbl 1070.90089 · doi:10.1023/B:COAP.0000044184.25410.39
[25] Y. Xiao, Z. Wei, and Z. Wang, “A limited memory BFGS-type method for large-scale unconstrained optimization,” Computers & Mathematics with Applications, vol. 56, no. 4, pp. 1001-1009, 2008. · Zbl 1155.90441 · doi:10.1016/j.camwa.2008.01.028
[26] J. Zhang, N. Y. Deng, and L. H. Chen, “New quasi-Newton equation and related methods for unconstrained optimization,” Journal of Optimization Theory and Applications, vol. 102, no. 1, pp. 147-167, 1999. · Zbl 0991.90135 · doi:10.1023/A:1021898630001
[27] H. Yabe and M. Takano, “Global convergence properties of nonlinear conjugate gradient methods with modified secant condition,” Computational Optimization and Applications, vol. 28, no. 2, pp. 203-225, 2004. · Zbl 1056.90130 · doi:10.1023/B:COAP.0000026885.81997.88
[28] L. Nazareth, “A conjugate direction algorithm without line searches,” Journal of Optimization Theory and Applications, vol. 23, no. 3, pp. 373-387, 1977. · Zbl 0348.65061 · doi:10.1007/BF00933447
[29] G. Zoutendijk, “Nonlinear programming, computational methods,” in Integer and Nonlinear Programming, J. Jabadie, Ed., pp. 37-86, North-Holland, Amsterdam, The Netherlands, 1970. · Zbl 0336.90057
[30] W. Sun and Y. Yuan, Optimization Theory and Methods: Nonlinear Programming, vol. 1 of Springer Optimization and Its Applications, Springer, New York, NY, USA, 2006. · Zbl 1129.90002
[31] I. Bongartz, A. R. Conn, N. Gould, and P. L. Toint, “CUTE: constrained and unconstrained testing environment,” ACM Transactions on Mathematical Software, vol. 21, no. 1, pp. 123-160, 1995. · Zbl 0886.65058 · doi:10.1145/200979.201043
[32] E. D. Dolan and J. J. Moré, “Benchmarking optimization software with performance profiles,” Mathematical Programming, vol. 91, no. 2, pp. 201-213, 2002. · Zbl 1049.90004 · doi:10.1007/s101070100263
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.