Armijo backtracking terminates for strict descent directions

By linearity of $Df(x)$ and its values on the standard basis, $Df(x)[p]=⟨\mathrm{\nabla }f(x),p⟩$. In the gradient branch, if $\mathrm{\nabla }f(x)\mathrm{\ne }0$, then $Df(x)[-\mathrm{\nabla }f(x)]=-\mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}^2<0$ by [F1]. In the Newton branch, write $g=\mathrm{\nabla }f(x)$ and $Hp=-g$. If $g\mathrm{\ne }0$, then $p\mathrm{\ne }0$ by [F4] and $Df(x)[p]=g^{T}p=-p^{T}Hp<0$, since $H$ is symmetric positive definite by [F2] and [F4].

Set $d:=-Df(x)[p]>0$. Fréchet differentiability gives $[f(x+tp)-f(x)]\mathrm{/}t\to -d$ as $t\downarrow 0$. Choose $\delta >0$ small enough that $x+tp\in U$ and this quotient is less than $-d+(1-\alpha )d\mathrm{/}2=-(1+\alpha )d\mathrm{/}2\le -\alpha d$ whenever $0<t<\delta$. Then every such trial satisfies the Armijo test.

The trials are $t_n={\beta }^n$. Put $c={\beta }^{-1}-1>0$. By [F5], ${\beta }^{-n}=(1+c{)}^n\ge 1+nc$, hence $t_n\le (1+nc{)}^{-1}$. By [F6], for any $\delta >0$ some $n$ is large enough that $(1+nc{)}^{-1}<\delta$; thus $t_n\to 0$.

Step 1.2 supplies a positive interval of accepted trial sizes. The geometric sequence shown in step 1.3 eventually tests such a size, so the prescribed loop accepts after finitely many reductions in either algorithm.