grandes-ecoles

Q1 Curve Sketching Range and Image Set Determination View

Let $f \in \mathcal{C}(\mathbb{R})$ such that $$\lim_{x \rightarrow -\infty} f(x) = +\infty \quad \text{and} \quad \lim_{x \rightarrow +\infty} f(x) = +\infty$$ a) Show that the set $\{x \in \mathbb{R} \mid f(x) \leq f(0)\}$ is closed and bounded. b) Deduce that there exists $x_* \in \mathbb{R}$ such that $f(x_*) = \min\{f(x) \mid x \in \mathbb{R}\}$.

Q2 Differential equations Higher-Order and Special DEs (Proof/Theory) 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)$.)

Q3 Differential equations Solving Separable DEs with Initial Conditions View

In this question only, we set $f(x) := \frac{1}{2}Lx^2$ for all $x \in \mathbb{R}$, where $L > 0$ is fixed. a) Show that $x_{n+1} = (1 - \tau L)x_n$, then express directly $x_n$ as a function of $x_0$ and $n$. b) We suppose $x_0 \neq 0$. Justify that $x_n \rightarrow 0$ if and only if $0 < \tau < 2/L$.

Q4 Differential equations Higher-Order and Special DEs (Proof/Theory) View

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$.

Q5 Differential equations Higher-Order and Special DEs (Proof/Theory) View

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}$.

Q6 Differential equations Higher-Order and Special DEs (Proof/Theory) View

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)$$

Q7 Applied differentiation Inequality proof via function study View

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)).$$

Q8 Applied differentiation Inequality proof via function study View

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$.

Q9 Stationary points and optimisation Composite or piecewise function extremum analysis View

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.

Q10 Sequences and series, recurrence and convergence Monotonicity and boundedness analysis View

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)$.

Q11 Fixed Point Iteration View

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$.

Q12 Stationary points and optimisation Prove an inequality using calculus-based optimisation View

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.

Q13 Applied differentiation Inequality proof via function study View

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}$.

Q14 Applied differentiation Inequality proof via function study View

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)

Q15 Proof Proof by Induction or Recursive Construction View

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)

Q16 Stationary points and optimisation Existence or properties of extrema via abstract/theoretical argument View

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$.

Q17 Stationary points and optimisation Existence or properties of extrema via abstract/theoretical argument View

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$.

Q18 Stationary points and optimisation Existence or properties of extrema via abstract/theoretical argument View

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$.

Q19 Stationary points and optimisation Existence or properties of extrema via abstract/theoretical argument View

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$$

Q20 Stationary points and optimisation Existence or properties of extrema via abstract/theoretical argument View

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^+$.

Q21 Differential equations Higher-Order and Special DEs (Proof/Theory) View

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)$$

Q22 Differential equations Higher-Order and Special DEs (Proof/Theory) View

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$.

Q23 Differential equations Higher-Order and Special DEs (Proof/Theory) View

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$.

Q24 Inequalities Prove or Verify an Algebraic Inequality (AM-GM, Cauchy-Schwarz, etc.) View

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|}$$

Q25 Differential equations Higher-Order and Special DEs (Proof/Theory) View

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$$

Q26 Differential equations Higher-Order and Special DEs (Proof/Theory) View

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$.

Q27 Proof Deduction or Consequence from Prior Results View

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}).$$

Q28 Proof Proof That a Map Has a Specific Property View

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.

Q29 Proof Deduction or Consequence from Prior Results View

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_{**}$.

Q30 Proof Deduction or Consequence from Prior Results View

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$.

Q31 Proof Existence Proof View

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.

Q32 Proof Direct Proof of a Stated Identity or Equality View

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$.

Q33 Proof Existence Proof View

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^+$.

Q34 Matrices Matrix Algebra and Product Properties View

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$. Let $M$ be a nonzero real symmetric matrix of size $d \times d$ such that $\forall x \in \mathbb{R}^d,\, \langle x, Mx \rangle \geq 0$. We define $f(x) := -\frac{1}{2}\langle x, Mx \rangle$. Show that $\nabla f(x) = -Mx$, for all $x \in \mathbb{R}^d$.

