|
Global convergence of the Polak-Ribière-Polyak conjugate gradient method with an Armijo-type inexact line search for nonconvex unconstrained optimization problems
Author(s):
Zeng Xin
Wei;
Guo Yin
Li;
Li Qun
Qi.
Journal:
Math. Comp.
77
(2008),
2173-2193.
MSC (2000):
Primary 65H10, 90C26
Posted:
June 11, 2008
Retrieve article in:
PDF DVI PostScript
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:
-
- 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:
10.1090/S0025-5718-08-02031-0
PII:
S 0025-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
Posted:
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
Copyright of article:
Copyright
2008,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org