Abstract

We present an algorithm for the solution of structured nonsmooth operator equations in Banach spaces. Specifically, we seek roots of mappings that involve the composition of a smooth outer and a semismooth inner map. To exploit this structure we propose a hybrid approach in which the semismooth part is linearized in the same way as in semismooth Newton methods while the smooth part is handled by a Broyden-like method. The resulting algorithm is a semismooth Newton-type method that does not require the evaluation of the derivative of the smooth part. We prove local q-linear and q-superlinear convergence results for the hybrid algorithm. In particular, this is the first work that establishes superlinear convergence of a semismooth quasi-Newton method in an infinite-dimensional setting. The convergence results also extend known finite-dimensional ones in that the structure of the equation and the algorithm under consideration are more general than those available in the literature. In addition, it is shown that q-linear convergence of the iterates and compactness of the initial operator discrepancy of the smooth part implies q-superlinear convergence without the assumption that the initial operator discrepancy is small in norm, which is a new type of result for semismooth quasi-Newton methods. The convergence theory is developed under mild assumptions, which yields extensions of available results for semismooth quasi-Newton methods as well as for Broyden-like methods. The benefit of the method in practical applications is addressed in a complementary paper. There, we show on problems from optimal control that the assumptions for q-superlinear convergence are satisfied and that the hybrid approach leads to highly competitive numerical schemes that have substantially lower runtimes than state-of-the-art semismooth Newton methods.

Author information

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

Keywords

  • Semismooth Newton-type methods
  • Broyden-like method
  • quasi-Newton methods
  • superlinear convergence
  • nonsmooth operator equations

Mathematics Subject Classification

47J25, 47N10, 49J27, 49J52, 49M15, 49M27, 65J15, 90C30, 90C48, 90C53, 90C56

