We are given $f \in \mathcal{C}^1(\mathbb{R})$ such that $f'$ is $L$-Lipschitzian, with $L > 0$, and we fix $\tau$ such that $0 < \tau \leq 2/L$. We further suppose that $f$ is $\alpha$-convex, with $\alpha > 0$, that is $$g(x) := f(x) - \frac{1}{2}\alpha x^2 \quad \text{is a convex function on } \mathbb{R}$$ Justify that $f'(x) - \alpha x$ is an increasing function of $x \in \mathbb{R}$. Deduce that $\alpha \leq L$.
We are given $f \in \mathcal{C}^1(\mathbb{R})$ such that $f'$ is $L$-Lipschitzian, with $L > 0$, and $f$ is $\alpha$-convex with $\alpha > 0$, that is $g(x) := f(x) - \frac{1}{2}\alpha x^2$ is a convex function on $\mathbb{R}$. Show that $f(x) \geq f(0) + f'(0)x + \alpha x^2/2$ for all $x \in \mathbb{R}$. Deduce that $f$ admits a minimizer on $\mathbb{R}$.
We are given $f \in \mathcal{C}^1(\mathbb{R})$ such that $f'$ is $L$-Lipschitzian, with $L > 0$, $f$ is $\alpha$-convex with $\alpha > 0$, and $x_*$ denotes a minimizer of $f$. Show that for all $x, y \in \mathbb{R}$ $$\alpha|x-y|^2 \leq \left(f'(x) - f'(y)\right)(x-y)$$
We are given $f \in \mathcal{C}^1(\mathbb{R})$ such that $f'$ is $L$-Lipschitzian, with $L > 0$, $f$ is $\alpha$-convex with $\alpha > 0$, and $x_*$ denotes a minimizer of $f$. Deduce that for all $x, y \in \mathbb{R}$, denoting $\tilde{x} := x - \tau f'(x)$ and $\tilde{y} := y - \tau f'(y)$, we have $$|\tilde{x} - \tilde{y}|^2 \leq |x-y|^2(1 - \alpha\tau(2 - L\tau)).$$
We are given $f \in \mathcal{C}^1(\mathbb{R})$ such that $f'$ is $L$-Lipschitzian, with $L > 0$, $f$ is $\alpha$-convex with $\alpha > 0$, and $x_*$ denotes a minimizer of $f$. We suppose $0 < \tau < 2/L$. Show that $\left|x_n - x_*\right| \leq \rho^n \left|x_0 - x_*\right|$, where $\rho$ is a constant that we will specify, and such that $0 \leq \rho < 1$.
Consider the function $$f(x) := \frac{1}{3}x^3 \quad \text{if } x \geq 0, \quad f(x) := 0 \quad \text{if } x < 0$$ Justify that $f \in \mathcal{C}^1(\mathbb{R})$ and that $f$ is convex. Give the set of its minimizers.
Consider the function $$f(x) := \frac{1}{3}x^3 \quad \text{if } x \geq 0, \quad f(x) := 0 \quad \text{if } x < 0$$ and the sequence $(x_n)_{n \in \mathbb{N}}$ defined by $x_{n+1} := x_n - \tau f'(x_n)$. We suppose in this question that $0 < x_0 < 1/\tau$. a) Justify that the sequence $\left(x_n\right)_{n \in \mathbb{N}}$ is decreasing, with strictly positive values, and satisfies $x_{n+1} = x_n(1 - \tau x_n)$ for all $n \in \mathbb{N}$. b) Justify that $x_n \rightarrow 0$ when $n \rightarrow \infty$. c) Show that $1/x_{n+1} = 1/x_n + \tau/(1 - \tau x_n)$ for all $n \in \mathbb{N}$. Deduce that $x_n \leq x_0/(1 + n\tau x_0)$.
Consider the function $$f(x) := \frac{1}{3}x^3 \quad \text{if } x \geq 0, \quad f(x) := 0 \quad \text{if } x < 0$$ and the sequence $(x_n)_{n \in \mathbb{N}}$ defined by $x_{n+1} := x_n - \tau f'(x_n)$. We suppose only $\tau > 0$. Show that for all $x_0 \in \mathbb{R}$, the sequence $\left(x_n\right)_{n \in \mathbb{N}}$ converges to a minimizer of $f$.
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$. Show that $0 \leq f(x) - f(x_*) \leq |x - x_*||f'(x)|$ for all $x \in \mathbb{R}$.
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)$. Show that for all $n \in \mathbb{N}$, assuming $x_0 \neq x_*$, $$f(x_{n+1}) \leq f(x_n) - \frac{\tau}{2}(2 - \tau L)\frac{\left|f(x_n) - f(x_*)\right|^2}{\left|x_0 - x_*\right|^2}$$ Hint: use question 2.c)
Let $c > 0$, and let $\left(a_n\right)_{n \in \mathbb{N}}$ be a sequence of positive real numbers such that $a_{n+1} \leq a_n - c(a_n)^2$ for all $n \in \mathbb{N}$. Show $a_n \leq a_0/(1 + nca_0)$ for all $n \in \mathbb{N}$. Hint: adapt the reasoning from question 10.c)
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)$. Establish an upper bound for the sequence with general term $a_n := f(x_n) - f(x_*)$. Conclude that $f(x_n) \rightarrow f(x_*)$ when $n \rightarrow \infty$.
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)$. Show that $\frac{\tau}{2}(2 - \tau L)\sum_{0 \leq i < n}\left|f'(x_i)\right|^2 \leq \left(f(x_0) - f(x_n)\right)$ for all $n \in \mathbb{N}^*$. Deduce that $f'(x_n) \rightarrow 0$ when $n \rightarrow \infty$.
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 the sequence $\left(x_n\right)_{n \in \mathbb{N}}$ admits a convergent subsequence. We denote by $\varphi : \mathbb{N} \rightarrow \mathbb{N}$ the extractor and $x_{**}$ the corresponding limit, so that $x_{\varphi(n)} \rightarrow x_{**}$ when $n \rightarrow \infty$. Hint. We may use without proof the Bolzano-Weierstrass theorem: from any bounded sequence in $\mathbb{R}$, we can extract a convergent subsequence. b) Show that $f'(x_{**}) = 0$. c) Deduce that $x_{**}$ is a minimizer of $f$, then that $\left|x_n - x_{**}\right| \rightarrow 0$ when $n \rightarrow \infty$.
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$. Let also $\tau > 0$. Show that the function $F_{x_0}(x) := \frac{1}{2}|x - x_0|^2 + \tau f(x)$ admits a unique minimizer on $\mathbb{R}$, which we will denote $p_f(x_0)$. Hint: We may consider minimizers $x_1$ and $x_2$ of $F_{x_0}$, and note that $$\left|\frac{1}{2}(x_1 + x_2) - x_0\right|^2 < \frac{1}{2}|x_1 - x_0|^2 + \frac{1}{2}|x_2 - x_0|^2 \quad \text{if } x_1 \neq x_2$$
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The operator $p_f$ is defined as the unique minimizer of $F_{x_0}(x) := \frac{1}{2}|x - x_0|^2 + \tau f(x)$. Show that $x_0 \in \mathbb{R}$ is a minimizer of $f$ if and only if $p_f(x_0) = x_0$. Hint: consider the quantity $F_{x_0}((1-t)x_0 + tx_*)$ when $t \rightarrow 0^+$.
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The operator $p_f$ is defined as the unique minimizer of $F_{x_0}(x) := \frac{1}{2}|x - x_0|^2 + \tau f(x)$. In this question only, we suppose that $f \in \mathcal{C}^1(\mathbb{R})$. Show that $x_1 := p_f(x_0)$ satisfies $$x_1 = x_0 - \tau f'(x_1)$$
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $x_{n+1} := p_f(x_n)$, where $p_f(x_0)$ is the unique minimizer of $F_{x_0}(x) := \frac{1}{2}|x - x_0|^2 + \tau f(x)$. In this question only, we set $f(x) := |x|$ for all $x \in \mathbb{R}$. a) Show that $$p_f(x) = \begin{cases} x - \tau & \text{if } x \geq \tau \\ x + \tau & \text{if } x \leq -\tau \\ 0 & \text{otherwise} \end{cases}$$ b) Deduce that $x_n \rightarrow 0$ as $n \rightarrow \infty$, for all $x_0 \in \mathbb{R}$ and $\tau > 0$.
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $x_{n+1} := p_f(x_n)$. Show that $\frac{1}{2}|x_1 - x_0|^2 + \tau f(x_1) \leq \tau f(x_0)$. Deduce that for all integers $N > M \geq 0$ $$\frac{1}{2}\sum_{M < n \leq N}|x_n - x_{n-1}|^2 \leq \tau\left(f(x_M) - f(x_N)\right)$$ Deduce that $|x_{n+1} - x_n| \rightarrow 0$ as $n \rightarrow \infty$.
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $x_{n+1} := p_f(x_n)$. Show that for all $M, N \in \mathbb{N}$ $$|x_N - x_M| \leq \sqrt{2\tau|N-M|}\sqrt{\left|f(x_M) - f(x_N)\right|}$$
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The operator $p_f$ is defined as the unique minimizer of $F_{x_0}(x) := \frac{1}{2}|x - x_0|^2 + \tau f(x)$. Let $x \in \mathbb{R}$ and $\tilde{x} := p_f(x)$. Show that for all $v \in \mathbb{R}$ and $t \in \mathbb{R}$ $$\tau f(\tilde{x}) + \frac{1}{2}|\tilde{x} - x|^2 \leq \tau f(\tilde{x} + tv) + \frac{1}{2}|\tilde{x} + tv - x|^2$$ Let also $y \in \mathbb{R}$, and $\tilde{y} := p_f(y)$. Deduce that $$2\tau(f(\tilde{x}) + f(\tilde{y}) - f(\tilde{x} + tv) - f(\tilde{y} - tv)) \leq |\tilde{x} + tv - x|^2 + |\tilde{y} - tv - y|^2 - |\tilde{x} - x|^2 - |\tilde{y} - y|^2$$
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The operator $p_f$ is defined as the unique minimizer of $F_{x_0}(x) := \frac{1}{2}|x - x_0|^2 + \tau f(x)$. Let $x, y \in \mathbb{R}$, $\tilde{x} := p_f(x)$, $\tilde{y} := p_f(y)$. Show that the right-hand side in inequality $$2\tau(f(\tilde{x}) + f(\tilde{y}) - f(\tilde{x} + tv) - f(\tilde{y} - tv)) \leq |\tilde{x} + tv - x|^2 + |\tilde{y} - tv - y|^2 - |\tilde{x} - x|^2 - |\tilde{y} - y|^2$$ admits the asymptotic expansion $2tv(\tilde{x} - x + y - \tilde{y}) + o(t)$ as $t \rightarrow 0$.
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The operator $p_f$ is defined as the unique minimizer of $F_{x_0}(x) := \frac{1}{2}|x - x_0|^2 + \tau f(x)$. Let $x, y \in \mathbb{R}$, $\tilde{x} := p_f(x)$, $\tilde{y} := p_f(y)$. We choose $v := \tilde{y} - \tilde{x}$ in inequality $$2\tau(f(\tilde{x}) + f(\tilde{y}) - f(\tilde{x} + tv) - f(\tilde{y} - tv)) \leq |\tilde{x} + tv - x|^2 + |\tilde{y} - tv - y|^2 - |\tilde{x} - x|^2 - |\tilde{y} - y|^2$$ Show that the left-hand side is positive for all $t \in [0,1]$. Deduce that $$|\tilde{x} - \tilde{y}|^2 \leq (x-y)(\tilde{x} - \tilde{y}).$$
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $x_{n+1} := p_f(x_n)$. Show that $\left|p_f(x) - p_f(y)\right| \leq |x-y|$ for all $x, y \in \mathbb{R}$. Deduce that the sequence $\left(\left|x_n - x_*\right|\right)_{n \in \mathbb{N}}$ is decreasing.
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $x_{n+1} := p_f(x_n)$. We have a convergent subsequence $x_{\varphi(n)} \rightarrow x_{**}$ as $n \rightarrow \infty$, where $\varphi : \mathbb{N} \rightarrow \mathbb{N}$ is strictly increasing and $x_{**} \in \mathbb{R}$. Show that $x_{\varphi(n)+1} \rightarrow x_{**}$ as $n \rightarrow \infty$, then deduce that $p_f(x_{**}) = x_{**}$.
We consider a convex function $f \in \mathcal{C}(\mathbb{R})$, admitting a minimizer $x_* \in \mathbb{R}$, and $\tau > 0$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $x_{n+1} := p_f(x_n)$. We have established that $p_f(x_{**}) = x_{**}$ for some $x_{**} \in \mathbb{R}$. Conclude that $x_{**}$ is a minimizer of $f$, and that $x_n \rightarrow x_{**}$ as $n \rightarrow \infty$.
We fix an integer $d \in \mathbb{N}^*$, and we equip $\mathbb{R}^d$ with the usual inner product denoted $\langle \cdot, \cdot \rangle$ and the associated Euclidean norm $\|\cdot\|$. We denote $C := \{x \in \mathbb{R}^d \mid \|x\| \leq 1\}$ the closed unit ball of $\mathbb{R}^d$, and we are given $f \in \mathcal{C}^1(\mathbb{R}^d)$. Show that $f$ admits a minimizer on $C$, which we denote $x_*$ in the following questions.
We fix an integer $d \in \mathbb{N}^*$, and we equip $\mathbb{R}^d$ with the usual inner product denoted $\langle \cdot, \cdot \rangle$ and the associated Euclidean norm $\|\cdot\|$. We denote $C := \{x \in \mathbb{R}^d \mid \|x\| \leq 1\}$ the closed unit ball of $\mathbb{R}^d$, and we are given $f \in \mathcal{C}^1(\mathbb{R}^d)$. Let $x_*$ be a minimizer of $f$ on $C$. Suppose in this question that $\|x_*\| < 1$. Show that $\nabla f(x_*) = 0$.
We fix an integer $d \in \mathbb{N}^*$, and we equip $\mathbb{R}^d$ with the usual inner product denoted $\langle \cdot, \cdot \rangle$ and the associated Euclidean norm $\|\cdot\|$. We denote $C := \{x \in \mathbb{R}^d \mid \|x\| \leq 1\}$ the closed unit ball of $\mathbb{R}^d$, and we are given $f \in \mathcal{C}^1(\mathbb{R}^d)$. Let $x_*$ be a minimizer of $f$ on $C$. Suppose in this question that $\|x_*\| = 1$. The objective is to show that $$\exists \lambda \geq 0,\, \nabla f(x_*) = -\lambda x_*.$$ a) Let $x, y \in \mathbb{R}^d$ such that $x \neq y$ and $\|x\| = \|y\| = 1$. Show that $\langle x, v \rangle > 0$ and $\langle y, v \rangle < 0$, where $v := x - y$. b) Suppose by contradiction that (7) is not satisfied. Show that there exists $v \in \mathbb{R}^d$ such that $\langle v, \nabla f(x_*) \rangle > 0$ and $\langle v, x_* \rangle > 0$. Deduce a contradiction and conclude. Hint: consider the quantities $f(x_* - tv)$ and $\|x_* - tv\|^2$, in the limit $t \rightarrow 0^+$.