Understanding two steps in the proof of Armijo's Convergence Theorem I was reading this paper in which Armijo proves his convergence theorem, and I struggle understanding some of the steps in the proof. The following questions regard the first theorem in the paper, which statement begins at the bottom of page 1.
The paper begins by defining four conditions that the functions the author is working with must satisfy. Important for our purposes is the third condition:

Let $f$ be a real-valued function defined and continuous everywhere on $\mathbb{R}^n$ and bounded below. For a fixed $x_0$ define $S(x_0)=\{x:f(x)\leq f(x_0)\}$. The function $f$ satisfies condition III at $x_0$ if $f\in C^1$ on $S(x_0)$ and $\nabla f(x)$ is Lipschitz continuous on $S(x_0)$, i.e., there exists a Lipschitz constant $K>0$ such that $|\nabla f(y)-\nabla f(x)|\leq K|y-x|$ for every pair $x,y\in S(x_0)$.

I do not think understanding condition IV, which is mentinoned in the theorem, is necessary for my post. In any case all conditions can be found in the first page of the linked paper.


Convergence Theorem: assume $f$ is a real valued function defined and continuous everywhere on $\mathbb{R}^n$, bounded below on $\mathbb{R}^n$, and that conditions III and IV hold at $x_0$.
If $0<\delta \leq 1/4K$ (here $K$ refers to the Lipschitz constant from condition III), then for any $x\in S(x_0)$, the set
$$(1) \ \ S^*(x,\delta)=\{ x_{\lambda} : x_{\lambda} = x - \lambda \nabla f(x), \lambda > 0, f(x_{\lambda}) - f(x) \leq -\delta |\nabla f(x)|^2\}$$
is a nonempty subset of $S(x_0)$ and any sequence $\{ x_k\}^{\infty}_{k=0}$ such that $x_{k+1}\in S^*(x_k, \delta), k=0,1,2,\ldots$, converges to the point $x^*$ which minimizes $f$.


Proof. If $x\in S(x_0)$ with $x_{\lambda}=x-\lambda \nabla f(x)$ and $0\leq \lambda \leq 1/K$, condition III and the mean value theorem imply the inequality
$$(2) \ \ \ \ f(x_{\lambda})-f(x)\leq -(\lambda - \lambda^2K)|\nabla f(x)|^2$$
which in turn implies that $x_{\lambda} \in S^*(x,\delta)$ for
$$(3) \ \ \ \ \lambda_1\leq\lambda\leq\lambda_2, \ \ \ \lambda_i=\frac{1+(-1)^i\sqrt{1-4\delta K}}{2K}$$
so that $S^*(x,\delta)$ is a nonempty subset of $S(x_0)$. If $\{ x_k\}^{\infty}_{k=0}$ is any sequence for which $x_{k+1}\in S^*(x_k, \delta)$, $k=0,1,2,\ldots$, then $(1)$ implies that sequence $\{ f(x_k)\}^{\infty}_{k=0}$ which is bounded below, is monotone nonincreasing and hence that $|\nabla f(x_k)|\rightarrow 0$ as $k\rightarrow \infty$. The remainder of the theorem follows from condition IV.


My questions:

*

*How does Armijo get to the equation $$(2) \ \ \ \ f(x_{\lambda})-f(x)\leq -(\lambda  - \lambda ^2K)|\nabla f(x)|^2 \ \text{?}$$
I suspect the argument goes somewhat like this: by the Mean Value Theorem we have that $$(4) \ \ \ \ |f(x_{\lambda})-f(x)| \leq |\nabla f(x+c(x_{\lambda} - x))||\lambda \nabla f(x)|.$$
Meanwhile condition III gives us $|\nabla f(x_{\lambda})-\nabla f(x)| \leq K|x_{\lambda} - x|$, or, put differently, $$(5) \ \ \ \ |\nabla f(x_{\lambda})| \leq |\nabla f(x)| + K|\lambda \nabla f(x)|=(1+|\lambda |K)|\nabla f(x)|.$$
Now, if we could assume that $|\nabla f(x+c(x_{\lambda} - x))| \leq |\nabla f(x_{\lambda})|$, and that $f(x_{\lambda})\leq f(x)$, then we may combine $(4)$ and $(5)$ to get
$$f(x_{\lambda})-f(x) \leq (1+|\lambda |K)|\nabla f(x)||\lambda \nabla f(x)|=(\lambda + \lambda ^2K)|\nabla f(x)|^2$$
which is similar to $(2)$.


*Why does the sequence $\{ \nabla f(x_k)\} \rightarrow 0$ as $k \rightarrow \infty$ ?

 A: Let us show the relation from the situation in Question 1. There are maybe too many details given, please go over the arguments if they pick from the euro each cent.
