Abstract

We study convergence of the Newton method for solving generalized equations of the form f(x)+F(x)∋0,f(x)+F(x)\ni 0, where ff is a continuous but not necessarily smooth function and FF is a set-valued mapping with closed graph, both acting in Banach spaces. We present a Kantorovich-type theorem concerning r-linear convergence for a general algorithmic strategy covering both nonsmooth and smooth cases. Under various conditions we obtain higher-order convergence. Examples and computational experiments illustrate the theoretical results.

Author information

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

Radek Cibulka

NTIS - Dept. of Mathematics, Faculty of Applied Sciences, University of West Bohemia, Univerzitní 22, 306 14 Pilsen, Czech Republic

cibi@kma.zcu.cz

Asen L. Dontchev

Mathematical Reviews, 416 Fourth Street, Ann Arbor, MI 48107-8604, U.S.A.
and: Institute of Statistics and Mathematical Methods in Economics, Vienna University of Technology, Wiedner Hauptstrasse 8, 1040 Vienna, Austria

ald@ams.org

Jakob Preininger

Institute of Statistics and Mathematical Methods in Economics, University of Technology, Wiedner Hauptstrasse 8, 1040 Vienna, Austria

jakob.preininger@tuwien.ac.at

Tomáš Roubal

NTIS - Dept. of Mathematics, Faculty of Applied Sciences, University of West Bohemia, Univerzitní 22, 306 14 Pilsen, Czech Republic

roubalt@students.zcu.cz

Vladimir Veliov

Institute of Statistics and Mathematical Methods in Economics, University of Technology, Wiedner Hauptstrasse 8, 1040 Vienna, Austria

veliov@tuwien.ac.at

Keywords

  • Newton's method
  • generalized equation
  • variational inequality
  • metric regularity
  • Kantorovich theorem
  • linear/superlinear/quadratic convergence

Mathematics Subject Classification

