Finite-budget improved-tangent NEB with a climbing image

Let $U,V,a,b$ satisfy Regular minimum-energy paths on a declared collision-free tube. Inputs: an integer $M\ge 2$, images $R_0=a,R_1,\dots ,R_M=b$ in $U$, spring constant $\kappa \ge 0$, fixed step $\eta >0$, force and spacing tolerances ${\tau }_F,{\tau }_s\ge 0$, an ordinary-step count $n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}\in {\mathbb{N}}_0$, and a finite update budget $N\in {\mathbb{N}}_0$. Require $n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}\le N$. Output: the last chain and one of tolerances-met, tangent-failure, geometry-failure, nonfinite-evaluation, or budget-exhausted.

At each iteration, endpoints are fixed and only interior images are updated. First evaluate $V_i=V(R_i)$ for every image; if any energy is nonfinite, return nonfinite-evaluation before making energy comparisons. For $i=1,\dots ,M-1$, write ${\mathrm{\Delta }}_i^{+}=R_{i+1}-R_i$ and ${\mathrm{\Delta }}_i^{-}=R_i-R_{i-1}$. Select an unnormalized tangent by

${\tau }_i=\{\begin{array}{ll}{\mathrm{\Delta }}_i^{+},& V_{i+1}>V_i>V_{i-1},\\ {\mathrm{\Delta }}_i^{-},& V_{i+1}<V_i<V_{i-1},\\ w_{\max }{\mathrm{\Delta }}_i^{+}+w_{\min }{\mathrm{\Delta }}_i^{-},& \text{otherwise and }{V}_{i+1}>V_{i-1},\\ w_{\min }{\mathrm{\Delta }}_i^{+}+w_{\max }{\mathrm{\Delta }}_i^{-},& \text{otherwise and }{V}_{i+1}<V_{i-1},\\ {\mathrm{\Delta }}_i^{+}+{\mathrm{\Delta }}_i^{-},& V_{i+1}=V_{i-1},\end{array}$

where $w_{\max }=\max (\mathrm{\mid }{V}_{i+1}-V_i\mathrm{\mid },\mathrm{\mid }{V}_{i-1}-V_i\mathrm{\mid })$ and $w_{\min }=\min (\mathrm{\mid }{V}_{i+1}-V_i\mathrm{\mid },\mathrm{\mid }{V}_{i-1}-V_i\mathrm{\mid })$. When $V_{i+1}=V_{i-1}$, the displayed centered-chord branch is the algorithm's explicit tie convention; it is a local completion of the strict-comparison rule in the cited improved-tangent formula. If ${\tau }_i=0$, return tangent-failure; otherwise set $t_i={\tau }_i\mathrm{/}\mathrm{\parallel }{\tau }_i{\mathrm{\parallel }}_2$. Next evaluate $\mathrm{\nabla }V(R_i)$ for every interior image; if any gradient is nonfinite, return nonfinite-evaluation before forming forces.

Initialize the update counter $k=0$. At iteration $k$, use the ordinary force

$F_i=-(I-t_i{t}_i^T)\mathrm{\nabla }V(R_i)+\kappa (\mathrm{\parallel }{\mathrm{\Delta }}_i^{+}{\mathrm{\parallel }}_2-\mathrm{\parallel }{\mathrm{\Delta }}_i^{-}{\mathrm{\parallel }}_2)t_i\mathrm{.}$

When $k\ge n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}$, choose the least index $i_{\ast }$ attaining the largest interior energy and replace that image's force by

$F_{i_{\ast }}^{\mathrm{C}\mathrm{I}}=-\mathrm{\nabla }V(R_{i_{\ast }})+2(\mathrm{\nabla }V(R_{i_{\ast }}{)}^T{t}_{i_{\ast }})t_{i_{\ast }};$

the climbing image has no spring force. The remaining interior images retain the ordinary force. If any resulting force is nonfinite, return nonfinite-evaluation. Thus iterations $k=0,\dots ,n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}-1$ use ordinary forces and the first climbing force is evaluated at iteration $k=n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}$. At each iteration report the maximum force norm and spacing residual ${\max }_i\mathrm{\mid }\mathrm{\parallel }{\mathrm{\Delta }}_i^{+}{\mathrm{\parallel }}_2-\mathrm{\parallel }{\mathrm{\Delta }}_i^{-}{\mathrm{\parallel }}_2\mathrm{\mid }$. Stop with tolerances-met only if both are within their declared tolerances. If a tolerance fails and $k=N$, return budget-exhausted; only when $k<N$ update every interior image by $R_i^{k+1}=R_i^k+\eta F_i^k$. Leaving $U$ returns geometry-failure. After a valid update set $k\leftarrow k+1$ and repeat. The tolerance check precedes the budget check, so $N=0$ still checks the initial chain and $n_{\mathrm{c}\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{b}}=N$ uses a climbing force at the final residual check (without an update if the budget is then exhausted).

The finite stopping status does not assert convergence to a MEP, a saddle, or a continuum path.