= Solution
Fix an iteration and abbreviate $x=x^k$, $s=s^k$, $d=\nabla f(x)^Ts$. Since $s$ is a <descent direction>, $d<0$. The <directional derivative> gives
$$
f(x+\alpha s)-f(x)-\beta_1\alpha d=(1-\beta_1)\alpha d+o(\alpha).
$$
Choose $\bar\alpha>0$ so that $|o(\alpha)|\leq\tfrac12(1-\beta_1)(-d)\alpha$ for $0<\alpha\leq\bar\alpha$. Then
$$
f(x+\alpha s)-f(x)-\beta_1\alpha d\leq\tfrac12(1-\beta_1)\alpha d<0.
$$
This is the <Armijo condition> for every such positive <step size>, and $\alpha=0$ gives equality. In particular, a <backtracking line search> terminates after finitely many reductions.
Back to article page
