Abstract
We are concerned with defining new globalization criteria for solution methods of nonlinear equations. The current criteria used in these methods require a sufficient decrease of a particular merit function at each iteration of the algorithm. As was observed in the field of smooth unconstrained optimization, this descent requirement can considerably slow the rate of convergence of the sequence of points produced and, in some cases, can heavily deteriorate the performance of algorithms. The aim of this paper is to show that the global convergence of most methods proposed in the literature for solving systems of nonlinear equations can be obtained using less restrictive criteria that do not enforce a monotonic decrease of the chosen merit function. In particular, we show that a general stabilization scheme, recently proposed for the unconstrained minimization of continuously differentiable functions, can be extended to methods for the solution of nonlinear (nonsmooth) equations. This scheme includes different kinds of relaxation of the descent requirement and opens up the possibility of describing new classes of algorithms where the old monotone linesearch techniques are replace with more flexible nonmonotone stabilization procedures. As in the case of smooth unconstrained optimization, this should be the basis for defining more efficient algorithms with very good practical rates of convergence.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Burdakov, O. P.,Some Globally Convergent Modifications of Newton's Method for Solving Systems of Nonlinear Equations, Soviet Mathematics Doklady, Vol. 22, pp. 376–379, 1980.
Stoer, J., andBulirsch, R.,Introduction to Numerical Analysis. Springer-Verlag, New York, New York, 1980.
Polak, E.,On the Global Stabilization of Locally Convergent Algorithms, Automatica, Vol. 12, pp. 337–349, 1976.
Han, S. P., Pang, J. S., andRangaraj, N.,Globally Convergent Newton Methods for Nonsmooth Equations, Mathematics of Operations Research, Vol. 17, pp. 586–607, 1992.
Harker, P. T., andXiao B.,Newton's Method for the Nonlinear Complementarity Problem: A B-Differentiable Equation Approach, Mathematical Programming, Vol. 48, pp. 339–358, 1990.
Pang, J. S., Han, S. P., andRangaraj, N.,Minimization of Locally Lipschitzian Functions, SIAM Journal on Optimization, Vol. 1, pp. 57–82, 1991.
Grippo, L., Lampariello, F., andLucidi, S.,A Nonmonotone Line Search Technique for Newton's Method, SIAM Journal on Numerical Analysis, Vol. 23, pp. 707–716, 1986.
Grippo, L., Lampariello, F., andLucidi, S.,A Class of Nonmonotone Stabilization Methods in Unconstrained Optimization, Numerische Mathematik, Vol. 59, pp. 779–805, 1991.
Dennis, J. E., andSchnabel, R. B.,Numerical Methods for Unconstrained Optimizations and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1983.
Shor, N. Z.,Minimization Methods for Nondifferentiable Functions, Springer-Verlag, Berlin, Germany, 1985.
Zowe, J.,Nondifferentiable Optimization, Computational Mathematical Programming, Edited by K. Schittkowski, Springer-Verlag, Berlin, Germany, pp. 321–356, 1985.
Bertsekas, D. P.,Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New York, New York, 1982.
Ortega, J. M., andRheinboldt, W. C.,Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970.
Clarke, F. H.,Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, New York, 1983.
Pshenichny, B. N., andDanilin, Yu. M.,Numerical Methods in Extremal Problems, MIR Publishers, Moscow, Russia, 1978.
Kiwiel, K. C.,Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Springer-Verlag, Berlin, Germany, Vol. 1113, 1985.
Ferris, M. C., andLucidi, S.,Globally Convergent Methods for Nonlinear Equations, Technical Report 1030, Computer Sciences Department, University of Wisconsin, 1991.
Author information
Authors and Affiliations
Additional information
Communicated by O. L. Mangasarian
This material is partially based on research supported by the Air Force Office of Scientific Research Grant AFOSR-89-0410, National Science Foundation Grant CCR-91-57632, and Istituto di Analisi dei Sistemi ed Informatica del CNR.
Rights and permissions
About this article
Cite this article
Ferris, M.C., Lucidi, S. Nonmonotone stabilization methods for nonlinear equations. J Optim Theory Appl 81, 53–71 (1994). https://doi.org/10.1007/BF02190313
Issue Date:
DOI: https://doi.org/10.1007/BF02190313