Cauchy-decrease trust-region iterations have liminf gradient norm zero

Fix any $\epsilon >0$ and suppose that $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\ge \epsilon$ for every $k\ge K$. Put $d_{\epsilon }:=\min \{\frac{\epsilon }{2M_B},\frac{{\theta }_C(1-{\eta }_2)\epsilon }{2(L+M_B)}\},{\bar{d}}_{\epsilon }:=\min \{d_{\epsilon },{\mathrm{\Delta }}_{max}\},$ where zero denominators are interpreted as $+\mathrm{\infty }$. Define $r_{\epsilon }:=\min \{{\mathrm{\Delta }}_K,{\gamma }_{dec}{\bar{d}}_{\epsilon }\}>0$. Every radius from index $K$ onward is at least $r_{\epsilon }$: this holds at index $K$; an accepted update does not shrink the radius; and a rejected update can occur only when ${\mathrm{\Delta }}_k>{\bar{d}}_{\epsilon }$, so its new radius is greater than ${\gamma }_{dec}{\bar{d}}_{\epsilon }\ge r_{\epsilon }$. The rejection restriction follows from [F1], [F3], and $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\ge \epsilon$; if ${\bar{d}}_{\epsilon }={\mathrm{\Delta }}_{max}$ then rejection is impossible.

Suppose, for contradiction, that $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\ge \epsilon$ for every $k$ after some index. An infinite block of rejections would give radii ${\gamma }_{dec}^j\mathrm{\Delta }$ tending to zero by [F4], contradicting step 1.1. Thus there are infinitely many accepted steps. At every such sufficiently late step, [F2] and [F1] give $m_k(0)-m_k(p_k)\ge \frac{1}{2}{\theta }_C\epsilon \min \{r_{\epsilon },\epsilon \mathrm{/}{M}_B\}>0,$ using the zero-matrix convention if $M_B=0$. Since acceptance means ${\rho }_k\ge {\eta }_1$, each accepted step decreases $f$ by at least ${\eta }_1$ times this fixed positive quantity. Infinitely many such decreases contradict the lower bound [A1]. Therefore the gradients cannot eventually stay above any $\epsilon >0$.

Put $a_k:=\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$. Since every $a_k\ge 0$, zero is a lower bound of each tail; [F6] therefore gives $0\le i_n\le a_k$ for every $k\ge n$, and [F5] gives ${\mathrm{lim\hspace{0.17em}inf}}_k{a}_k\ge 0$. Suppose instead that ${\mathrm{lim\hspace{0.17em}inf}}_k{a}_k>0$. Choose $\epsilon >0$ strictly below this extended-real value (take $\epsilon =1$ if it is $+\mathrm{\infty }$). If $i_n\le \epsilon$ for every $n$, then [F7] makes $\epsilon$ an upper bound for all $i_n$ and therefore ${\mathrm{lim\hspace{0.17em}inf}}_k{a}_k={\sup }_n{i}_n\le \epsilon$, a contradiction. Thus some $i_N>\epsilon$, and [F6] implies $a_k\ge i_N>\epsilon$ for all $k\ge N$. This contradicts step 2.1. Hence the liminf is zero.