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
DOI: https://doi.org/10.1090/S0025-5718-08-02031-0
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. L. Armijo, Minimization of functions having Lipschitz conditions partial derivatives, Pacific Journal of Mathematics, 16 (1966), pp. 1-3. MR 0191071 (32:8480)
  • 2. A. Al-Baali, Descent property and global convergence of the Fletcher-Reeves method with inexact line search, IMA J. Numer. Anal, 5 (1985), pp. 121-124 . MR 777963 (86d:49043)
  • 3. X. Chen and J. Sun, Global convergence of a two-parameter family of conjugate gradient methods without line search, J. Comput. Appl. Math. 146 (2002), pp. 37-45. MR 1923444
  • 4. Y. Dai, Convergence of nonlinear conjugate methods, J. Comput. Math., 19 (2001), pp. 539-549. MR 1851852 (2002f:65085)
  • 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. Y. Dai and Q. Ni, Testing different conjugate gradient methods for large-scale unconstrained optimization, J. Comput. Math. 21 (2003), no. 3, pp. 311-320. MR 1978635
  • 8. Y. Dai and Y. Yuan, A nonlinear conjugate gradient with a strong global convergence properties, SIAM Journal of Optimization, 10 (2000), pp. 177-182. MR 1740963 (2000i:90074)
  • 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. Y. Dai and Y. Yuan, Convergence properties of the conjugate descent method, Advances in Mathematics, 6 (1996), pp. 552-562. MR 1453164
  • 11. Y. Dai and Y. Yuan, An efficient hybird conjugate gradient method for unconstrained optimization, Annals of Operations Research, 103 (2001), 33-47. MR 1868442 (2002m:90107)
  • 12. Y. Dai and Y. Yuan, Nonlinear Conjugate Gradient Methods, Science Press of Shanghai, 2000.
  • 13. R. Fletcher, Practical Method of Optimization, Vol I: Unconstrained Optimization, Second edition, Wiley, New York, 1997. MR 585160 (83i:65055a)
  • 14. R. Fletcher and C. Reeves, Function minimization by conjugate gradients, Compute. J., 7 (1964), pp. 149-154. MR 0187375 (32:4827)
  • 15. J. C. Gibert and J. Nocedal, Global convergence properties of conjugate gradient methods for optimization, SIAM Journal of Optimization, 2 (1992), pp. 21-42. MR 1147881 (92k:90089)
  • 16. L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's methods, SIAM J. Numer. Anal., 23 (1986), pp. 707-716. MR 849278 (87g:90105)
  • 17. L. Grippo and S. Lucidi, A globally convergent version of the Polak-Ribière gradient method, Mathematics Programming, 78 (1997), pp. 375-391. MR 1466138 (98k:90080)
  • 18. A. Griewank, On automatic differentiation, in: Mathematical Programming: Recent De- velopments and Applications, M. Iri and K. Tanabe, eds., Kluwer Academic Publishers, (1989), pp. 84-108. MR 1114312 (92k:65002)
  • 19. M. R. Hestenes and E. Stiefel, Method of conjugate gradient for solving linear equations, J. Res. Nat. Bur. Stand ., 49 (1952), pp. 409-436. MR 0060307 (15:651a)
  • 20. D.H. Li, A descent modified Polak ``Ribiére'' Polyak conjugate gradient method and its global convergence, IMA Journal of Numerical Analysis (2006) 26, 629-640. MR 2263891 (2007f:90152)
  • 21. Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms, part 1: theory, Journal of Optimization Theory and Application, 69 (1992), pp. 129-137. MR 1104590 (92e:90077)
  • 22. G. McCormick, A modification of Armijo's step-size rule for negative curvature, Mathematical Programming, 13 (1977), pp. 111-115. MR 0461907 (57:1889)
  • 23. J. J. Morè, B. S. Garbow, and K. E. Hillstrome, Testing unconstrained optimization software, AVM Trans. Math. Software, 7 (1981), pp. 17-41. MR 607350 (83b:90144)
  • 24. J. Nocedal, Theory of algorithm for unconstrained optimization, Acta Numerica, Cambridge University Press, 1992 MR 1165726 (93b:90087)
  • 25. J. Nocedal, Conjugate gradient methods and nonlinear optimization, in Linear and Nonlinear Conjugate Gradient Related Methods, L. Adams and J.L. Nazareth, ed., SIAM Philadelphia, 1995, pp. 9-23. MR 1446295
  • 26. E. Polak and G. Ribière, Note Sur la convergence de directions conjugèes, Rev. Francaise Informat Recherche Operationelle, 3e Annèe, 16 (1969), pp. 35-43. MR 0255025 (40:8232)
  • 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, In Lecture Notes in Mathematics, Springer-Verlag, Berlin, 1066 (1984) pp. 122-141. MR 760460 (85g:49035)
  • 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. J. Sun and J. Zhang, Global convergence of conjugate gradient methods without line search, Annals of Operations Research, 103 (2001), 161-173. MR 1868449 (2003b:90140)
  • 31. Z. Wei, L. Qi and X. Chen, An SQP-type method and its application in stochastic programming, to appear in: Journal of Optimization Theory and Applications, 1 (2003). MR 1961035 (2003m:90166)
  • 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, Jabadie, ed., North-Holland, Amsterdam, 1970, pp. 37-86. MR 0437081 (55:10015)

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
Email: zxwei@gxu.edu.cn

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
Email: g.li@unsw.edu.au

Li Qun Qi
Affiliation: Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong
Email: maqilq@polyu.edu.hk

DOI: https://doi.org/10.1090/S0025-5718-08-02031-0
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.

American Mathematical Society