49J53, 49J40, 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. S. Adly, H. V. Ngai, N. V. Vu: Newton’s method for solving generalized equations: Kantorovich’s and Smale’s approaches, J. Math. Anal. Appl. 439 (2016) 396–418.https://doi.org/10.1016/j.jmaa.2016.02.047Google Scholar
  3. F. J. Aragón Artacho, A. Belyakov, A. L. Dontchev, M. Lopez: Local convergence of quasi-Newton methods under metric regularity, Comput. Optim. Appl. 58 (2014) 225–247.https://doi.org/10.1007/s10589-013-9615-yGoogle Scholar
  4. I. K. Argyros: Convergence and Applications of Newton-Type Iterations, Springer, Berlin (2008).Google Scholar
  5. J.-P. Aubin, H. Frankowska: Set-Valued Analysis, Systems and Control: Foundations and Applications, Birkhäuser, Boston (1990).Google Scholar
  6. R. G. Bartle: Newton’s method in Banach spaces, Proc. Amer. Math. Soc. 6 (1955) 827–831.https://doi.org/10.1090/S0002-9939-1955-0071730-1Google Scholar
  7. S. C. Billups: Algorithms for Complementarity Problems and Generalized Equations, PhD Thesis, Technical Report 95-14, Computer Sciences Department, University of Wisconsin, Madison (1995).Google Scholar
  8. K. Butts, A. Dontchev, M. Huang, I. Kolmanovsky: A perturbed chord (Newton-Kantorovich) method for constrained nonlinear model predictive control, Proceedings of NOLCOS 2016, IFAC-PapersOnLine 49-18 (2016) 253–258.https://doi.org/10.1016/j.ifacol.2016.10.172Google Scholar
  9. P. G. Ciarlet, C. Mardare: On the Newton-Kantorovich theorem, Anal. Appl. (Singapore) 10 (2012) 249–269.https://doi.org/10.1142/S0219530512500121Google Scholar
  10. S. P. Dirkse: Robust Solution of Mixed Complementarity Problems, PhD Thesis, Computer Science Departement, University of Wisconsin, Madison (1994).Google Scholar
  11. S. P. Dirkse, M. C. Ferris, T. Munson: http://pages.cs.wisc.edu/~ferris/path.html.Google Scholar
  12. A. L. Dontchev, R. T. Rockafellar: Parametric stability of solutions in models of economic equilibrium, J. Convex Analysis 19 (2012) 975–997.https://doi.org/10.68381/jca19051Google Scholar
  13. A. L. Dontchev: Local analysis of a Newton-type method based on partial linearization, in: The Mathematics of Numerical Analysis, (Park City, 1995), Lectures Appl. Math. 32, Amer. Math. Soc., Providence, (1996) 295–306.Google Scholar
  14. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings. A View from Variational Analysis, 2nd edition, Springer, Berlin (2014).https://doi.org/10.1007/978-1-4939-1037-3Google Scholar
  15. F. Facchinei, J.-S. Pang: Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York (2003).https://doi.org/10.1007/b97543Google Scholar
  16. O. P. Ferreira, G. N. Silva: Inexact Newton’s method to nonlinear functions with values in a cone, Applicable Analysis (2018).https://doi.org/10.1080/00036811.2018.1430779Google Scholar
  17. W. B. Gragg, R. A. Tapia: Optimal error bounds for the Newton-Kantorovich theorem, SIAM J. Numer. Anal. 11 (1974) 10–13.https://doi.org/10.1137/0711002Google Scholar
  18. M. Hintermüller: Semismooth Newton methods and applications, http://www.math.uni-hamburg.de/home/hinze/Psfiles/Hintermueller_OWNotes.pdf, Oberwolfach (2010).Google Scholar
  19. K. Ito, K. Kunisch: Lagrange Multiplier Approach to Variational Problems and Applications, SIAM, Philadelphia (2008).https://doi.org/10.1137/1.9780898718614Google Scholar
  20. A. F. Izmailov, A. S. Kurennoy, M. V. Solodov: The Josephy-Newton method for semismooth generalized equations and semismooth SQP for optimization, Set-Valued Var. Anal. 21 (2013) 17–45.https://doi.org/10.1007/s11228-012-0218-zGoogle Scholar
  21. A. F. Izmailov, M. V. Solodov: Newton-Type Methods for Optimization and Variational Problems, Springer, Berlin (2014).https://doi.org/10.1007/978-3-319-04247-3Google Scholar
  22. L. V. Kantorovich: On Newton’s method for functional equations (Russian), Doklady Akad. Nauk SSSR (N.S.) 59 (1948) 1237–1240.Google Scholar
  23. L. V. Kantorovich, G. P. Akilov: Functional Analysis (Russian), 2nd revised edition, Nauka, Moscow (1977).Google Scholar
  24. C. T. Kelley: Solving Nonlinear Equations with Newton’s Method, Fundamentals of Algorithms, SIAM, Philadelphia (2003).https://doi.org/10.1137/1.9780898718898Google Scholar
  25. D. Klatte, B. Kummer: Nonsmooth Equations in Optimization. Regularity, Calculus, Methods and Applications, Kluwer, New York (2002).Google Scholar
  26. B. Kummer: Newton’s method for non-differentiable functions, in: “Advances in Mathematical Optimization”, J. Guddat et al. (eds.), Ser. Math. Res. 45, Akademie-Verlag, Berlin (1988) 114–125.https://doi.org/10.1515/9783112479926-011Google Scholar
  27. J. M. Ortega: The Newton-Kantorovich theorem, Amer. Math. Monthly 75 (1968) 658–660.https://doi.org/10.2307/2313800Google Scholar
  28. A. Pietrus: Non differentiable perturbed Newton’s method for functions with values in a cone, Investigación Oper. 35 (2014) 58–67.Google Scholar
  29. F. A. Potra, V. Pták: Nondiscrete induction and iterative processes, Research Notes in Mathematics 103, Pitman, Boston (1984).Google Scholar
  30. L. Qi, J. Sun: A nonsmooth version of Newton’s method, Math. Programming A 58 (1993) 353–367.https://doi.org/10.1007/BF01581275Google Scholar
  31. S. M. Robinson: Extension of Newton’s method to nonlinear functions with values in a cone, Numer. Math. 19 (1972) 341–347.https://doi.org/10.1007/BF01404880Google Scholar
  32. G. N. Silva: Kantorovich’s theorem on Newton’s method for solving generalized equations under the majorant condition, Appl. Math. Comput. 286 (2016) 178–188.https://doi.org/10.1016/j.amc.2016.04.015Google Scholar
  33. M. Ulbrich: Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, SIAM, Philadelphia (2011).https://doi.org/10.1137/1.9781611970692Google Scholar
  34. T. J. Ypma: Historical development of the Newton-Raphson method, SIAM Rev. 37 (1995) 531–551.https://doi.org/10.1137/1037125Google Scholar

Suggested citation

R. Cibulka, A. L. Dontchev, J. Preininger, T. Roubal, V. Veliov. “Kantorovich-Type Theorems for Generalized Equations.” Journal of Convex Analysis 25 (2018), No. 2, 459–486. https://doi.org/10.68381/jca25031

Download BibTeXPublished by Heldermann Verlag.

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