Abstract.
For a class of semismooth operator equations a mesh independence result for generalized Newton methods is established. The main result states that the continuous and the discrete Newton process, when initialized properly, converge q-linearly with the same rate. The problem class considered in the paper includes MCP-function based reformulations of first order conditions of a class of control constrained optimal control problems for partial differential equations for which a numerical validation of the theoretical results is given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Allgower, E.L., Böhmer, K., Potra, F.A., Rheinboldt, W.C.: A mesh-independence principle for operator equations and their discretizations. SIAM J. Numer. Anal. 23 (1), 160–169 (1986)
Alt, W.: Discretization and mesh-independence of Newton’s method for generalized equations. In: A. Fiacco (ed.), Mathematical programming with data perturbations. Dekker, New York, 1998, pp. 1–30
Arada, N., Casas, E., Tröltzsch, F.: Error estimates for the numerical approximation of a semilinear elliptic control problem. Comp. Optim. Appl. 23 (2), 201–229 (2002)
Argyros, I.K.: A mesh-independence principle for nonlinear operator equations and their discretizations under mild differentiability conditions. Computing 45 (3), 265–268 (1990)
Argyros, I.K.: The asymptotic mesh independence principle for Newton-Galerkin methods using weak hypotheses on the Fréchet derivatives. Math. Sci. Res. Hot-Line 4 (11), 51–58 (2000)
Chen, X., Nashed, Z., Qi, L.: Convergence of Newton’s method for singular smooth and nonsmooth equations using adaptive outer inverses. SIAM J. Optim. 7 (2), 445–462 (1997)
Chen, X., Nashed, Z., Qi, L.: Smoothing methods and semismooth methods for nondifferentiable operator equations. SIAM J. Numer. Anal. 38 (4), 1200–1216 (2000)
De Figueiredo, D.G.: Lectures on the Ekeland Variational Principle with applications and detours. Springer Verlag, Berlin, 1989.
Deuflhard, P., Potra, F.A.: Asymptotic mesh independence of Newton-Galerkin methods via a refined Mysovskii theorem. SIAM J. Numer. Anal. 29 (5), 1395–1412 (1992)
Dontchev, A.L., Hager, W.W., Veliov, V.M.: Uniform convergence and mesh independence of Newton’s method for discretized variational problems. SIAM J. Control Optim. 39 (3), 961–980 (2000)
Facchinei, F., Fischer, A., Kanzow, C., Peng, J.-M.: A simply constrained optimization reformulation of KKT systems arising from variational inequalities. Appl. Math. Optim. 40 (1), 19–37 (1999)
Falk, R.: Approximation of a class of optimal control problems with order of convergence estimates. J. Math. Anal. Appl. 44, 28–44 (1973)
Hintermüller, M., Ito, K., Kunisch, K.: The primal-dual active set strategy as a semi-smooth Newton method. SIAM J. Optim. 13 (3), 865–888 (2003)
Kelley, C.T., Sachs, E.W.: Mesh independence of the gradient projection method for optimal control problems. SIAM J. Control Optim. 30 (2), 477–493 (1992)
Kummer, B.: Newton’s method for nondifferentiable functions. In: J. Guddat, B. Bank, H. Hollatz, P. Kall, D. Klatte, B. Kummer, K. Lommatzsch, K. Tammer, M. Vlach, K. Zimmermann (eds.), Advances in Mathematical Optimization, Akademie-Verlag, Berlin, 1988, pp. 114–125
Kummer, B.: Generalized Newton and NCP-methods: convergence, regularity, actions. Discuss. Math. Differ. Incl. Control Optim. 20 (2), 209–244 (2000)
Ortega, J.M., Rheinboldt, W.C.: Iterative solution of nonlinear equations in several variables. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. Reprint of the 1970 original
Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18 (1), 227–244 (1993)
Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58 (3), 353–367 (1993)
Robinson, S.M.: Newton’s method for a class of nonsmooth functions. Set-Valued Anal. 2 (1-2), 291–305 (1994), Set convergence in nonlinear analysis and optimization
Ulbrich, M.: Nonsmooth Newton-like Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces. Habilitationsschrift, Zentrum Mathematik, Technische Universität München, München, Germany, 2001
Ulbrich, M.: On a nonsmooth Newton method for nonlinear complementarity problems in function space with applications to optimal control. In: M.C. Ferris, O.L. Mangasarian, J.-S. Pang (eds.), Complementarity: Applications, algorithms and extensions (Madison, WI, 1999), Kluwer Acad. Publ., Dordrecht, 2001, pp. 341–360
Ulbrich, M.: Semismooth Newton methods for operator equations in function spaces. SIAM J. Optim. 13 (3), 805–842 (2003)
Ulbrich, M., Ulbrich, S.: Superlinear convergence of affine-scaling interior-point Newton methods for infinite-dimensional nonlinear problems with pointwise bounds. SIAM J. Contr. Optim. 38 (6), 1938–1984 (2000)
Volkwein, S.: Mesh-independence for an augmented Lagrangian-SQP method in Hilbert spaces. SIAM J. Contr. Optim. 38 (3), 767–785 (2000)
Zeidler, E.: Nonlinear Functional Analysis and its Applications II/B. Springer Verlag, Berlin, 1990
Author information
Authors and Affiliations
Corresponding author
Additional information
Mathematics Subject Classification (1991):65J15, 65K10, 49M25, 90C33
Accepted: April 19, 2004
Rights and permissions
About this article
Cite this article
Hintermüller, M., Ulbrich, M. A mesh-independence result for semismooth Newton methods. Math. Program., Ser. A 101, 151–184 (2004). https://doi.org/10.1007/s10107-004-0540-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-004-0540-9