Q35 Matrices Eigenvalue and Characteristic Polynomial Analysis View

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$. Let $M$ be a nonzero real symmetric matrix of size $d \times d$ such that $\forall x \in \mathbb{R}^d,\, \langle x, Mx \rangle \geq 0$. We define $f(x) := -\frac{1}{2}\langle x, Mx \rangle$. Describe the set of minimizers of $f$ on $C$.

Q36 Invariant lines and eigenvalues and vectors Properties of eigenvalues under matrix operations View

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$. Let $M$ be a nonzero real symmetric matrix of size $d \times d$ such that $\forall x \in \mathbb{R}^d,\, \langle x, Mx \rangle \geq 0$. We define $f(x) := -\frac{1}{2}\langle x, Mx \rangle$, so that $\nabla f(x) = -Mx$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $$x_{n+1} := P_C(x_n - \tau \nabla f(x_n)), \quad \text{with} \quad P_C(x) := \begin{cases} x & \text{if } \|x\| \leq 1, \\ x/\|x\| & \text{otherwise.} \end{cases}$$ Suppose in this question that $\|x_0\| \geq 1$. a) Show that $$\forall n \in \mathbb{N} \setminus \{0\},\, x_n = \frac{(\mathrm{I}_d + \tau M)^n x_0}{\|(\mathrm{I}_d + \tau M)^n x_0\|}$$ b) Calculate $\lim_{n \rightarrow \infty} x_n$. Hint. Decompose $x_0 = \sum_{1 \leq i \leq d} \alpha_i e_i$ in an orthonormal basis of eigenvectors $(e_1, \cdots, e_d)$, associated with the eigenvalues $\lambda_1, \cdots, \lambda_d$ of $M$. Introduce the set of indices $I := \{i \in \llbracket 1, d \rrbracket \mid \alpha_i \neq 0\}$, the eigenvalue $\lambda := \max_{i \in I} \lambda_i$, and the vector $x_0' := \sum_{i \in I'} \alpha_i e_i$ where $I' := \{i \in I \mid \lambda_i = \lambda\}$.

Q37 Invariant lines and eigenvalues and vectors Properties of eigenvalues under matrix operations View

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$. Let $M$ be a nonzero real symmetric matrix of size $d \times d$ such that $\forall x \in \mathbb{R}^d,\, \langle x, Mx \rangle \geq 0$. We define $f(x) := -\frac{1}{2}\langle x, Mx \rangle$, so that $\nabla f(x) = -Mx$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $$x_{n+1} := P_C(x_n - \tau \nabla f(x_n)), \quad \text{with} \quad P_C(x) := \begin{cases} x & \text{if } \|x\| \leq 1, \\ x/\|x\| & \text{otherwise.} \end{cases}$$ How does the sequence behave when $\|x_0\| < 1$?

Q38 Invariant lines and eigenvalues and vectors Invariant subspaces and stable subspace analysis View

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$. Let $M$ be a nonzero real symmetric matrix of size $d \times d$ such that $\forall x \in \mathbb{R}^d,\, \langle x, Mx \rangle \geq 0$. We define $f(x) := -\frac{1}{2}\langle x, Mx \rangle$, so that $\nabla f(x) = -Mx$. The sequence $(x_n)_{n \in \mathbb{N}}$ is defined by $$x_{n+1} := P_C(x_n - \tau \nabla f(x_n)), \quad \text{with} \quad P_C(x) := \begin{cases} x & \text{if } \|x\| \leq 1, \\ x/\|x\| & \text{otherwise.} \end{cases}$$ Show that there exists a hyperplane $H \subset \mathbb{R}^d$ such that, for all $x_0 \in \mathbb{R}^d \setminus H$, we have $\lim_{n \rightarrow \infty} f(x_n) = \min\{f(x) \mid x \in C\}$.

grandes-ecoles

Papers (191)

2025 x-ens-maths__psi