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

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(\epsilon^{-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 $\eta = 0$), and specialise its stochastic version to the deterministic gradient-scaled