Riemannian trust regions reach an epsilon-gradient iterate

If $M=\mathrm{St}(n,r)$, the real-coordinate Stiefel set is a nonempty compact metric space by [F4], so [F4] gives an attained minimum of $f$. If $M$ is either Grassmannian, let $q$ be its continuous surjective quotient map from the corresponding real or complex Stiefel set. Then $f\circ q$ is continuous on that nonempty compact metric frame set and attains its minimum by [F4]. Surjectivity makes this the minimum of $f$ on $M$. Thus $f_{\inf }$ is finite and attained in every case.

Fix $0<\epsilon \le 1$ and write ${\bar{\delta }}_{\epsilon }=\min \{c_{\delta }\epsilon ,{\mathrm{\Delta }}_{\max }\}$. Whenever $\mathrm{\parallel }{g}_k\mathrm{\parallel }>\epsilon$ and ${\mathrm{\Delta }}_k\le {\bar{\delta }}_{\epsilon }$, the hypotheses of [F2] hold because ${\mathrm{\Delta }}_k\le c_{\delta }\mathrm{\parallel }{g}_k\mathrm{\parallel }$. Thus ${\rho }_k\ge {\eta }_2>{\eta }_1$, and [F1] forbids rejection. Therefore every radius before target is at least $r_{\epsilon }=\min \{{\mathrm{\Delta }}_0,{\gamma }_{\mathrm{d}\mathrm{e}\mathrm{c}}{\bar{\delta }}_{\epsilon }\}>0.$ Indeed the initial radius has this bound; an accepted update does not shrink it, and a rejected update starts above ${\bar{\delta }}_{\epsilon }$ and leaves a radius above ${\gamma }_{\mathrm{d}\mathrm{e}\mathrm{c}}{\bar{\delta }}_{\epsilon }$. Induction proves the claim.

The pointwise gradient convention requires only differentiability. In an orthonormal real tangent basis $e_i$, write $v={\sum }_i{v}_i{e}_i$ and $G={\sum }_{i}d{f}_x(e_i)e_i$. Then $⟨G,v⟩={\sum }_{i}d{f}_x(e_i)v_i=d{f}_x(v)$ by linearity, and if $H$ has the same pairing with every $v$, taking $v=G-H$ gives $\mathrm{\parallel }G-H{\mathrm{\parallel }}^2=0$, hence $G=H$. The zero tangent space has $G=0$. Thus the gradient is well-defined for a $C^2$ objective. For the chosen first-order retraction, $D{R}_x(0)[v]=v$; the chain rule gives $D{\widehat{f}}_x(0)[v]=d{f}_x[v]=⟨g,v⟩$, so the pullback gradient at zero is $g$. All subsequent estimates require only the stated pullback Lipschitz bound and the continuity used in step 1.1.

Choose orthonormal real coordinates on each finite-dimensional tangent or horizontal space. In those coordinates [F3] applies and the matrix norm of $B_x$ is $\mathrm{\parallel }{B}_x{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$. If $\mathrm{\parallel }{g}_k\mathrm{\parallel }>\epsilon$, then $r_{\epsilon }\ge c_R\epsilon ,\min \{{\mathrm{\Delta }}_k,\mathrm{\parallel }{g}_k\mathrm{\parallel }\mathrm{/}\mathrm{\parallel }{B}_{x_k}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\}\ge c_P\epsilon ,$ with the stated infinite-ratio convention when $M_B=0$. The first inequality follows from $\epsilon \le 1$ and the definitions of $r_{\epsilon },c_R$; the second follows from ${\mathrm{\Delta }}_k\ge r_{\epsilon }$, $\mathrm{\parallel }{g}_k\mathrm{\parallel }>\epsilon$, and $\mathrm{\parallel }{B}_{x_k}{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le M_B$. By [F1] and [F3], the selected step has predicted decrease at least the Cauchy fraction, hence at least $\frac{1}{2}{\theta }_C{c}_P{\epsilon }^2$. Every accepted step has ${\rho }_k\ge {\eta }_1$, so its actual decrease is at least $c_S{\epsilon }^2$. Run the update rule without applying the outer cap. If the target were never reached and only finitely many steps were accepted, the resulting infinite block of rejections would keep the point fixed and force its radius to zero by [F8], contradicting the radius floor in step 1.2. Thus the uncapped process must have infinitely many accepted steps unless it reaches the target. By [F7], choose an integer $m>(f(x_0)-f_{\inf })\mathrm{/}(c_S{\epsilon }^2)$. After $m$ accepted steps the objective would be below $f_{\inf }$, a contradiction. Thus the target is reached after finitely many accepted steps. Summing their decreases and using step 1.1 gives $N_s\le \frac{f(x_0)-f_{\inf }}{c_S{\epsilon }^2}\mathrm{.}$

If the initial point already meets the target, then $N_s=N_u=0$ and the bounds hold. Otherwise let ${\mathrm{\Delta }}_T$ be the radius after the accepted step that first reaches the target. Each rejected trial multiplies the radius by ${\gamma }_{\mathrm{d}\mathrm{e}\mathrm{c}}$, and each accepted update multiplies it by a factor $q_j\in [1,{\gamma }_{\mathrm{i}\mathrm{n}\mathrm{c}}]$. Hence ${\mathrm{\Delta }}_T={\mathrm{\Delta }}_0{\gamma }_{\mathrm{d}\mathrm{e}\mathrm{c}}^{N_u}{\prod }_{j=1}^{N_s}{q}_j,{\mathrm{\Delta }}_T\ge r_{\epsilon }$ by step 1.2. Taking logarithms using [F5], then rearranging and using $\log q_j\le \log {\gamma }_{\mathrm{i}\mathrm{n}\mathrm{c}}$, gives $N_u\mathrm{\mid }\log {\gamma }_{\mathrm{d}\mathrm{e}\mathrm{c}}\mathrm{\mid }=\log ({\mathrm{\Delta }}_0\mathrm{/}{\mathrm{\Delta }}_T)+{\sum }_{j=1}^{N_s}\log q_j\le \log ({\mathrm{\Delta }}_0\mathrm{/}{r}_{\epsilon })+N_s\log {\gamma }_{\mathrm{i}\mathrm{n}\mathrm{c}}\mathrm{.}$ This is the asserted rejected-trial bound.

By step 1.1, $f_{\inf }$ is finite. The definitions give $r_{\epsilon }\ge c_R\epsilon$, so [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 \le 1\mathrm{/}{\epsilon }^2$ for $0<\epsilon \le 1$. Thus this radius term is $O({\epsilon }^{-2})$; step 2.2 gives the same order for $N_s$, and step 2.3 gives it for $N_u$. A finite integer outer cap at least the resulting trial bound therefore suffices to return stationary or target-achieved. The algorithm tests zero gradient first, so stationary is possible; either return has gradient norm at most $\epsilon$.