Backward Step Control globalization for Newton-type methods: Dr. Andreas Potschka (IWR Heidelberg)

ABSTRACT: We present a step size selection method for the globalization of
convergence of Newton-type methods for nonlinear root finding problems
and its generalization to a Hilbert space setting. The approach
generalizes on the well-known interpretation of the Newton method as an
explicit Euler time-stepping scheme for the Davidenko differential
equation to the setting of Newton-type directions that may deviate from
the exact Newton direction. The advantages of the globalization strategy
comprise a simple yet efficient implementation and a rigorous
convergence analysis based on generalized Newton paths, which are the
solution to an inital value problem of an appropriate generalization of
the Davidenko differential equation. Under reasonable assumptions, the
results of the convergence analysis include full steps in the vicinity
of a solution, a uniform lower step size bound, a priori guarantees for
the nonlinear decrease of the residual norm, and convergence to a
distinguished root, namely the end point of the generalized Newton path
emanating from the initial guess. In addition, the framework delivers
suitable relative termination tolerances for inexact residual minimizing
Krylov--Newton methods and can be utilized to derive general purpose
adaptive grid refinement strategies for finite element discretizations
of elliptic PDE problems. For optimization problems, the idea of
Backward Step Control can be applied within a generic homotopy approach.
We conclude the talk with numerical results for the unconstrained
optimization problems of the CUTEst test set and for the minimal surface
PDE.