×

A Barzilai-Borwein conjugate gradient method. (English) Zbl 1352.49031

Summary: The linear conjugate gradient method is an optimal method for convex quadratic minimization due to the Krylov subspace minimization property. The proposition of limited-memory BFGS method and Barzilai-Borwein gradient method, however, heavily restricted the use of conjugate gradient method for large-scale nonlinear optimization. This is, to the great extent, due to the requirement of a relatively exact line search at each iteration and the loss of conjugacy property of the search directions in various occasions. On the contrary, the limited-memory BFGS method and the Barzilai-Bowein gradient method share the so-called asymptotical one stepsize per line-search property, namely, the trial stepsize in the method will asymptotically be accepted by the line search when the iteration is close to the solution. This paper will focus on the analysis of the subspace minimization conjugate gradient method by Y. Yuan and J. Stoer [Z. Angew. Math. Mech. 75, No. 1, 69–77 (1995; Zbl 0823.65061)]. Specifically, if choosing the parameter in the method by combining the Barzilai-Borwein idea, we will be able to provide some efficient Barzilai-Borwein Conjugate Gradient (BBCG) methods. The initial numerical experiments show that one of the variants, BBCG3, is specially efficient among many others without line searches. This variant of the BBCG method might enjoy the asymptotical one stepsize per line-search property and become a strong candidate for large-scale nonlinear optimization.

MSC:

49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming

Citations:

Zbl 0823.65061

Software:

L-BFGS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barzilai J, Borwein J M. Two-point step size gradient methods. IMA J Numer Anal, 1988, 8: 141-148 · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[2] Birgin EG, Martinez J M. A spectral conjugate gradient method for unconstrained optimization. Appl Math Optim, 2001, 43: 117-128 · Zbl 0990.90134 · doi:10.1007/s00245-001-0003-0
[3] Dai, Y. H., Nonlinear conjugate gradient methods (2011)
[4] Dai Y H. A new analysis on the Barzilai-Borwein gradient method. J Oper Res Soc China, 2013, 1: 187-198 · Zbl 1334.90162 · doi:10.1007/s40305-013-0007-x
[5] Dai Y H, Fletcher R. On the asymptotic behaviour of some new gradient methods. Math Program Ser A, 2005, 13: 541-559 · Zbl 1099.90038 · doi:10.1007/s10107-004-0516-9
[6] Dai Y H, Kou C X. A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search. SIAM J Optim, 2013, 23: 296-320 · Zbl 1266.49065 · doi:10.1137/100813026
[7] Dai Y H, Liao L Z. New conjugacy conditions and related nonlinear conjugate gradient methods. Appl Math Optim, 2001, 43: 87-101 · Zbl 0973.65050 · doi:10.1007/s002450010019
[8] Dai YH, Liao LZ. R-linear convergence of the Barzilai and Borwein gradient method. IMA J Numer Anal, 2002, 22: 1-10 · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1
[9] Dai Y H, Yuan Y. A nonlinear conjugate gradient method with a strong global convergence property. SIAM J Optim, 1999, 10: 177-182 · Zbl 0957.65061 · doi:10.1137/S1052623497318992
[10] Fletcher R, Reeves C M. Function minimization by conjugate gradients. Comput J, 1964, 7: 149-154 · Zbl 0132.11701 · doi:10.1093/comjnl/7.2.149
[11] Grippo L, Lamparillo F, Lucidi S. A nonmonotone line search technique for Newton’s method. SIAM J Numer Anal, 1986, 23: 707-716 · Zbl 0616.65067 · doi:10.1137/0723046
[12] Hager W W, Ngo C, Yashtini M, et al. An alternating direction approximate newton algorithm for ill-conditioned inverse problems with application to parallel MRI. J Oper Res Soc China, 2015, 3: 139-162 · Zbl 1317.90235 · doi:10.1007/s40305-015-0078-y
[13] Hager W W, Zhang H. A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J Optim, 2005, 16: 170-192 · Zbl 1093.90085 · doi:10.1137/030601880
[14] Hager W W, Zhang H. A survey of nonlinear conjugate gradient methods. Pac J Optim, 2006, 2: 35-58 · Zbl 1117.90048
[15] Hestenes M R, Stiefel E. Method of conjugate gradient for solving linear system. J Res Nat Bur Stand, 1952, 49: 409-436 · Zbl 0048.09901 · doi:10.6028/jres.049.044
[16] Liu D C, Nocedal J. On the limited memory BFGS method for large scale optimization. Math Program, 1989, 45: 503-528 · Zbl 0696.90048 · doi:10.1007/BF01589116
[17] Nocedal J. Updating quasi-Newton matrices with limited storage. Math Comp, 1980, 35: 773-782 · Zbl 0464.65037 · doi:10.1090/S0025-5718-1980-0572855-7
[18] Oren S S. Self scaling variable metric (SSVM) algorithms, part II: Implementation and experiments. Manag Sci, 1974, 20: 863-874 · Zbl 0316.90065 · doi:10.1287/mnsc.20.5.863
[19] Oren S S, Luenberger D G. Self scaling variable metric (SSVM) algorithms, part I: Criteria and sufficient conditions for scaling a class of algorithms. Manag Sci, 1974, 20: 845-862 · Zbl 0316.90064 · doi:10.1287/mnsc.20.5.845
[20] Polak E, Ribière G. Note sur la convergence de méthods de directions conjugées. Rev Franaise Informat Recherche Opérationnelle, 1969, 16: 35-43 · Zbl 0174.48001
[21] Polyak B T. The conjugate gradient method in extremem problems. USSR Comp Math Math Phys, 1969, 9: 94-112 · Zbl 0229.49023 · doi:10.1016/0041-5553(69)90035-4
[22] Raydan M. On the Barzilai and Borwein choice of steplength for the gradient method. IMA J Numer Anal, 1993, 13: 321-326 · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321
[23] Raydan M. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J Optim, 1997, 7: 26-33 · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[24] Sun W, Yuan Y. Optimization Theory and Methods: Nonlinear Programming. New York: Springer, 2006 · Zbl 1129.90002
[25] Yuan Y, Stoer J. A subspace study on conjugate gradient algorithms. Z Angew Math Mech, 1995, 75: 69-77 · Zbl 0823.65061 · doi:10.1002/zamm.19950750118
[26] Zhang L, ZhouW, Li D. A descentmodified Polak-Ribière-Polyak conjugate gradient method and its global convergence. IMA J Numer Anal, 2006, 26: 629-640 · Zbl 1106.65056 · doi:10.1093/imanum/drl016
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.