Trust Region Algorithms and Timestep Selection (Q4699110)

Unconstrained optimization problems are closely related to systems of ordinary differential equations (ODEs) with gradient structure. In this work, the author proves results that apply to both areas. He analyzes the convergence properties of a trust region, or Levenberg-Marquardt, algorithm for optimization. The algorithm may also be regarded as a linearized implicit Euler method with adaptive timestep for gradient ODEs. From the optimization viewpoint, the algorithm is driven directly by the Levenberg-Marquardt parameter rather than the trust region radius. The author gives a rigorous error analysis for the algorithm establishing global convergence and an unusual, extremely rapid, type of superlinear convergence. It is also shown how an inexpensive change to the algorithm leads to quadratic convergence. From the ODE viewpoint, the work contributes to the theory of gradient stability by presenting an algorithm that reproduces the correct global dynamics and gives very rapid local convergence to a stable steady state.