Finite-budget Riemannian trust-region method

Let $1\le r\le n$. Let $M$ be a real Stiefel manifold $\mathrm{St}(n,r)$, a real Grassmannian $\mathrm{Gr}(r,n)$, or a complex Grassmannian ${\mathrm{Gr}}_{\mathbb{C}}(r,n)$, with each tangent space regarded as a real inner-product space under the corresponding Frobenius metric. On a real Stiefel manifold or real Grassmannian choose the induced map of either the real QR or real polar formula from QR and polar retractions on Stiefel and Grassmann; on a complex Grassmannian choose the complex polar map from Polar retraction on the complex Grassmannian. Denote the chosen map by $R$. Let $f:M\to \mathbb{R}$ be of class $C^2$ and take an initial point $x_0\in M$. For this regularity, $\mathrm{grad}f(x)$ denotes the pointwise metric dual of $d{f}_x$: in any orthonormal real basis $e_i$ of $T_{x}M$, it is ${\sum }_{i}d{f}_x(e_i)e_i$ (the empty sum is zero). This convention agrees with The Riemannian gradient is the metric dual of the differential when $f$ is smooth; no infinitely differentiable gradient field is required.

Fix $0<{\eta }_1<{\eta }_2<1$, $0<{\gamma }_{\mathrm{d}\mathrm{e}\mathrm{c}}<1<{\gamma }_{\mathrm{i}\mathrm{n}\mathrm{c}}$, $0<{\theta }_C\le 1$, a declared model-operator bound $M_B\ge 0$, a maximum radius ${\mathrm{\Delta }}_{\max }>0$, an initial radius $0<{\mathrm{\Delta }}_0\le {\mathrm{\Delta }}_{\max }$, target $\epsilon \ge 0$, and finite outer cap $N\in {\mathbb{N}}_0$. Supply as input a rule that evaluates a family $x\mapsto B_x$ of self-adjoint real-linear operators $B_x:T_{x}M\to T_{x}M$ at each visited point. On a Grassmannian, represent this intrinsic operator on the current horizontal space, consistently under changes of frame. Require $\mathrm{\parallel }{B}_x{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le M_B$ for every $x\in M$, where $\mathrm{\parallel }{B}_x{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}:={\sup }_{s\mathrm{\ne }0}\frac{\mathrm{\parallel }{B}_{x}s\mathrm{\parallel }}{\mathrm{\parallel }s\mathrm{\parallel }},$ with $\mathrm{\parallel }{B}_x{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}=0$ when the tangent space is $\{0\}$. Supply a subproblem routine $S$ with a finite operation cap $J_S\in {\mathbb{N}}_0$; on input of the current model $m_k$, radius ${\mathrm{\Delta }}_k$, and tangent or horizontal space, it terminates within that cap and returns either a vector in that space or failure. No quality guarantee is required because the returned vector is checked below.

Starting with $x_0$ and ${\mathrm{\Delta }}_0$, process $k=0,\dots ,N$ in order:

1. Set $g_k=\mathrm{grad}f(x_k)$. Return $(x_k,\mathtt{\text{stationary}})$ if $g_k=0$, $(x_k,\mathtt{\text{target-achieved}})$ if $\mathrm{\parallel }{g}_k\mathrm{\parallel }\le \epsilon$, and $(x_k,\mathtt{\text{outer-budget-exhausted}})$ if $k=N$.
2. Form the real pullback quadratic model $m_k(s)=f(x_k)+⟨g_k,s⟩+\frac{1}{2}⟨s,B_{x_k}s⟩\mathrm{.}$ With $c_k=⟨g_k,B_{x_k}{g}_k⟩$, set ${\tau }_k=\{\begin{array}{ll}{\mathrm{\Delta }}_k\mathrm{/}\mathrm{\parallel }{g}_k\mathrm{\parallel },& c_k\le 0,\\ \min \{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}^2\mathrm{/}{c}_k,{\mathrm{\Delta }}_k\mathrm{/}\mathrm{\parallel }{g}_k\mathrm{\parallel }\},& c_k>0,\end{array}{p}_C=-{\tau }_k{g}_k,$ and set $P_C=m_k(0)-m_k(p_C)$.
3. Call $S$ on $(m_k,{\mathrm{\Delta }}_k)$ in the current tangent or horizontal space. If it returned a vector $q$ with $\mathrm{\parallel }q\mathrm{\parallel }\le {\mathrm{\Delta }}_k$ and $m_k(0)-m_k(q)\ge {\theta }_C{P}_C$, set $p_k=q$; otherwise set $p_k=p_C$. If ${\mathrm{\Delta }}_k\le \mathrm{\parallel }{g}_k\mathrm{\parallel }\mathrm{/}(2M_B)$, replace the candidate by $p_k=p_C$, interpreting that threshold as $+\mathrm{\infty }$ when $M_B=0$. Set $P_k=m_k(0)-m_k(p_k)$.
4. If $P_k\le 0$, return $(x_k,\mathtt{\text{model-evaluation-failure}})$. Otherwise evaluate $y_k=R_{x_k}(p_k)$; if the selected retraction is unavailable, return $(x_k,\mathtt{\text{model-evaluation-failure}})$. If $f(y_k)$ cannot be evaluated, return the same status. Otherwise set ${\rho }_k=(f(x_k)-f(y_k))\mathrm{/}{P}_k$.
5. If ${\rho }_k<{\eta }_1$, reject and set $(x_{k+1},{\mathrm{\Delta }}_{k+1})=(x_k,{\gamma }_{\mathrm{d}\mathrm{e}\mathrm{c}}{\mathrm{\Delta }}_k)$. Otherwise accept and set $x_{k+1}=y_k$. If also ${\rho }_k\ge {\eta }_2$ and $\mathrm{\parallel }{p}_k\mathrm{\parallel }={\mathrm{\Delta }}_k$, set ${\mathrm{\Delta }}_{k+1}=\min \{{\gamma }_{\mathrm{i}\mathrm{n}\mathrm{c}}{\mathrm{\Delta }}_k,{\mathrm{\Delta }}_{\max }\}$; in every other accepted case set ${\mathrm{\Delta }}_{k+1}={\mathrm{\Delta }}_k$.

Return the last accepted point with the corresponding stop status. A failed finite subproblem call, infeasible candidate, or candidate that misses the fraction-of-Cauchy test uses $p_C$.