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

Authors:
William La Cruz, José Mario Martínez and Marcos Raydan

Journal:
Math. Comp. **75** (2006), 1429-1448

MSC (2000):
Primary 49M05, 90C06, 90C56, 65K10

DOI:
https://doi.org/10.1090/S0025-5718-06-01840-0

Published electronically:
April 11, 2006

MathSciNet review:
2219036

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**1.**J. Barzilai and J. M. Borwein, Two-point step size gradient methods,*IMA Journal of Numerical Analysis*,**8**, 1988, pp. 141-148. MR**0967848 (90h:65113)****2.**S. Bellavia and B. Morini, A globally convergent Newton-GMRES subspace method for systems of nonlinear equations,*SIAM Journal on Scientific Computing*,**23**, 2001, pp. 940-960. MR**1860971 (2002h:65077)****3.**E. G. Birgin, J. M. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets,*SIAM Journal on Optimization*,**10**, 2000, pp. 1196-1211. MR**1777088 (2001e:90143)****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.**5.**E. G. Birgin, J. M. Martínez and M. Raydan, Inexact spectral projected gradient methods on convex sets,*IMA Journal of Numerical Analysis*,**23**, 2003, pp. 539-559. MR**2011339 (2004h:90098)****6.**P. N. Brown and Y. Saad, Hybrid Krylov methods for nonlinear systems of equations,*SIAM Journal on Scientific Computing*,**11**, 1990, pp. 450-481.MR**1047206 (91e:65069)****7.**P. N. Brown and Y. Saad, Convergence theory of nonlinear Newton-Krylov algorithms,*SIAM Journal on Optimization*,**4**, 1994, pp. 297-330.MR**1273761 (95e:65052)****8.**Y. H. Dai and L. Z. Liao, R-linear convergence of the Barzilai and Borwein gradient method,*IMA Journal of Numerical Analysis*,**22**, 2002, pp. 1-10.MR**1880051 (2002j:90072)****9.**J. E. Dennis and R. B. Schnabel,*Numerical Methods for Unconstrained Optimization and Nonlinear Equations*, Prentice-Hall, Englewood Cliffs, New Jersey, 1983.MR**0702023 (85j:65001)****10.**R. Fletcher, Low storage methods for unconstrained optimization,*Lectures in Applied Mathematics (AMS)*,**26**, 1990, pp. 165-179.MR**1066281****11.**R. Fletcher, On the Barzilai-Borwein method,*Optimization and control with applications*, Appl. Optim., vol. 96, Springer, New York, 2005, pp. 235-256.MR**2144378****12.**M. Gasparo, A nonmonotone hybrid method for nonlinear systems,*Optimization Methods and Software*,**13**, 2000, pp. 79-94.MR**1771922 (2001b:65060)****13.**L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton's method,*SIAM Journal on Numerical Analysis*,**23**, 1986, pp. 707-716. MR**0849278 (87g:90105)****14.**L. Grippo and M. Sciandrone, Nonmonotone Derivative Free Methods for Nonlinear Equations, Technical Report 01-05, DIS, Università di Roma ``La Sapienza", 2005.**15.**C. T. Kelley,*Iterative Methods for Linear and Nonlinear Equations*, SIAM, Philadelphia, 1995. MR**1344684 (96d:65002)****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`.**17.**W. La Cruz and M. Raydan, Nonmonotone spectral methods for large-scale nonlinear systems,*Optimization Methods and Software*,**18**, 2003, pp. 583-599. MR**2015399 (2004i:65046)****18.**D. H. Li and M. Fukushima, A derivative-free line search and global convergence of Broyden-like method for nonlinear equations,*Optimization Methods and Software*,**13**, 2000, pp. 181-201. MR**1785195 (2001e:90146)****19.**F. Luengo, M. Raydan, W. Glunt and T. L. Hayden, Preconditioned Spectral Gradient Method,*Numerical Algorithms*,**30**, 2002, pp. 241-258. MR**1927505 (2004d:90132)****20.**J. M. Martínez, Practical quasi-Newton methods for solving nonlinear systems,*Journal of Computational and Applied Mathematics*,**124**, 2000, pp. 97-122. MR**1803295****21.**B. Molina and M. Raydan, Preconditioned Barzilai-Borwein method for the numerical solution of partial differential equations,*Numerical Algorithms*,**13**, 1996, pp. 45-60. MR**1417682 (97g:65071)****22.**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York, 1970. MR**0273810 (42:8686)****23.**M. Raydan, On the Barzilai and Borwein choice of the steplength for the gradient method,*IMA Journal on Numerical Analysis*,**13**, 1993, pp. 321-326. MR**1225468 (94e:90103)****24.**M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem,*SIAM Journal on Optimization*,**7**, 1997, pp. 26-33. MR**1430555 (98b:90131)**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
49M05,
90C06,
90C56,
65K10

Retrieve articles in all journals with MSC (2000): 49M05, 90C06, 90C56, 65K10

Additional Information

**William La Cruz**

Affiliation:
Departamento de Electrónica, Computación y Control, Facultad de Ingeniería, Universidad Central de Venezuela, Caracas 1051-DF, Venezuela

Email:
wlacruz@elecrisc.ing.ucv.ve

**José Mario Martínez**

Affiliation:
Department of Applied Mathematics, IMECC-UNICAMP, University of Campinas, CP 6065, 13081-970 Campinas SP, Brazil

Email:
martinez@ime.unicamp.br

**Marcos Raydan**

Affiliation:
Departamento de Computación, Facultad de Ciencias, Universidad Central de Vene- zuela, Apartado 47002, Caracas 1041-A, Venezuela

Email:
mraydan@kuaimare.ciens.ucv.ve

DOI:
https://doi.org/10.1090/S0025-5718-06-01840-0

Keywords:
Nonlinear systems,
spectral gradient method,
nonmonotone line search,
Newton-Krylov methods

Received by editor(s):
July 14, 2004

Received by editor(s) in revised form:
February 1, 2005

Published electronically:
April 11, 2006

Additional Notes:
The first author was supported by Agenda Petróleo UCV-PROJECT 97-003769.

The second author was supported by PRONEX-Optimization 76.79.1008-00, FAPESP (Grant 2001-04597-4), CNPq and FAEP-UNICAMP

The third author was supported by Agenda Petróleo UCV-PROJECT 97-003769.

Article copyright:
© Copyright 2006
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.