×

zbMATH — the first resource for mathematics

Global convergence of the Polak-Ribière-Polyak conjugate gradient method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems. (English) Zbl 1198.65091
Summary: We propose two algorithms for nonconvex unconstrained optimization problems that employ Polak-Ribière-Polyak conjugate gradient formula and new inexact line search techniques. We show that the new algorithms converge globally if the function to be minimized has Lipschitz continuous gradients. Preliminary numerical results show that the proposed methods for particularly chosen line search conditions are very promising.

MSC:
65H10 Numerical computation of solutions to systems of equations
90C26 Nonconvex programming, global optimization
Software:
minpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Larry Armijo, Minimization of functions having Lipschitz continuous first partial derivatives, Pacific J. Math. 16 (1966), 1 – 3. · Zbl 0202.46105
[2] 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. · Zbl 0578.65063 · doi:10.1093/imanum/5.1.121 · doi.org
[3] Xiongda Chen and Jie Sun, Global convergence of a two-parameter family of conjugate gradient methods without line search, J. Comput. Appl. Math. 146 (2002), no. 1, 37 – 45. Sino-Japan Optimization Meeting (Hong Kong, 2000). · Zbl 1018.65081 · doi:10.1016/S0377-0427(02)00416-8 · doi.org
[4] Yu-hong Dai, Convergence of nonlinear conjugate gradient methods, J. Comput. Math. 19 (2001), no. 5, 539 – 548. · Zbl 1008.65039
[5] Y. Dai, J. Han, G. Liu, D. Sun, H. Yin and Y. Yan, Convergence properties of nonlinear conjugate methods, SIAM Journal of Optimization, 2 (1999), pp. 345-358. · Zbl 0957.65062
[6] Y. Dai, Convergence of Polak-Ribière-Polyak conjugate gradient method with constant stepsizes, Manuscript, Institute of Computational Mathematics abd Scientific/Engineering Computing, Chinese Academy of Sciences, 2001.
[7] Yu-hong Dai and Qin Ni, Testing different conjugate gradient methods for large-scale unconstrained optimization, J. Comput. Math. 21 (2003), no. 3, 311 – 320. · Zbl 1041.65048
[8] 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. · Zbl 0957.65061 · doi:10.1137/S1052623497318992 · doi.org
[9] Y. Dai and Y. Yuan, Further studies on the Polak-Ribière-Polyak method, Research Report ICM-95-040, Institute of Computational Mathematics and Scientific/ Engineering Computing, Chinese Academy of Sciences, 1995.
[10] Yuhong Dai and Yaxiang Yuan, Convergence properties of the conjugate descent method, Adv. in Math. (China) 25 (1996), no. 6, 552 – 562 (English, with English and Chinese summaries). · Zbl 0871.49028
[11] Y. H. Dai and Y. Yuan, An efficient hybrid conjugate gradient method for unconstrained optimization, Ann. Oper. Res. 103 (2001), 33 – 47. Optimization and numerical algebra (Nanjing, 1999). · Zbl 1007.90065 · doi:10.1023/A:1012930416777 · doi.org
[12] Y. Dai and Y. Yuan, Nonlinear Conjugate Gradient Methods, Science Press of Shanghai, 2000.
[13] R. Fletcher, Practical methods of optimization. Vol. 1, John Wiley & Sons, Ltd., Chichester, 1980. Unconstrained optimization; A Wiley-Interscience Publication. R. Fletcher, Practical methods of optimization. Vol. 2, John Wiley & Sons, Ltd., Chichester, 1981. Constrained optimization; A Wiley-Interscience Publication. · Zbl 0439.93001
[14] R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, Comput. J. 7 (1964), 149 – 154. · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149 · doi.org
[15] Jean Charles Gilbert and Jorge Nocedal, Global convergence properties of conjugate gradient methods for optimization, SIAM J. Optim. 2 (1992), no. 1, 21 – 42. · Zbl 0767.90082 · doi:10.1137/0802003 · doi.org
[16] L. Grippo, F. Lampariello, and S. Lucidi, A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal. 23 (1986), no. 4, 707 – 716. · Zbl 0616.65067 · doi:10.1137/0723046 · doi.org
[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. · Zbl 0887.90157 · doi:10.1016/S0025-5610(97)00002-6 · doi.org
[18] Andreas Griewank, On automatic differentiation, Mathematical programming (Tokyo, 1988) Math. Appl. (Japanese Ser.), vol. 6, SCIPRESS, Tokyo, 1989, pp. 83 – 107. · Zbl 0696.65015
[19] Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409 – 436 (1953). · Zbl 0048.09901
[20] Li Zhang, Weijun Zhou, and Dong-Hui Li, A descent modified Polak-Ribière-Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal. 26 (2006), no. 4, 629 – 640. · Zbl 1106.65056 · doi:10.1093/imanum/drl016 · doi.org
[21] Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms. I. Theory, J. Optim. Theory Appl. 69 (1991), no. 1, 129 – 137. · Zbl 0702.90077 · doi:10.1007/BF00940464 · doi.org
[22] Garth P. McCormick, A modification of Armijo’s step-size rule for negative curvature, Math. Programming 13 (1977), no. 1, 111 – 115. · Zbl 0367.90100 · doi:10.1007/BF01584328 · doi.org
[23] Jorge J. Moré, Burton S. Garbow, and Kenneth E. Hillstrom, Testing unconstrained optimization software, ACM Trans. Math. Software 7 (1981), no. 1, 17 – 41. · Zbl 0454.65049 · doi:10.1145/355934.355936 · doi.org
[24] Jorge Nocedal, Theory of algorithms for unconstrained optimization, Acta numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992, pp. 199 – 242. · Zbl 0766.65051
[25] Jorge Nocedal, Conjugate gradient methods and nonlinear optimization, Linear and nonlinear conjugate gradient-related methods (Seattle, WA, 1995) SIAM, Philadelphia, PA, 1996, pp. 9 – 23. · Zbl 0866.65037
[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). · Zbl 0174.48001
[27] B. T. Polyak, The conjugate gradient method in extreme problems, USSR Comp. Math. and Math. Phys., 9 (1969), pp. 94-112. · Zbl 0229.49023
[28] 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. · Zbl 0531.65035 · doi:10.1007/BFb0099521 · doi.org
[29] H. Qi, J. Han and G. Liu, A modification of Hestenes-Stiefel conjugate gradient method, Chinese Annals of Mathematics, 3 (1996), pp. 177-184.
[30] Jie Sun and Jiapu Zhang, Global convergence of conjugate gradient methods without line search, Ann. Oper. Res. 103 (2001), 161 – 173. Optimization and numerical algebra (Nanjing, 1999). · Zbl 1014.90071 · doi:10.1023/A:1012903105391 · doi.org
[31] Z. Wei, L. Qi, and X. Chen, An SQP-type method and its application in stochastic programs, J. Optim. Theory Appl. 116 (2003), no. 1, 205 – 228. · Zbl 1030.90142 · doi:10.1023/A:1022122521816 · doi.org
[32] Z. Wei, L. Qi and S. Ito, New step-size rules for optimization problems, Department of Mathematics and Information Science, Guangxi University, Nanning, Guangxin, P. R. China, October, 2000.
[33] Y. Yuan and W. Sun, Theory and Methods of Optimization, Science Press of China, 1999.
[34] G. Zoutendijk, Nonlinear programming, computational methods, Integer and nonlinear programming, North-Holland, Amsterdam, 1970, pp. 37 – 86. · Zbl 0336.90057
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.