Abstract

We study the quasi-Newton method by using set-valued approximations for solving generalized equations without smoothness assumptions. The set-valued approximations appear naturally when dealing with nonsmooth problems, or even in smooth cases, data in almost concrete applications are not exact. We present a generalization of the classical Dennis-Moré theorem, which gives a characterization of the q-superlinear convergence of the quasi-Newton iterates. The local linear and superlinear convergences of the method, especially, a modification of the Broyden update method are investigated. We present an example showing that the classical Broyden update method is no longer linearly convergent when the function involved in the nonlinear equation is not smooth. A modified version of the Broyden update is proposed and its convergence is proved. These results are new, and can be considered as both an improvement and an extension of some results appeared recently in the literature on this subject.

Author information

Contact details are reproduced from the original publication and may be historical.

Samir Adly

Laboratoire Xlim, Université de Limoges, 123 Avenue Albert Thomas, 87060 Limoges, France
and: XLIM UMR-CNRS 7252

samir.adly@unilim.fr

Huynh Van Ngai

Dept. of Mathematics, University of Quynhon, 170 An Duong Vuong, Qui Nhon, Vietnam

ngaivn@yahoo.com

Keywords

  • Quasi-Newton methods
  • Broyden's update
  • Dennis-Moré theorem
  • metric regularity
  • generalized equations

Mathematics Subject Classification

47N10, 49J40, 49J53, 65K10, 65K15, 65J15, 90C30

References

  1. S. Adly, R. Cibulka, H. V. Ngai: Newton’s method for solving inclusions using set-valued approximations, SIAM J. Optim. 25 (2015) 159–184.https://doi.org/10.1137/130926730Google Scholar
  2. F. J. Aragón Artacho, A. Belyakov, A. L. Dontchev, M. López: Local convergence of quasi-Newton methods under metric regularity, Comp. Optim. Appl. 58(1) (2014) 225–247.https://doi.org/10.1007/s10589-013-9615-yGoogle Scholar
  3. C. G. Broyden: A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965) 577–593.https://doi.org/10.1090/S0025-5718-1965-0198670-6Google Scholar
  4. C. G. Broyden, J. E. Dennis, J. J. Moré: On the local and superlinear convergence of quasi-Newton methods, IMA J. 12 (1973) 223–246.https://doi.org/10.1093/imamat/12.3.223Google Scholar
  5. R. Cibulka, A. L. Dontchev, M. H. Geoffroy: Inexact Newton methods and Dennis-Moré theorems for nonsmooth generalized equations, SIAM J. Control and Optim. 53(2) (2015) 1003–1019.https://doi.org/10.1137/140969476Google Scholar
  6. J. E. Dennis, J. J. Moré: A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comput. 28 (1974) 549–560.https://doi.org/10.1090/S0025-5718-1974-0343581-1Google Scholar
  7. A. L. Dontchev: Local analysis of Newton-type method based on linearization, in: Letters in Applied Mathematics 32, Amer. Math. Soc., Providence (1996) 295–306.Google Scholar
  8. A. L. Dontchev: Generalizations of the Dennis-More theorem, SIAM J. Optim. 22 (2012) 821–830.https://doi.org/10.1137/110833567Google Scholar
  9. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings. A View from Variational Analysis, Springer Monographs in Mathematics, Springer, New York (2014).https://doi.org/10.1007/978-1-4939-1037-3Google Scholar
  10. F. Facchinei, J.-S. Pang: Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. II, Springer Series in Operations Research, Springer, New York (2003).https://doi.org/10.1007/b97544Google Scholar
  11. A. Griewank: Broyden updating, the good and the bad! Optimization stories, Doc. Math. (2012) 301–315.https://doi.org/10.4171/dms/6/32Google Scholar
  12. A. D. Ioffe: Nonsmooth analysis: differential calculus of nondifferentiable mappings, Trans. Amer. Math. Soc. 266 (1981) 1–56.https://doi.org/10.1090/S0002-9947-1981-0613784-7Google Scholar
  13. N. H. Josephy: Newton’s method for generalized equations, Technical Summary Report no. 1965, Mathematics Research Center, University of Wisconsin, Madison (1979).Google Scholar
  14. C. T. Kelly, E. Sachs: A new proof of superlinear convergence for Broyden’s method in Hilbert space, SIAM J. Optim. 1(1) (1991) 146–150.https://doi.org/10.1137/0801011Google Scholar
  15. D. Klatte, B. Kummer: Nonsmooth Equations in Optimization. Regularity, Calculus, Methods and Applications, Kluwer Academic Publishers, Dordrecht (2002).Google Scholar
  16. A. S. Lewis, M. L. Overton: Nonsmooth optimization via quasi-Newton methods, Math. Program., Ser. A 141 (2013) 135–163.https://doi.org/10.1007/s10107-012-0514-2Google Scholar
  17. H. V. Ngai, M. Théra: Error bounds in metric spaces and application to the perturbation stability of metric regularity, SIAM J. Optim. 19 (2008) 1–20.https://doi.org/10.1137/060675721Google Scholar
  18. M. Ortega, W. C. Rheinboldt: Iterative Solution of Nonlinear Equations in Several Variables, Classics in Applied Mathematics 30, SIAM, Philadelphia (2000).https://doi.org/10.1137/1.9780898719468Google Scholar
  19. J.-P. Penot: Calculus without derivatives, Graduate Texts in Mathematics 266, Springer, New York (2013).https://doi.org/10.1007/978-1-4614-4538-8Google Scholar
  20. S. M. Robinson: Strongly regular generalized equations, Math. Oper. Res. 5 (1980) 43–62.https://doi.org/10.1287/moor.5.1.43Google Scholar
  21. E. W. Sachs: Broyden’s method in Hilbert spaces, Math. Program. 35 (1986) 71–82.https://doi.org/10.1007/BF01589442Google Scholar
  22. E. Sachs: Convergence rates of quasi-Newton algorithms for some nonsmooth optimization problems, SIAM J. Control Optim. 23(3) (1985) 401–418.https://doi.org/10.1137/0323026Google Scholar
  23. H. Xu: Set-valued approximations and Newton’s methods, Math. Program., Ser. A 84 (1999) 401–420.https://doi.org/10.1007/s101070050028Google Scholar

Suggested citation

S. Adly, H. V. Ngai. “Quasi-Newton Methods for Solving Nonsmooth Equations: Generalized Dennis-Moré Theorem and Broyden's Update.” Journal of Convex Analysis 25 (2018), No. 4, 1075–1104. https://doi.org/10.68381/jca25069

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2018. Rights now held by Banach Press.