Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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.


References [Enhancements On Off] (What's this?)

  • 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)

Similar Articles

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.

American Mathematical Society