Spectral residual method without gradient information for solving large-scale nonlinear systems of equations

La Cruz, William; Martínez, José; Raydan, Marcos

doi:10.1090/S0025-5718-06-01840-0

Spectral residual method without gradient information for solving large-scale nonlinear systems of equations
HTML articles powered by AMS MathViewer

by William La Cruz, José Mario Martínez and Marcos Raydan PDF

Math. Comp. 75 (2006), 1429-1448 Request permission

Abstract:

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.

References

Jonathan Barzilai and Jonathan M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal. 8 (1988), no. 1, 141–148. MR 967848, DOI 10.1093/imanum/8.1.141
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. MR 1860971, DOI 10.1137/S1064827599363976
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. MR 1777088, DOI 10.1137/S1052623497330963
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.
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. MR 2011339, DOI 10.1093/imanum/23.4.539
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. MR 1047206, DOI 10.1137/0911026
Peter N. Brown and Youcef Saad, Convergence theory of nonlinear Newton-Krylov algorithms, SIAM J. Optim. 4 (1994), no. 2, 297–330. MR 1273761, DOI 10.1137/0804017
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. MR 1880051, DOI 10.1093/imanum/22.1.1
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. MR 702023
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. MR 1066281
Roger Fletcher, On the Barzilai-Borwein method, Optimization and control with applications, Appl. Optim., vol. 96, Springer, New York, 2005, pp. 235–256. MR 2144378, DOI 10.1007/0-387-24255-4_{1}0
Maria Grazia Gasparo, A nonmonotone hybrid method for nonlinear systems, Optim. Methods Softw. 13 (2000), no. 2, 79–94. MR 1771922, DOI 10.1080/10556780008805776
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. MR 849278, DOI 10.1137/0723046
L. Grippo and M. Sciandrone, Nonmonotone Derivative Free Methods for Nonlinear Equations, Technical Report 01-05, DIS, Università di Roma “La Sapienza", 2005.
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. MR 1344684, DOI 10.1137/1.9781611970944
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.
William La Cruz and Marcos Raydan, Nonmonotone spectral methods for large-scale nonlinear systems, Optim. Methods Softw. 18 (2003), no. 5, 583–599. MR 2015399, DOI 10.1080/10556780310001610493
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. MR 1785195, DOI 10.1080/10556780008805782
F. Luengo, M. Raydan, W. Glunt, and T. L. Hayden, Preconditioned spectral gradient method, Numer. Algorithms 30 (2002), no. 3-4, 241–258. MR 1927505, DOI 10.1023/A:1020181927999
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. MR 1803295, DOI 10.1016/S0377-0427(00)00434-9
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. MR 1417682, DOI 10.1007/BF02143126
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
Marcos Raydan, On the Barzilai and Borwein choice of steplength for the gradient method, IMA J. Numer. Anal. 13 (1993), no. 3, 321–326. MR 1225468, DOI 10.1093/imanum/13.3.321
Marcos Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim. 7 (1997), no. 1, 26–33. MR 1430555, DOI 10.1137/S1052623494266365