Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Global convergence of the Polak-Ribière-Polyak conjugate gradient method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems

Authors: Zeng Xin Wei, Guo Yin Li and Li Qun Qi
Journal: Math. Comp. 77 (2008), 2173-2193
MSC (2000): Primary 65H10, 90C26
Published electronically: June 11, 2008
MathSciNet review: 2429880
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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.

References [Enhancements On Off] (What's this?)

  • 1. Larry Armijo, Minimization of functions having Lipschitz continuous first partial derivatives, Pacific J. Math. 16 (1966), 1–3. MR 0191071
  • 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. MR 777963, 10.1093/imanum/5.1.121
  • 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). MR 1923444, 10.1016/S0377-0427(02)00416-8
  • 4. Yu-hong Dai, Convergence of nonlinear conjugate gradient methods, J. Comput. Math. 19 (2001), no. 5, 539–548. MR 1851852
  • 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.
  • 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. MR 1978635
  • 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. MR 1740963, 10.1137/S1052623497318992
  • 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). MR 1453164
  • 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). MR 1868442, 10.1023/A:1012930416777
  • 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. MR 585160
  • 14. R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, Comput. J. 7 (1964), 149–154. MR 0187375
  • 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. MR 1147881, 10.1137/0802003
  • 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. MR 849278, 10.1137/0723046
  • 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. MR 1466138, 10.1016/S0025-5610(97)00002-6
  • 18. Andreas Griewank, On automatic differentiation, Mathematical programming (Tokyo, 1988) Math. Appl. (Japanese Ser.), vol. 6, SCIPRESS, Tokyo, 1989, pp. 83–107. MR 1114312
  • 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). MR 0060307
  • 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. MR 2263891, 10.1093/imanum/drl016
  • 21. Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms. I. Theory, J. Optim. Theory Appl. 69 (1991), no. 1, 129–137. MR 1104590, 10.1007/BF00940464
  • 22. Garth P. McCormick, A modification of Armijo’s step-size rule for negative curvature, Math. Programming 13 (1977), no. 1, 111–115. MR 0461907
  • 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. MR 607350, 10.1145/355934.355936
  • 24. Jorge Nocedal, Theory of algorithms for unconstrained optimization, Acta numerica, 1992, Acta Numer., Cambridge Univ. Press, Cambridge, 1992, pp. 199–242. MR 1165726
  • 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. MR 1446295
  • 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). MR 0255025
  • 27. B. T. Polyak, The conjugate gradient method in extreme problems, USSR Comp. Math. and Math. Phys., 9 (1969), pp. 94-112.
  • 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. MR 760460, 10.1007/BFb0099521
  • 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). MR 1868449, 10.1023/A:1012903105391
  • 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. MR 1961035, 10.1023/A:1022122521816
  • 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. MR 0437081

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65H10, 90C26

Retrieve articles in all journals with MSC (2000): 65H10, 90C26

Additional Information

Zeng Xin Wei
Affiliation: Department of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, People’s Republic of China

Guo Yin Li
Affiliation: Department of Mathematics and Information Science, Guangxi University, Nanning, Guangxi, People’s Republic of China
Address at time of publication: Department of Applied Mathematics, The University of New South Wales, Australia

Li Qun Qi
Affiliation: Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

Keywords: Inexact line search, PRP method, nonconvex optimization, global convergence.
Received by editor(s): May 12, 2003
Received by editor(s) in revised form: June 12, 2004
Published electronically: June 11, 2008
Additional Notes: The first author’s work was done during his visit to the Department of Applied Mathematics, Hong Kong Polytechnic University, Kowloon, Hong Kong and was supported by the Groucher Foundation of Hong Kong, Chinese NSF grant 10161002 and Guangxi NSF grant 0542043
The third author’s work was supported by the Research Grant Council of Hong Kong
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.