The given function $f$ is a function $f:\Bbb R^n\to \Bbb R$. To have an easy notation, i will use $f'$ (instead of $\nabla f$) for the derivative of $f$, which is a function $\Bbb R^n\to \Bbb R^n$, its components are the partial derivatives of $f$.
Fix $x_0\in\Bbb R^n$, in the domain of definition of $f$. Consider (depending on $x_0$) a point $x\in S(x_0)$, i.e. a point with $f(x)\le f(x_0)$. Fix some $\lambda \in[0,\ 1/K]$. Consider the point
$$x_\lambda := x-\lambda f'(x)\in\Bbb R^n\ .$$
Note: This $x_\lambda$ is a bad notation, since if we try to set $\lambda=0$,
thus getting a collision with the fixed $x_0$,
we do not obtain $x_0$, but the point $x$. I will try to avoid confusions resulting from this substitution below.
We will apply now the mean value theorem for the (help) function $h$ in one real variable $t$ given by
$$
h(t) = f(x-tf'(x))\ .
$$
Then using the chain rule, $h'(t)$ is
$$
\begin{aligned}
h'(t)
&=f'(x-tf'(x))\cdot \frac{\partial}{\partial t}(x-tf'(x))
\\
&=f'(x-tf'(x))\cdot(-f'(x))
\\
&=-f'(x-tf'(x))\cdot f'(x)\ ,
\end{aligned}
$$
where the dot stays for the scalar product in $\Bbb R^n$. We apply this for the interval $[0,\lambda]$, so there is a scalar $\xi$ between $0$ and $\lambda$ with
$$
\frac{h(\lambda)-h(0)}{\lambda-0}=h'(\xi)\ .
$$
Above $h(\lambda)=f(x_\lambda)$, $h(0)=f(x)$, so
we get explicitly written:
$$
f(x_\lambda)-f(x) = -\lambda \;f'(\;\underbrace{x-\xi f'(x)}_{:=x_\xi}\;)\cdot f'(x)\ .
$$
Now there is some convexity detail related to
$x_\xi\in S(x_0)$. Then using the Lipschitz condition for $f'$ at $x_\xi$ and $x$ we have
$$
|\ f'(x_\xi)-f'(x)\ |\le K|x_\xi-x|=K\xi\;|f'(x)|\le K\lambda\;|f'(x)|\ .
$$
So the vector $f'(x_\xi)-f'(x)$ is of the shape $K\lambda\;|f'(x)|\; w$
for some $w$ with $|w|\le 1$.
Putting all together:
$$
\begin{aligned}
f(x_\lambda)-f(x)
&=
-\lambda \;f'(x_\xi)\cdot f'(x)
\\
&= 
-\lambda \;\Big(\ f'(x)+K\lambda\;|f'(x)|\; w\ \Big)\cdot f'(x)
\\
&= 
-\lambda \;f'(x)\cdot f'(x)
-K\lambda^2 \;|f'(x)| \; w\cdot f'(x)
\\
&= 
-\lambda \;|f'(x)|^2
-K\lambda^2 \;|f'(x)| \; \underbrace{w\cdot f'(x)}_{\in[\ -|f'(x)|\ ,\ +|f'(x)|\ ]}
\\
&\le
-\lambda \;|f'(x)|^2
+K\lambda^2 \;|f'(x)|^2\\
\\
&=
-(\lambda - K\lambda^2) \;|f'(x)|^2
\ .
\end{aligned}
$$
Point one is done.
$\square$

For Question 2, let us denote by $-M$ some lower bound for $f$.
($M$ is psychologically big and positive.)
We have first from $x_{k+1}\in 
S(x_k,\delta)$ for all $k$ the many estimations
$$
\begin{aligned} 
f(x_2) - f(x_1) &\le -\delta |f'(x_1)|^2\\
f(x_3) - f(x_2) &\le -\delta |f'(x_2)|^2\\
f(x_4) - f(x_3) &\le -\delta |f'(x_3)|^2\\
&\vdots
&&\text{ and so on till}\\
f(x_{n+1}) - f(x_n) &\le -\delta |f'(x_n)|^2\ ,&&\text{ and adding now we get:}\\[3mm]
-M-f(x_1)\le f(x_{n+1}) - f(x_1) &\le -\delta\sum_{1\le k\le n}|f'(x_k)|^2\ .
\end{aligned} 
$$
The R.H.S. is thus bounded from below.
So the series $\displaystyle\sum_{1\le k<\infty}|f'(x_k)|^2$
is bounded from above. Its terms are building a zero-sequence.
(A sequence converging to zero.)
$\square$
