Cubic regularization bounds consecutive unsuccessful trials

Fix a trial point $x$ and a solver-success candidate $s$ that reaches the ratio computation. By [F7], $B={\mathrm{\nabla }}^{2}f(x)$ is symmetric, so the cubic model is defined. Put $\varphi (t):=f(x+ts)$ for $0\le t\le 1$. The Hessian Lipschitz assumption gives $\mathrm{\mid }{\varphi }^{\mathrm{\prime }\mathrm{\prime }}(u)-{\varphi }^{\mathrm{\prime }\mathrm{\prime }}(v)\mathrm{\mid }=\mathrm{\mid }{s}^T({\mathrm{\nabla }}^{2}f(x+us)-{\mathrm{\nabla }}^{2}f(x+vs))s\mathrm{\mid }\le L\mathrm{\mid }u-v\mathrm{\mid }\mathrm{\parallel }s{\mathrm{\parallel }}_2^3,$ where the bound follows from [A1], [F3], and [F4]. Define $h(t):=\varphi (t)-\varphi (0)-t{\varphi }^{\mathrm{\prime }}(0)-\frac{1}{2}{t}^2{\varphi }^{\mathrm{\prime }\mathrm{\prime }}(0)$. For $t>0$, [F5] applied to ${\varphi }^{\mathrm{\prime }}$ on $[0,t]$ gives ${\varphi }^{\mathrm{\prime }}(t)-{\varphi }^{\mathrm{\prime }}(0)=t{\varphi }^{\mathrm{\prime }\mathrm{\prime }}(u_t)$ for some $u_t\in (0,t)$. Hence $\mathrm{\mid }{h}^{\mathrm{\prime }}(t)\mathrm{\mid }=t\mathrm{\mid }{\varphi }^{\mathrm{\prime }\mathrm{\prime }}(u_t)-{\varphi }^{\mathrm{\prime }\mathrm{\prime }}(0)\mathrm{\mid }\le L{t}^2\mathrm{\parallel }s{\mathrm{\parallel }}_2^3$. Applying [F5] to $h$ on $[0,1]$ yields $\mathrm{\mid }f(x+s)-f(x)-⟨\mathrm{\nabla }f(x),s⟩-\frac{1}{2}{s}^T{\mathrm{\nabla }}^{2}f(x)s\mathrm{\mid }\le L\mathrm{\parallel }s{\mathrm{\parallel }}_2^3\mathrm{.}$ By [F2], when $\sigma \ge 3L$ the cubic term dominates this remainder, so $f(x+s)\le m_{\sigma }(s)$. Since the trial reaches the ratio computation, $g\mathrm{\ne }0$ and the algorithm's first two model checks hold; the extended Global cubic minimizers, admissible inexact steps, and cubic Cauchy decrease then gives $m_{\sigma }(0)-m_{\sigma }(s)\ge \sigma \mathrm{\parallel }s{\mathrm{\parallel }}_2^3\mathrm{/}6>0$. Hence $\rho \ge 1>{\eta }_1$; that trial cannot be rejected.

If $3L\le {\sigma }_{min}$, all weights are at least $3L$ and there are no rejections, so take $R=0$. Otherwise, by [F6] choose a finite $R$ with ${\gamma }_{up}^R{\sigma }_{min}\ge 3L$. At the start of any rejection block, $\sigma \ge {\sigma }_{min}$. After at most $R$ consecutive rejections, repeated use of [F1] gives $\sigma \ge \min \{{\gamma }_{up}^R{\sigma }_{min},{\sigma }_{max}\}\ge 3L$. By step 1.1 the next trial cannot be rejected. Thus the block contains at most $R$ rejections.