Finite-budget adaptive regularization using cubic models

Input an open set $U\subseteq {\mathbb{R}}^n$, a twice continuously differentiable $f:U\to \mathbb{R}$, an initial point $x_0\in U$, target $\epsilon \ge 0$, outer trial cap $N\in {\mathbb{N}}_0$, and an exact-Hessian cubic-model solver $S$. Other inputs are $0<{\eta }_1<{\eta }_2<1$, ${\gamma }_{up}>1$, $0<{\gamma }_{down}<1$, $0<\kappa <1$, $0<{\sigma }_{min}\le {\sigma }_0\le {\sigma }_{max}$, $0<{\kappa }_{\theta }<1$, and the finite inner cap $J\in {\mathbb{N}}_0$. On input of the model, $J$, and ${\kappa }_{\theta }$, the solver $S$ returns no-candidate or proposes a vector. A proposed vector is admissible when it passes the model-solution checks below. The solver may return no-candidate if it cannot certify such a vector within its cap. Exact global minimizers are an admissible special case; the local criterion also permits inexact steps satisfying the stated conditions of Global cubic minimizers, admissible inexact steps, and cubic Cauchy decrease ↗.

The output is the last accepted iterate and one of stationary, target-achieved, outer-budget-exhausted, model-solver-failure, inconsistent-model-solver, domain-exit, or regularization-cap-exhausted.

For $k=0,1,\dots ,N$, in order:

1. Compute $g_k:=\mathrm{\nabla }f(x_k)$. If $g_k=0$, return $(x_k,\mathtt{\text{stationary}})$. If $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\le \epsilon$, return $(x_k,\mathtt{\text{target-achieved}})$. If $k=N$, return $(x_k,\mathtt{\text{outer-budget-exhausted}})$.
2. Set $B_k:={\mathrm{\nabla }}^{2}f(x_k)$ and form the model $m_k(s)=f(x_k)+⟨g_k,s⟩+\frac{1}{2}{s}^T{B}_{k}s+\frac{{\sigma }_k}{3}\mathrm{\parallel }s{\mathrm{\parallel }}_2^3$ of The cubic-regularized quadratic model. By The Hessian of a $C^2$ scalar field is symmetric, $B_k$ is symmetric. Put $a_k:=\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$, $q_k:=g_k^T{B}_k{g}_k$, and compute the cubic Cauchy step $s_{C,k}:=-t_{C,k}{g}_k,t_{C,k}:=\frac{-q_k+\sqrt{q_k^2+4{\sigma }_k{a}_k^5}}{2{\sigma }_k{a}_k^3}\mathrm{.}$ Call $S(m_k,J,{\kappa }_{\theta })$. If it returns no-candidate, return $(x_k,\mathtt{\text{model-solver-failure}})$. For a proposed $s_k$, recompute ${\mathrm{pred}}_k:=m_k(0)-m_k(s_k)$ and $\mathrm{\nabla }{m}_k(s_k):=g_k+B_k{s}_k+{\sigma }_k\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2{s}_k$. Check $g_k^T{s}_k+s_k^T{B}_k{s}_k+{\sigma }_k\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2^3=0,s_k^T{B}_k{s}_k+{\sigma }_k\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2^3\ge 0,$ $\mathrm{\parallel }\mathrm{\nabla }{m}_k(s_k){\mathrm{\parallel }}_2\le {\kappa }_{\theta }\min \{1,\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2\}\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2,m_k(s_k)\le m_k(s_{C,k})\mathrm{.}$ If any check fails, or if $s_k=0$ or ${\mathrm{pred}}_k\le 0$, return $(x_k,\mathtt{\text{inconsistent-model-solver}})$.
3. If $x_k+s_k\mathrm{\notin }U$, return $(x_k,\mathtt{\text{domain-exit}})$ without evaluating $f$ there. Otherwise evaluate $f(x_k+s_k)$ and set ${\rho }_k:=[f(x_k)-f(x_k+s_k)]\mathrm{/}{\mathrm{pred}}_k$. If ${\rho }_k<{\eta }_1$, reject the step and keep $x_{k+1}:=x_k$. If ${\sigma }_k={\sigma }_{max}$, return $(x_k,\mathtt{\text{regularization-cap-exhausted}})$; otherwise set ${\sigma }_{k+1}:=\min \{{\gamma }_{up}{\sigma }_k,{\sigma }_{max}\}$ and continue.
4. If ${\rho }_k\ge {\eta }_1$, accept and set $x_{k+1}:=x_k+s_k$. If ${\rho }_k>{\eta }_2$ and $\mathrm{\parallel }{s}_k{\mathrm{\parallel }}_2\ge \kappa \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{/}{\sigma }_k$, set ${\sigma }_{k+1}:=\max \{{\sigma }_{min},{\gamma }_{down}{\sigma }_k\}$; otherwise set ${\sigma }_{k+1}:={\sigma }_k$.

The finite cap, solver failure, inconsistent-solver, domain-exit, and regularization-cap branches are explicit. The model-solution checks include the two cubic conditions (4.1)–(4.2), residual condition TC.s, and the Cauchy-model decrease condition of Cartis–Gould–Toint, Part II, §4. The procedure alone makes no unconditional convergence or evaluation-complexity claim.