×

zbMATH — the first resource for mathematics

Spectral residual method without gradient information for solving large-scale nonlinear systems of equations. (English) Zbl 1122.65049
Summary: A fully derivative-free spectral residual method for solving large-scale nonlinear systems of equations is presented. It uses in a systematic way the residual vector as a search direction, a spectral steplength that produces a nonmonotone process and a globalization strategy that allows for this nonmonotone behavior. The global convergence analysis of the combined scheme is presented. An extensive set of numerical experiments that indicate that the new combination is competitive and frequently better than well-known Newton-Krylov methods for large-scale problems is also presented.

MSC:
65H10 Numerical computation of solutions to systems of equations
65K10 Numerical optimization and variational techniques
90C30 Nonlinear programming
Software:
SPG; KELLEY
PDF BibTeX Cite
Full Text: DOI
References:
[1] Jonathan Barzilai and Jonathan M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal. 8 (1988), no. 1, 141 – 148. · Zbl 0638.65055
[2] Stefania Bellavia and Benedetta Morini, A globally convergent Newton-GMRES subspace method for systems of nonlinear equations, SIAM J. Sci. Comput. 23 (2001), no. 3, 940 – 960. · Zbl 0998.65053
[3] Ernesto G. Birgin, José Mario Martínez, and Marcos Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10 (2000), no. 4, 1196 – 1211. · Zbl 1047.90077
[4] E. G. Birgin, J. M. Martínez and M. Raydan, Algorithm 813: SPG - Software for convex-constrained optimization, ACM Transactions on Mathematical Software, 27, 2001, pp. 340-349. · Zbl 1070.65547
[5] Ernesto G. Birgin, José Mario Martínez, and Marcos Raydan, Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal. 23 (2003), no. 4, 539 – 559. · Zbl 1047.65042
[6] Peter N. Brown and Youcef Saad, Hybrid Krylov methods for nonlinear systems of equations, SIAM J. Sci. Statist. Comput. 11 (1990), no. 3, 450 – 481. · Zbl 0708.65049
[7] Peter N. Brown and Youcef Saad, Convergence theory of nonlinear Newton-Krylov algorithms, SIAM J. Optim. 4 (1994), no. 2, 297 – 330. · Zbl 0814.65048
[8] Yu-Hong Dai and Li-Zhi Liao, R-linear convergence of the Barzilai and Borwein gradient method, IMA J. Numer. Anal. 22 (2002), no. 1, 1 – 10. · Zbl 1002.65069
[9] John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. · Zbl 0579.65058
[10] R. Fletcher, Low storage methods for unconstrained optimization, Computational solution of nonlinear systems of equations (Fort Collins, CO, 1988) Lectures in Appl. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1990, pp. 165 – 179. · Zbl 0699.65052
[11] Roger Fletcher, On the Barzilai-Borwein method, Optimization and control with applications, Appl. Optim., vol. 96, Springer, New York, 2005, pp. 235 – 256. · Zbl 1118.90318
[12] Maria Grazia Gasparo, A nonmonotone hybrid method for nonlinear systems, Optim. Methods Softw. 13 (2000), no. 2, 79 – 94. · Zbl 0957.65043
[13] 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. · Zbl 0616.65067
[14] L. Grippo and M. Sciandrone, Nonmonotone Derivative Free Methods for Nonlinear Equations, Technical Report 01-05, DIS, Università di Roma “La Sapienza”, 2005. · Zbl 1180.90310
[15] C. T. Kelley, Iterative methods for linear and nonlinear equations, Frontiers in Applied Mathematics, vol. 16, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1995. With separately available software. · Zbl 0832.65046
[16] W. La Cruz, J. M. Martínez and M. Raydan, Spectral residual method without gradient information for solving large-scale nonlinear systems: Theory and experiments, Technical Report RT-04-08, Dpto. de Computacion, UCV, 2004. Available at www.kuainasi.ciens.ucv.ve/ccct/mraydan_pub.html. · Zbl 1122.65049
[17] William La Cruz and Marcos Raydan, Nonmonotone spectral methods for large-scale nonlinear systems, Optim. Methods Softw. 18 (2003), no. 5, 583 – 599. · Zbl 1069.65056
[18] Dong-Hui Li and Masao Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Softw. 13 (2000), no. 3, 181 – 201. · Zbl 0960.65076
[19] F. Luengo, M. Raydan, W. Glunt, and T. L. Hayden, Preconditioned spectral gradient method, Numer. Algorithms 30 (2002), no. 3-4, 241 – 258. · Zbl 1027.90110
[20] José Mario Martínez, Practical quasi-Newton methods for solving nonlinear systems, J. Comput. Appl. Math. 124 (2000), no. 1-2, 97 – 121. Numerical analysis 2000, Vol. IV, Optimization and nonlinear equations. · Zbl 0967.65065
[21] Brigida Molina and Marcos Raydan, Preconditioned Barzilai-Borwein method for the numerical solution of partial differential equations, Numer. Algorithms 13 (1996), no. 1-2, 45 – 60. · Zbl 0861.65025
[22] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. · Zbl 0241.65046
[23] Marcos Raydan, On the Barzilai and Borwein choice of steplength for the gradient method, IMA J. Numer. Anal. 13 (1993), no. 3, 321 – 326. · Zbl 0778.65045
[24] Marcos Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim. 7 (1997), no. 1, 26 – 33. · Zbl 0898.90119
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.