A finite-budget trust-region method with ratio-based radius updates

Input $f:{\mathbb{R}}^n\to \mathbb{R}$ of class $C^1$, an initial point $x_0$, an initial radius $0<{\mathrm{\Delta }}_0\le {\mathrm{\Delta }}_{max}$, a trial cap $N\in {\mathbb{N}}_0$, a target $\epsilon \ge 0$, constants $0<{\eta }_1<{\eta }_2<1$, $0<{\gamma }_{dec}<1<{\gamma }_{inc}$, $0<{\theta }_C\le 1$, and a declared model-Hessian bound $M_B\ge 0$. At each trial $k$, the supplied symmetric model matrix $B_k$ must satisfy $\mathrm{\parallel }{B}_k{\mathrm{\parallel }}_2\le M_B$. A finite-budget subproblem routine $S$ returns either a vector or failure; its output is treated only as a candidate and is not assumed to minimize the trust-region model. The output is the last accepted point and one of stationary, target-achieved, outer-budget-exhausted, or model-evaluation-failure.

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

1. Set $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. Form $m_k$ from Quadratic trust-region models and the actual-to-predicted reduction ratio, compute the Cauchy step $p_C$ from The Cauchy step for a quadratic trust-region model, and set $P_C:=m_k(0)-m_k(p_C)$. Query $S$ with this model and radius. Use its candidate $q$ only if it is feasible and $m_k(0)-m_k(q)\ge {\theta }_C{P}_C$; otherwise set $p:=p_C$. If it qualifies, set $p:=q$. If $M_B=0$, interpret $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{/}(2M_B)=+\mathrm{\infty }$. Whenever ${\mathrm{\Delta }}_k\le \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{/}(2M_B)$, replace the candidate by $p:=p_C$.
3. Recompute $P_k:=m_k(0)-m_k(p)$. Evaluate ${\rho }_k:=[f(x_k)-f(x_k+p)]\mathrm{/}{P}_k$. If this evaluation is unavailable, return $(x_k,\mathtt{\text{model-evaluation-failure}})$.
4. If ${\rho }_k<{\eta }_1$, reject: set $x_{k+1}:=x_k$ and ${\mathrm{\Delta }}_{k+1}:={\gamma }_{dec}{\mathrm{\Delta }}_k$. Otherwise accept and set $x_{k+1}:=x_k+p$. If ${\rho }_k\ge {\eta }_2$ and $\mathrm{\parallel }p{\mathrm{\parallel }}_2={\mathrm{\Delta }}_k$, set ${\mathrm{\Delta }}_{k+1}:=\min \{{\gamma }_{inc}{\mathrm{\Delta }}_k,{\mathrm{\Delta }}_{max}\}$; in every other accepted case set ${\mathrm{\Delta }}_{k+1}:={\mathrm{\Delta }}_k$.

The finite subproblem budget alone does not imply convergence or a complexity bound.