zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Gradient methods with adaptive step-sizes. (English) Zbl 1121.90099
Summary: Motivated by the superlinear behavior of the Barzilai-Borwein (BB) method for two-dimensional quadratics, we propose two gradient methods which adaptively choose a small step-size or a large step-size at each iteration. The small step-size is primarily used to induce a favorable descent direction for the next iteration, while the large step-size is primarily used to produce a sufficient reduction. Although the new algorithms are still linearly convergent in the quadratic case, numerical experiments on some typical test problems indicate that they compare favorably with the BB method and some other efficient gradient methods.
MSC:
90C20Quadratic programming
90C52Methods of reduced gradient type
Software:
GPDT; SPG; CONV_QP
References:
[1]H.Akaike, ”On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method,” Ann. Inst. Statist. Math., Tokyo, vol. 11, pp. 1–17, 1959. · Zbl 0100.14002 · doi:10.1007/BF01831719
[2]R.Andreani, E.G.Birgin, J.M.Martínez, and J.Yuan, ”Spectral projected gradient and variable metric methods for optimization with linear inequalities,” IMA J.Numer. Anal., vol. 25, pp. 221–252, 2005. · Zbl 1072.90051 · doi:10.1093/imanum/drh020
[3]J.Barzilai and J.M.Borwein, ”Two-point step size gradient methods,” IMA J. Numer. Anal., vol. 8, pp. 141–148, 1988. · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141
[4]L.Bello and M.Raydan, ”Preconditioned spectral projected gradient methods on convex sets,” Journal of Computational Mathematics, vol. 23, pp. 225–232, 2005.
[5]E.G.Birgin, J.M.Martínez, and M.Raydan, ”Nonmonotone spectral projected gradient methods on convex sets,” SIAM J. Optim., vol. 10, pp. 1196–1211, 2000. · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[6]E.G.Birgin, J.M.Martínez, and M.Raydan, ”Algorithm 813: SPG–software for convex-constrained optimization,” ACM Trans. Math. Software, vol. 27, pp. 340–349, 2001. · Zbl 1070.65547 · doi:10.1145/502800.502803
[7]E.G.Birgin, J.M.Martínez, and M.Raydan, ”Inexact spectral projected gradient methods on convex sets,” IMA J. Numer. Anal., vol. 23, pp. 539–559, 2003. · Zbl 1047.65042 · doi:10.1093/imanum/23.4.539
[8]A.Cauchy, ”Méthode générale pour la résolution des syst è ms d’équations simultanées,” Comp. Rend. Sci. Paris, vol. 25, pp. 536–538, 1847.
[9]Y.H.Dai, ”Alternate step gradient method,” Optimization, vol. 52, pp. 395–415, 2003. · Zbl 1056.65055 · doi:10.1080/02331930310001611547
[10]Y.H.Dai and L.Z.Liao, ”R-linear convergence of the Barzilai and Borwein gradient method,” IMA J. Numer. Anal., vol. 22, pp. 1–10, 2002. · Zbl 1002.65069 · doi:10.1093/imanum/22.1.1
[11]Y.H.Dai and Y.Yuan, ”Alternate minimization gradient method,” IMA J. Numer. Anal., vol. 23, pp. 377–393, 2003. · Zbl 1055.65073 · doi:10.1093/imanum/23.3.377
[12]R.Fletcher, ”Low storage methods for unconstrained optimization,” Lectures in Applied Mathematics (AMS), vol. 26, pp. 165–179, 1990.
[13]R.Fletcher, ”On the Barzilai-Borwein method,” Numerical Analysis Report NA/207, Department of Mathematics, University of Dundee, 2001.
[14]A.Friedlander, J.M. Martínez, B.Molina, and M.Raydan, ”Gradient method with retards and generalizations,” SIAM J. Numer. Anal., vol. 36, pp. 275–289, 1999. · Zbl 0940.65032 · doi:10.1137/S003614299427315X
[15]L.Grippo, F.Lampariello, and S.Lucidi, ”A nonmonotone line search technique for Newton’s method,” SIAM J. Numer. Anal., vol. 23, pp. 707–716, 1986. · Zbl 0616.65067 · doi:10.1137/0723046
[16]M.R.Hestenes and E.L.Stiefel, ”Methods of conjugate gradients for solving linear systems,” J. Research National Bureau of Standards, vol. B49, pp. 409–436, 1952.
[17]W.LaCruz, J.M.Martínez, and M.Raydan, ”Spectral residual method without gradient information for solving large-scale nonlinear systems of equations,” Mathematics of Computation, to appear.
[18]W.LaCruz and M.Raydan, ”Nonmonotone spectral methods for large-scale nonlinear systems,” Optimization Methods and Software, vol. 18, pp. 583–599, 2003. · Zbl 1069.65056 · doi:10.1080/10556780310001610493
[19]J.-L.Lamotte, B.Molina, and M.Raydan, ”Smooth and adaptive gradient method with retards,” Mathematical and Computer Modelling, vol. 36, pp. 1161–1168, 2002. · Zbl 1029.65029 · doi:10.1016/S0895-7177(02)00266-2
[20]F.Luengo and M.Raydan, ”Gradient method with dynamical retards for large-scale optimization problems,” Electronic Transactions on Numerical Analysis, vol. 16, pp. 186–193, 2003.
[21]M.Raydan, ”On the Barzilai and Borwein choice of steplength for the gradient method,” IMA J. Numer. Anal., vol. 13, pp. 321–326, 1993. · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321
[22]M.Raydan, ”The Barzilai and Borwein method for the large scale unconstrained minimization problem,” SIAM J. Optim., vol. 7, pp. 26–33, 1997. · Zbl 0898.90119 · doi:10.1137/S1052623494266365
[23]M.Raydan and B.F.Svaiter, ”Relaxed steepest descent and Cauchy-Barzilai-Borwein method,” Computational Optimization and Applications, vol. 21, pp. 155–167, 2002. · Zbl 0988.90049 · doi:10.1023/A:1013708715892
[24]T.Serafini, G.Zanghirati, and L.Zanni, ”Gradient projection methods for quadratic programs and applications in training support vector machines,” Tech. Rep. 48, University of Modena and Reggio Emilia, Italy, 2003.
[25]H.Zhang and W.W. Hager, ”A nonmonotone line search technique and its application to unconstrained optimization,” SIAM J. Optim., vol. 14, pp. 1043–1056, 2004. · Zbl 1073.90024 · doi:10.1137/S1052623403428208