Trust-region first-order complexity counts both successful and unsuccessful trials

Let ${\bar{\delta }}_{\epsilon }:=\min \{c_{\delta }\epsilon ,{\mathrm{\Delta }}_{max}\}$. Every radius during a pre-target trial is at least $r_{\epsilon }=\min \{{\mathrm{\Delta }}_0,{\gamma }_{dec}{\bar{\delta }}_{\epsilon }\}>0.$ Indeed, this holds initially. If a trial is rejected, [F3] implies its radius exceeded ${\bar{\delta }}_{\epsilon }$, since at or below that threshold the ratio is at least ${\eta }_2$; after multiplication by ${\gamma }_{dec}$ the new radius is greater than ${\gamma }_{dec}{\bar{\delta }}_{\epsilon }$. An accepted update does not decrease the radius. Induction proves the bound.

For any nonstationary trial, $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2>0$ and ${\mathrm{\Delta }}_k>0$. By [F2], the Cauchy step has $P_C>0$. The selection rule either chooses a candidate with predicted decrease at least ${\theta }_C{P}_C$, or uses $p_C$; the small-radius override also uses $p_C$. Since $0<{\theta }_C\le 1$, every branch therefore gives $P_k\ge {\theta }_C{P}_C>0$, so the ratio in the algorithm is defined.

If the target were never reached, every rejection block would be finite: an infinite block would multiply a fixed radius by ${\gamma }_{dec}^j\to 0$ by [F8], eventually making $\mathrm{\Delta }\le {\bar{\delta }}_{\epsilon }$, where [F3] forbids rejection. Thus an infinite pre-target run would contain infinitely many accepted trials. For any accepted trial its starting gradient norm $a$ exceeds $\epsilon$. From step 1.1, ${\mathrm{\Delta }}_k\ge r_{\epsilon }\ge c_R\epsilon$, because $\epsilon \le 1$ and $\min \{c_{\delta }\epsilon ,{\mathrm{\Delta }}_{max}\}\ge \epsilon \min \{c_{\delta },{\mathrm{\Delta }}_{max}\}\mathrm{.}$ Since ${\mathrm{\Delta }}_0\ge \epsilon {\mathrm{\Delta }}_0$, taking the minimum with ${\mathrm{\Delta }}_0$ in the definition of $r_{\epsilon }$ gives $r_{\epsilon }\ge c_R\epsilon$. Also $a\mathrm{/}\mathrm{\parallel }{B}_k{\mathrm{\parallel }}_2\ge \epsilon \mathrm{/}{M}_B$, with the stated infinity convention if $M_B=0$. Hence $\min \{{\mathrm{\Delta }}_k,a\mathrm{/}\mathrm{\parallel }{B}_k{\mathrm{\parallel }}_2\}\ge c_P\epsilon \mathrm{.}$ By [F1] and [F2], the predicted reduction is at least $\frac{1}{2}{\theta }_C{c}_P{\epsilon }^2$. Acceptance gives actual decrease at least ${\eta }_1$ times this amount, namely $c_S{\epsilon }^2$. If the target were never reached, after $m$ accepted trials the objective would be at most $f(x_0)-m{c}_S{\epsilon }^2$. By [F7] choose an integer $m>(f(x_0)-f_{inf})\mathrm{/}(c_S{\epsilon }^2)$; this contradicts [A3]. Therefore the target is reached after finitely many accepted trials. Summing their decreases gives $N_s{c}_S{\epsilon }^2\le f(x_0)-f_{inf}$, the claimed successful-step bound.

Let ${\mathrm{\Delta }}_T$ be the radius after the accepted trial that first reaches the target. Each rejected trial multiplies the radius by ${\gamma }_{dec}$; each accepted update multiplies it by some $r_j\in [1,{\gamma }_{inc}]$. Therefore ${\mathrm{\Delta }}_T={\mathrm{\Delta }}_0{\gamma }_{dec}^{N_u}{\prod }_{j=1}^{N_s}{r}_j\mathrm{.}$ Step 1.1 gives ${\mathrm{\Delta }}_T\ge r_{\epsilon }$. By [F5], $\log {\gamma }_{dec}<0$, and logarithms of positive products give $\log {\mathrm{\Delta }}_T=\log {\mathrm{\Delta }}_0+N_u\log {\gamma }_{dec}+{\sum }_{j=1}^{N_s}\log r_j\mathrm{.}$ Rearranging and using $\log r_j\le \log {\gamma }_{inc}$ yields $N_u\mathrm{\mid }\log {\gamma }_{dec}\mathrm{\mid }=\log ({\mathrm{\Delta }}_0\mathrm{/}{\mathrm{\Delta }}_T)+{\sum }_{j=1}^{N_s}\log r_j\le \log ({\mathrm{\Delta }}_0\mathrm{/}{r}_{\epsilon })+N_s\log {\gamma }_{inc},$ which proves the rejection bound, including every rejected trial.

Since $r_{\epsilon }\ge c_R\epsilon$ for $0<\epsilon \le 1$, [F5] gives $\log ({\mathrm{\Delta }}_0\mathrm{/}{r}_{\epsilon })\le \log ({\mathrm{\Delta }}_0\mathrm{/}(c_R\epsilon ))=\log ({\mathrm{\Delta }}_0\mathrm{/}{c}_R)+\log (1\mathrm{/}\epsilon )\mathrm{.}$ By [F6], $\log (1\mathrm{/}\epsilon )\le 1\mathrm{/}\epsilon$; since $0<\epsilon \le 1$, $1\mathrm{/}\epsilon \le 1\mathrm{/}{\epsilon }^2$. Thus the radius term is $O({\epsilon }^{-2})$, as is $N_s$ by step 2.1, so $N_s+N_u=O({\epsilon }^{-2})$. If the finite outer cap allows at least that many trials, the process reaches the target before the cap.

On an accepted trial, ${\rho }_k\ge {\eta }_1>0$ and $P_k>0$ by step 1.2. Thus $f(x_{k+1})=f(x_k)-{\rho }_k{P}_k<f(x_k)$, proving strict decrease at every accepted trial.