References

  1. S. Adly, H. V. Ngai: Quasi-Newton methods for solving nonsmooth equations: Generalized Dennis-Moré Theorem and Broyden’s update, J. Convex Analysis 25/4 (2018) 1075–1104.https://doi.org/10.68381/jca25069Google Scholar
  2. S. Amat, S. Busquier: A modified secant method for semismooth equations, Appl. Math. Lett. 16/6 (2003) 877–881.https://doi.org/10.1016/S0893-9659(03)90011-5Google Scholar
  3. F. J. Aragón Artacho, A. Belyakov, A. L. Dontchev, M. López: Local convergence of quasi-Newton methods under metric regularity, Comput. Optim. Appl. 58/1 (2014) 225–247.https://doi.org/10.1007/s10589-013-9615-yGoogle Scholar
  4. C. G. Broyden, J. E. Dennis jun., J. J. More: On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl. 12 (1973) 223–245.https://doi.org/10.1093/imamat/12.3.223Google Scholar
  5. X. Chen: On the convergence of Broyden-like methods for nonlinear equations with nondifferentiable terms, Ann. Inst. Stat. Math. 42/2 (1990) 387–401.https://doi.org/10.1007/BF00050844Google Scholar
  6. X. Chen: Superlinear convergence of smoothing quasi-Newton methods for nonsmooth equations, J. Comput. Appl. Math. 80/1 (1997) 105–126.https://doi.org/10.1016/S0377-0427(97)80133-1Google Scholar
  7. X. Chen, Z. Nashed, L. Qi: Smoothing methods and semismooth methods for nondifferentiable operator equations, SIAM J. Numer. Analysis 38/4 (2000) 1200–1216.https://doi.org/10.1137/S0036142999356719Google Scholar
  8. X. Chen, L. Qi: A parameterized Newton method and a quasi-Newton method for nonsmooth equations, Comput. Optim. Appl. 3/2 (1994) 157–179.https://doi.org/10.1007/BF01300972Google Scholar
  9. J. Chen, L. Qi: Globally and superlinearly convergent inexact Newton-Krylov algorithms for solving nonsmooth equations, Numer. Linear Algebra Appl. 17/1 (2010) 155–174.https://doi.org/10.1002/nla.673Google Scholar
  10. X. Chen, T. Yamamoto: On the convergence of some quasi-Newton methods for nonlinear equations with nondifferentiable operators, Computing 49/1 (1992) 87–94.https://doi.org/10.1007/BF02238652Google Scholar
  11. P. G. Ciarlet: Linear and Nonlinear Functional Analysis with Applications, SIAM, Philadelphia (2013).https://doi.org/10.1137/1.9781611972597Google Scholar
  12. J. E. Dennis jun.: On the convergence of Broyden’s method for nonlinear systems of equations, Math. Comput. 25 (1971) 559–567.https://doi.org/10.1090/S0025-5718-1971-0295560-8Google Scholar
  13. J. E. Dennis jun., J. J. More: 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
  14. A. L. Dontchev: Generalizations of the Dennis-Moré theorem, SIAM J. Optimization 22/3 (2012) 821–830.https://doi.org/10.1137/110833567Google Scholar
  15. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings. A View from Variational Analysis, 2nd ed., Springer, Berlin (2014).https://doi.org/10.1007/978-1-4939-1037-3Google Scholar
  16. A. Griewank: The local convergence of Broyden-like methods on lipschitzian problems in Hilbert spaces, SIAM J. Numer. Analysis 24/3 (1987) 684–705.https://doi.org/10.1137/0724045Google Scholar
  17. J. Han, D. Sun: Newton and quasi-Newton methods for normal maps with polyhedral sets, J. Optimization Theory Appl. 94/3 (1997) 659–676.https://doi.org/10.1023/A:1022653001160Google Scholar
  18. D. M. Hwang, C. T. Kelley: Convergence of Broyden’s method in Banach spaces, SIAM J. Optimization 2/3 (1992) 505–532.https://doi.org/10.1137/0802025Google Scholar
  19. C.-M. Ip, J. Kyparisis: Local convergence of quasi-Newton methods for B-differentiable equations, Math. Programming 56/1 (1992) 71–89.https://doi.org/10.1007/BF01580895Google Scholar
  20. K. Ito, K. Kunisch: Lagrange Multiplier Approach to Variational Problems and Applications, SIAM, Philadelphia (2008).https://doi.org/10.1137/1.9780898718614Google 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. C. T. Kelley: Iterative Methods for Linear and Nonlinear Equations, SIAM, Philadelphia (1995).https://doi.org/10.1137/1.9781611970944Google Scholar
  23. C. T. Kelley, E. W. Sachs: A new proof of superlinear convergence for Broyden’s method in Hilbert space, SIAM J. Optimization 1/1 (1991) 146–150.https://doi.org/10.1137/0801011Google Scholar
  24. F. Kruse: Semismooth implicit functions, J. Convex Analysis 25/2 (2018) 595–622.https://doi.org/10.68381/jca25037Google Scholar
  25. D. Li, M. Fukushima: A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optimization Meth. Software 13/3 (2000) 181–201.https://doi.org/10.1080/10556780008805782Google Scholar
  26. D. Li, M. Fukushima: Globally convergent Broyden-like methods for semismooth equations and applications to VIP, NCP and MCP, Ann. Oper. Res. 103 (2001) 71–97.https://doi.org/10.1023/A:1012996232707Google Scholar
  27. J. Liu, Y. Gao: Inexact-Newton method for solving operator equations in infinite-dimensional spaces, J. Appl. Math. Comput. 22/1-2 (2006) 351–360.https://doi.org/10.1007/BF02896484Google Scholar
  28. F. Mannel, A. Rund: A hybrid semismooth quasi-Newton method for nonsmooth optimal control with PDEs, Optimization Eng. (2020) 1–39, electronic.https://doi.org/10.1007/s11081-020-09523-wGoogle Scholar
  29. J. M. Martínez: Practical quasi-Newton methods for solving nonlinear systems, J. Comput. Appl. Math. 124/1-2 (2000) 97–121.https://doi.org/10.1016/S0377-0427(00)00434-9Google Scholar
  30. J. M. Martínez, L. Qi: Inexact Newton methods for solving nonsmooth equations, J. Comput. Appl. Math. 60/1-2 (1995) 127–145.https://doi.org/10.1016/0377-0427(94)00088-IGoogle Scholar
  31. B. S. Mordukhovich: Variational Analysis and Generalized Differentiation. I: Basic Theory, Springer, Berlin (2005).Google Scholar
  32. J. J. More, J. A. Trangenstein: On the global convergence of Broyden’s method, Math. Comput. 30 (1976) 523–540.https://doi.org/10.1090/S0025-5718-1976-0418451-2Google Scholar
  33. P. Q. Muoi, D. N. Hào, P. Maass, M. Pidcock: Semismooth Newton and quasi-Newton methods in weighted ℓ1 -regularization, J. Inverse Ill-Posed Problems 21/5 (2013) 665–693.https://doi.org/10.1515/jip-2013-0031Google Scholar
  34. F. A. Potra, L. Qi, D. Sun: Secant methods for semismooth equations, Numer. Math. 80/2 (1998) 305–324https://doi.org/10.1007/s002110050369Google Scholar
  35. L. Qi: On superlinear convergence of quasi-Newton methods for nonsmooth equations, Oper. Res. Letters 20/5 (1997) 223–228.https://doi.org/10.1016/S0167-6377(97)00012-6Google Scholar
  36. L. Qi, H. Jiang: Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi-Newton methods for solving these equations, Math. Oper. Res. 22/2 (1997) 301–325.https://doi.org/10.1287/moor.22.2.301Google Scholar
  37. S. M. Robinson: Normal maps induced by linear transformations, Math. Oper. Res. 17/3 (1992) 691–714.https://doi.org/10.1287/moor.17.3.691Google Scholar
  38. E. W. Sachs: Convergence rates of quasi-Newton algorithms for some nonsmooth optimization problems, SIAM J. Control Optimization 23 (1985) 401–418.https://doi.org/10.1137/0323026Google Scholar
  39. E. W. Sachs: Broyden’s method in Hilbert space, Math. Programming 35 (1986) 71–82.https://doi.org/10.1007/BF01589442Google Scholar
  40. D. Sun, J. Han: Newton and quasi-Newton methods for a class of nonsmooth equations and related problems, SIAM J. Optimization 7/2 (1997) 463–480.https://doi.org/10.1137/S1052623494274970Google Scholar
  41. M. Ulbrich: Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, MOS-SIAM Series on Optimization, SIAM, Philadelphia (2011).https://doi.org/10.1137/1.9781611970692Google Scholar
  42. X. Wang, C. Ma, M. Li: A globally and superlinearly convergent quasi-Newton method for general box constrained variational inequalities without smoothing approximation, J. Global Optimization 50/4 (2011) 675–694.https://doi.org/10.1007/s10898-010-9629-2Google Scholar

Suggested citation

F. Mannel, A. Rund. “A Hybrid Semismooth Quasi-Newton Method for Structured Nonsmooth Operator Equations in Banach Spaces.” Journal of Convex Analysis 29 (2022), No. 1, 183–204. https://doi.org/10.68381/jca29011

Download BibTeXPublished by Heldermann Verlag.

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