grandes-ecoles 2025 Q2
View
We suppose in this question that $f \in \mathcal{C}^1(\mathbb{R})$ is convex, and that $f'$ is $L$-Lipschitzian, for some $L > 0$. a) Show that for all $x, y \in \mathbb{R}$ $$\left|f'(x) - f'(y)\right|^2 \leq L(x-y)\left(f'(x) - f'(y)\right)$$ b) Let $x, y \in \mathbb{R}$, and let $\tilde{x} := x - \tau f'(x)$ and $\tilde{y} := y - \tau f'(y)$. Show that $$|\tilde{x} - \tilde{y}|^2 \leq |x-y|^2 - \tau(2 - \tau L)(x-y)\left(f'(x) - f'(y)\right)$$ c) We further suppose that $f$ admits a minimizer $x_*$, and that $0 < \tau \leq 2/L$. Show that the sequence $\left(\left|x_n - x_*\right|\right)_{n \in \mathbb{N}}$ is decreasing. (Recall that $\left(x_n\right)_{n \in \mathbb{N}}$ satisfies the recurrence relation $\forall n \in \mathbb{N},\, x_{n+1} := x_n - \tau f'(x_n)$.)