We are given $f \in \mathcal{C}^1(\mathbb{R})$, convex, admitting a minimizer $x_* \in \mathbb{R}$, with $f'$ being $L$-Lipschitzian, and $0 < \tau < 2/L$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $x_{n+1} := x_n - \tau f'(x_n)$. a) Show that for all $x, y \in \mathbb{R}$ $$f(y) \geq f(x) + f'(x)(y-x)$$ Hint: consider a Taylor expansion of the convexity inequality when $t \rightarrow 0^+$. b) Show that for all $x, y \in \mathbb{R}$ $$f(y) \leq f(x) + f'(x)(y-x) + \frac{L}{2}(y-x)^2$$ c) Establish that for all $n \in \mathbb{N}$ $$f(x_{n+1}) \leq f(x_n) - \frac{\tau}{2}(2 - \tau L)\left|f'(x_n)\right|^2$$ Deduce that the sequence $\left(f(x_n)\right)_{n \in \mathbb{N}}$ is decreasing.
We are given $f \in \mathcal{C}^1(\mathbb{R})$, convex, admitting a minimizer $x_* \in \mathbb{R}$, with $f'$ being $L$-Lipschitzian, and $0 < \tau < 2/L$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $x_{n+1} := x_n - \tau f'(x_n)$.\\
a) Show that for all $x, y \in \mathbb{R}$
$$f(y) \geq f(x) + f'(x)(y-x)$$
Hint: consider a Taylor expansion of the convexity inequality when $t \rightarrow 0^+$.\\
b) Show that for all $x, y \in \mathbb{R}$
$$f(y) \leq f(x) + f'(x)(y-x) + \frac{L}{2}(y-x)^2$$
c) Establish that for all $n \in \mathbb{N}$
$$f(x_{n+1}) \leq f(x_n) - \frac{\tau}{2}(2 - \tau L)\left|f'(x_n)\right|^2$$
Deduce that the sequence $\left(f(x_n)\right)_{n \in \mathbb{N}}$ is decreasing.