A survey of trust-region radius update mechanisms. Part I: First-order analysis

Abstract

We isolate three structural conditions on trust-region radius update rules for smooth unconstrained nonlinear optimisation, and study the class of mechanisms they define. The conditions act on the radius directly: a lower bound relative to the gradient norm, a contraction on unsuccessful iterations, and a controlled expansion on successful ones. A mechanism is \emph{weakly admissible} if it satisfies the first two conditions, and \emph{strongly admissible} if it satisfies the lower bound together with the controlled-expansion condition. Under uniformly bounded model Hessians, weak admissibility yields $\lim_{k\to\infty}\|\nabla f(x_k)\|=0$, and strong admissibility yields the optimal worst-case complexity $O(ε^{-2})$ for first-order stationarity. Strong admissibility extends the convergence guarantee to linearly growing model Hessians. We verify admissibility for five mechanism classes: fixed-factor, step-driven, retrospective, criticality-anchored, and gradient-scaled. Along the way, we prove convergence of the retrospective update under linearly growing model Hessians and revisit the framework of Curtis and Scheinberg (2020), and Wang and Yuan (2022): we extend it to three distinct scaling factors with decoupled step acceptance (covering $η= 0$), and specialise its stochastic version to the deterministic gradient-scaled