Connectez-vous pour consulter le corrigé.
Dans tout le texte, on adopte les notations suivantes :
Pour tout \(n \in \mathbb{N}^*\), on note \(I_n\) la matrice identité de \(\mathcal{M}_{n}(\mathbb{R})\).
Pour tout \((n, p) \in \mathbb{N}^* \times \mathbb{N}^\ast\) et toute matrice \(A \in \mathcal{M}_{n, p}(\mathbb{R})\) on note \(\mathrm{Ker}(A)\) et \(\operatorname{Im}(A)\) les ensembles : \begin{align*} \operatorname{Ker}(A) & =\left\{X \in \mathcal{M}_{p, 1}(\mathbb{R}) \mid A X=0\right\} \\ \operatorname{Im}(A) & =\left\{A X \mid X \in \mathcal{M}_{p, 1}(\mathbb{R})\right\} \end{align*}
Lorsque \(A=[ a ] \in \mathcal{M}_1(\mathbb{R})\), où \(a \in \mathbb{R}\), on identifie \(A\) au réel \(a\).
Pour tout \((i, j) \in \left[\kern-0.15em\left[ {1,n} \right]\kern-0.15em\right]\times \left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right]\), le coefficient situé sur la \(i\)-ème ligne et la \(j\)-ème colonne de \(A\) est noté \(A_{i, j}\).
Si \(X \in \mathcal{M}_{p,1}(\mathbb{R})\) est un vecteur colonne et \(i \in \left[\kern-0.15em\left[ {1,p} \right]\kern-0.15em\right]\), on note \(x_i\) (lettre minuscule) sa \(i\)-ème composante.
Pour \(n \in \mathbb{N}^*\), on note \(\left \langle \cdot , \cdot \right \rangle\) le produit scalaire canonique de \(\mathcal{M}_{n, 1}(\mathbb{R})\) défini par : \[\forall X \in \mathcal{M}_{n, 1}(\mathbb{R}), \ \forall Y \in \mathcal{M}_{n, 1}(\mathbb{R}), \ \langle X, Y\rangle= {}^t\!X Y=\sum_{i=1}^n x_i y_i\]
Pour tout \(X \in \mathcal{M}_{n, 1}(\mathbb{R})\), \(n \in \mathbb{N}^*\), on note \(\|X\|\) la norme euclidienne de \(X\) définie par : \[\|X\|=\sqrt{\left \langle X, X \right \rangle}=\sqrt{ {}^t\!XX}\]
Soit \((\Omega, A, \mathbb{P})\) un espace probabilisé. Toutes les variables aléatoires de cet énoncé sont définies sur cet espace.
Si \(Z\) est une variable aléatoire réelle, on note \(\mathbb{E}(Z)\) son espérance et \(\mathbb{V}(Z)\) sa variance, si elles existent.
Pour tout \(k \in \mathbb{N}^*\), les éléments de \(\mathbb{R}^k\) seront considérés comme des vecteurs colonnes. Autrement dit, et sauf indication du contraire, on confondra \(\mathbb{R}^k\) et \(\mathcal{M}_{k, 1}(\mathbb{R})\).
Dans tout l’énoncé, \(n, m\) et \(p\) désignent trois entiers naturels non nuls avec \(n \geqslant 4\) et \(n \geqslant p\) et \(A\) et \(B\) deux matrices réelles fixées telles que \(A \in \mathcal{M}_{n, p}(\mathbb{R})\) et \(B \in \mathcal{M}_{m, p}(\mathbb{R})\). \(M\) désigne la matrice de \(\mathcal{M}_p(\mathbb{R})\) définie par \(M= {}^t\!A A\) et on pose pour tout \(X \in \mathcal{M}_{p, 1}(\mathbb{R})\) : \[D(X)=M X- {}^t\!A Y\]
On s’intéresse au problème d’optimisation suivant
\[\text { Minimiser\ \ } \frac{1}{2}\, \|A X-Y\|^2+\mu\|B X\|, \ X \in \mathcal{M}_{p, 1}(\mathbb{R}) \text {, }\]
où dans toute la suite, et sauf indication du contraire, \(Y \in \mathcal{M}_{n, 1}(\mathbb{R})\) désigne un vecteur fixé et \(\mu\) un réel donné.
On dira que \(X\) réalise un minimum global d’une fonction \(G\) si \(G(X)\) est un minimum global de \(G\).
L’énoncé comporte trois parties.
La partie I porte sur quelques résultats d’algèbre linéaire qui pourraient être utiles dans les parties II et III. Dans la partie II, on s’intéresse au problème d’optimisation ci-dessus quand \(\mu=0\), \(c^{\prime}\) c’est-à-dire sans le second terme. La partie III est dédiée au problème d’optimisation ci-dessus quand \(\mu=1\). Le mot FIN marque la fin de l’énoncé.
Pour les programmes Python, on dispose d’un
petit formulaire à la fin du sujet. On importe aussi les bibliothèques
suivantes :
import numpy as np import matplotlib.pyplot as plt import numpy.random as rd import numpy.linalg as al
Toute fonction Python écrite en réponse à
une question de l’énoncé peut être utilisée dans les programmes ou
fonctions Python demandés par la suite.
Dans toute cette partie, \(E\) et \(F\) désignent deux espaces euclidiens de dimensions \(p\) et \(n\) respectivement. On note \(\langle\cdot, \cdot\rangle_E\) le produit scalaire de \(E\) et \(\mathcal{B}_E=\left(e_1, e_2, \dots, e_p\right)\) une base orthonormale de \(E\). De même, on note \(\langle\cdot, \cdot\rangle_F\) le produit scalaire de \(F\) et \(\mathcal{B}_F=\left(f_1, f_2, \dots, f_n\right)\) une base orthonormale de \(F\). Si \(G\) est un sous-espace vectoriel de \(E\) (respectivement de \(F\)) on note \(G^{\perp}\) le supplémentaire orthogonal de \(G\) dans \(E\) (respectivement dans \(F\)).
On note \(u\) l’application linéaire de \(E\) dans \(F\) dont la matrice est \(A\) dans les bases \(\mathcal{B}_E\) et \(\mathcal{B}_F\); ainsi \(A=\mathrm{Mat}_{\mathcal{B}_F,\mathcal{B}_E}(u)\).
Soit \(\ell\) une application linéaire de \(E\) dans \(\mathbb{R}\). Montrer qu’il existe un et un seul vecteur \(a_0 \in E\) tel que :
\[\forall x \in E, \ \ell(x)= \left \langle a_0, x \right \rangle_E\]
En déduire que, pour tout \(y \in F\), il existe un seul \(z_y \in E\) tel que :
\[\forall x \in E, \ \langle u(x), y\rangle_F=\left\langle z_y, x\right\rangle_E\]
Montrer que l’application \(u^*:\left\{\begin{array}{lll}F & \rightarrow & E \\ y & \mapsto & z_y\end{array}\right.\) est linéaire.
L’application \(u^*\) s’appelle l’application adjointe de \(u\). On a ainsi l’identité : \[\forall x \in E, \forall y \in F, \ \left \langle u(x), y \right \rangle_F=\left\langle x, u^*(y)\right\rangle_E \tag{1}\]
Montrer que : \[\mathrm{Mat}_{\mathcal{B}_E,\mathcal{B}_F}(u^*)= {}^t\!A\]
et en déduire que : \[\operatorname{rg}(u^*)=\operatorname{rg}(u) \quad \text{et} \quad (u^*)^*=u\]
Montrer que : \[\operatorname{Im}(u^*)=\operatorname{Ker}(u)^{\perp}\]
Montrer que : \[\mathrm{Ker}(u^* \circ u)=\mathrm{Ker}(u)\]
et en déduire que : \[\operatorname{Im}(u^* \circ u)=\operatorname{Im}(u^*)\]
Soit l’application \(w: \operatorname{Im}(u^*) \rightarrow \operatorname{Im}(u^*)\) définie par : \[\forall x \in \operatorname{Im}(u^*), \ w(x)=u^* \circ u(x)\]
Montrer que \(w\) est un isomorphisme et donner une interprétation en terme d’équation matricielle de ce résultat.
Soit \(\pi\) le projecteur orthogonal de \(F\) sur \(\operatorname{Im}(u)\) et \(Q\) sa matrice dans la base \(\mathcal{B}_F\).
Montrer que : \[{}^t\!A Q= {}^t\!A\]
Montrer que \(\operatorname{Tr}(Q)=\operatorname{rg}(u)\).
Montrer que \(M\) est inversible si et seulement si \(A\) est de rang égal à \(p\).
On suppose que le rang de \(A\) est égal à \(p\).
Montrer que
\[Q=A(M)^{-1} \,{}^t\!A\]
Écrire une fonction Python
Calcule_Q(A) qui prend en entrée la matrice \(A\) de type array de taille
\(n \times p\), qui teste si \(A\) est de rang \(p\) et qui renvoie la matrice \(Q\) de la question précédente dans ce cas
et un message d’erreur sinon.
Montrer que pour tout \(X \in \mathcal{M}_{p, 1}(\mathbb{R})\) : \[{}^t\!X M X \geqslant 0\]
Dans cette partie, on s’intéresse à la minimisation de la fonction \(J_0\), définie sur \(\mathcal{M}_{p}(\mathbb{R})\) par :
\[J_0(X)=\frac{1}{2} \, \|A X-Y\|^2, \text { pour tout } X \in \mathcal{M}_{p, 1}(\mathbb{R})\]
Montrer que pour tout \(X \in \mathcal{M}_{p, 1}(\mathbb{R})\) et tout \(H \in \mathcal{M}_{p, 1}(\mathbb{R})\) on a : \[J_0(X+H)-J_0(X)=\left \langle D(X), H \right \rangle +\frac{1}{2} \, {}^t\!H M H \tag{2}\]
Montrer que \(J_0\) possède un minimum global en un point \(X \in \mathcal{M}_{p, 1}(\mathbb{R})\) si et seulement \(D(X)=0\).
On notera dans la suite \(S_0\) l’ensemble : \[S_0=\left\{X \in \mathcal{M}_{p, 1}(\mathbb{R}) \mid D(X)=0\right\}\]
Montrer qu’il existe \(X_0 \in \mathrm{Ker}(A)^{\perp}\) tel que : \[S_0 \cap \mathrm{Ker}(A)^{\perp}=\left\{X_0\right\} .\]
Soit \(X \in S_0\).
Justifier l’identité : \[A X=Q Y \tag{3}\]
Montrer que \(X-X_0 \in \mathrm{Ker}(A)\) et en déduire que si \(X \neq X_0\) alors : \[\|X\|>\left\|X_0\right\|\]
On suppose que le rang de \(A\) est égal à \(p\). Montrer que \(S_0=\{X\}\) avec \[X=M^{-1} \, {}^t\!A Y \tag{4}\]
Dans cette question, on suppose à nouveau que le rang de \(A\) est égal à \(p\) et que \(Y\) s’écrit sous la forme \[Y=A U_0+Z\]
où :
\(U_0\) est un vecteur constant fixé,
\(Z={}^t\!\left(z_1, \cdots, z_n\right)\) où \(z_1, \dots, z_n\) sont des variables aléatoires indépendantes identiquement distribuées suivant une loi normale de paramètres \(\left(0, \sigma^2\right)\) : \[z_i \hookrightarrow \mathcal{N}(0, \sigma^2)\]
On définit \(X\) par la formule (4) (c’est-à-dire \(X=M^{-1 } \,{}^t\!A Y\)). Ainsi les composantes \(y_1, \dots, y_n\) de \(Y\) et les composantes \(x_1, \dots, x_p\) de \(X\) sont toutes des variables aléatoires.
On considère aussi la variable aléatoire : \[T=\left\|A\left(X-U_0\right)\right\|^2 .\]
Montrer que \(T=\|Q Z\|^2= {}^t\!\, Z Q Z\)
Proposer une fonction Python
simuleT(A,sigma) qui prend en argument \(A\) de type array et
sigma de type flottant simulant la variable aléatoire \(T\).
Proposer une fonction Python
esperance(A,sigma) qui prend en argument \(A\) de type array et
sigma de type flottant et qui renvoie une valeur approchée
de l’espérance de \(T\).
Nous avons testé notre algorithme pour \(\sigma=1\) et trois matrices \(A_1, A_2\) et \(A_3\) où \[A_1= \begin{pmatrix} 1 & 0 \\ 2 & 1 \\ 3 & 2 \end{pmatrix}\quad A_2= \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 2 & 1 \\ 4 & 3 & 2 \end{pmatrix}\quad A_3= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 \\ 4 & 3 & 2 & 1 & 0 \\ 5 & 4 & 3 & 2 & 1 \\ 6 & 5 & 4 & 3 & 2 \end{pmatrix}\]
Les résultats obtenus sont \(1,99 \quad 3,01 \quad 4,97\).
Que pouvez-vous conjecturer?
On effectue maintenant le programme suivant
sig=np.arange(1,7)
rep=np.zeros(6)
for k in range(6) :
rep[k]=esperance(A1,sig[k])
plt.plot(sig,rep,"*k")
plt.grid()
plt.show()
On obtient ce graphique :
Que pouvez-vous conjecturer?
Prouvons nos conjectures dans les questions suivantes!
Exprimer \(\mathbb{E}(z_1^2), \mathbb{E}(z_1^3)\) et \(\mathbb{E}(z_1^4)\) en fonction de \(\sigma\).
Montrer que \(T=T_1+2 T_2\) où \(\displaystyle T_1=\sum_{i=1}^n Q_{i, i} z_i^2\) et \(\displaystyle T_2=\sum_{i=1}^n \sum_{j=i+1}^n Q_{i, j} z_i z_j\).
En déduire \(\mathbb{E}(T)\) et vérifier vos conjectures.
Montrer que \(\mathbb{E}(T_1 T_2)=0\).
Notons \(\displaystyle q=\sum_{k=1}^n Q_{k, k}^2\).
Montrer que \(\mathbb{E}(T_1^2)=\sigma^4\left(2 q+p^2\right)\) et \(\displaystyle \mathbb{E}(T_2^2)=\frac{\sigma^4}{2} \left( p-q \right)\).
En déduire que \(\mathbb{V}(T)=2 p \sigma^4\) et montrer pour tout \(\alpha>0\) on a \[\mathbb{P}(T> \left(1+\alpha \right) p \sigma^2) \leqslant \frac{2}{p \alpha^2}\]
Dans cette partie, on suppose à nouveau que \(Y \in \mathcal{M}_{n, 1}(\mathbb{R})\) est un vecteur fixé (et non une variable aléatoire).
On s’intéresse désormais à la fonction \(J\) définie sur \(\mathcal{M}_{p, 1}(\mathbb{R})\) par : \[J(X)=\frac{1}{2} \, \|A X-Y\|^2+\|B X\|, \text { pour } X \in \mathcal{M}_{p, 1}(\mathbb{R})\]
Pour tout \(X \in \mathcal{M}_{p,1}(\mathbb{R})\), on note \(\mathcal{N}(X)\) l’ensemble \[\mathcal{N}(X)=\left\{ {}^t\!B V \mid V \in \mathcal{M}_{m, 1}(\mathbb{R}), \ \|V\| \leqslant 1 \text { et } \|B X\| V-B X=0\right\}\]
Soient \(u\) et \(v\) deux vecteurs de \(\mathbb{R}^n\) tels que \(u \neq 0\). Montrer que : \[\lim _{t \rightarrow 0} \frac{\|u+t v\|-\|u\|}{t}=\frac{\langle u, v\rangle}{\|u\|}\]
Soit \(X_0 \in \mathcal{M}_{p, 1}(\mathbb{R})\) réalisant le minimum global de \(J\). Montrer que si \(B X_0 \neq 0\) alors nécessairement : \[-D(X_0)= {}^t\!B \, \frac{B X_0}{\left\|B X_0\right\|}\]
et en déduire que \(-D(X_0) \in \mathcal{N}\left(X_0\right)\).
Soit \(X_0 \in \mathcal{M}_{p, 1}(\mathbb{R})\) réalisant le minimum global de \(J\) et vérifiant \(B X_0=0\).
Montrer que : \[\forall H \in \mathcal{M}_{n, 1}(\mathbb{R}), \ \left\langle D(X_0), H\right\rangle \leqslant\|B H\|\]
En déduire que : \[D(X_0) \in \mathrm{Ker}(B)^{\perp}\]
En déduire qu’il existe un vecteur \(W \in \mathcal{M}_{m, 1}(\mathbb{R})\) tel que \(D(X_0)= {}^t\!B W\).
En déduire qu’il existe un vecteur \(V \in \mathcal{M}_{p, 1}(\mathbb{R})\) tel que \(D(X_0)= {}^t\!B B V\).
Montrer que \(\|B V\| \leqslant 1\) et en déduire que \(-D(X_0) \in \mathcal{N}(X_0)\).
Soient \(u\) et \(v\) deux vecteurs de \(\mathbb{R}^n\) avec \(u \neq 0\).
Montrer que
\[\|u+v\|^2-\left(\|u\|+\frac{\langle u, v\rangle}{\|u\|}\right)^2=\frac{\|u\|^2\|v\|^2-\langle u, v\rangle^2}{\|u\|^2}\]
En déduire que
\[\|u+v\|-\|u\| \geqslant \frac{\langle u, v\rangle}{\|u\|}\]
Soient maintenant \(X_0, X \in \mathcal{M}_{p, 1}(\mathbb{R})\) et \(W \in \mathcal{N}\left(X_0\right)\).
Montrer que : \[\|B X\|-\left\|B X_0\right\| \geqslant\left\langle W, X-X_0\right\rangle\]
En déduire que :
\[J(X)-J\left(X_0\right) \geqslant\left\langle D(X_0)+W, X-X_0\right\rangle\]
En déduire que \(X_0 \in \mathcal{M}_{p, 1}(\mathbb{R})\) réalise un minimum global de \(J\) si et seulement si
\[-D(X_0) \in \mathcal{N}\left(X_0\right)\]
On se place dans toute la suite dans le cas où \(n=p=m, A=I_{n}\) et \(B\) la matrice diagonale définie par:
\[B_{i, i}= \begin{cases}\alpha_i & \text { si } 1 \leqslant i \leqslant k \\ 0 & \text { si } k+1 \leqslant i \leqslant n\end{cases}\]
où \(k\) est un entier naturel vérifiant \(1 \leqslant k<n\) et \(\alpha_1, \dots, \alpha_k\) sont des nombres réels tous non nuls. On pose : \[\rho(Y)=\sum_{i=1}^k \frac{y_i^2}{\alpha_i^2}\]
On définit la fonction \(F\) de \([0,+\infty[\) dans \(\mathbb{R}\) par : \[\forall \lambda \in\left[0,+\infty\right[, \ F(\lambda)=-1+\sum_{i=1}^k \frac{\alpha_i^2 y_i^2}{\left(\lambda+\alpha_i^2\right)^2}\]
Montrer que : \[\forall \lambda \in \left] 0,+\infty\right[, \ F(\lambda) \leqslant-1+\frac{1}{4 \lambda} \sum_{i=1}^k y_i^2\]
On suppose dans cette question uniquement que \(\rho(Y)>1\). Montrer qu’il existe un et un seul \(\lambda_0 \in \left] 0,+\infty \right[\) tel que \(F(\lambda_0)=0\) et justifier l’inégalité : \[\lambda_0 \leqslant \frac{1}{4} \sum_{i=1}^k y_i^2\]
On pose : \[\beta= \begin{cases}0 & \text { si } \rho(Y) \leqslant 1 \\ \lambda_0 & \text { si } \rho(Y)>1 \end{cases}\]
et : \[X_0=Y-B V\]
où \(V \in \mathcal{M}_{n, 1}(\mathbb{R})\) est défini par : \[v_i= \begin{cases} \displaystyle \frac{\alpha_i y_i}{\beta+\alpha_i^2} & \text { si } 1 \leqslant i \leqslant k \\ \hfill 0 \hfill & \text { si } k+1 \leqslant i \leqslant n \rule[0pt]{0pt}{20pt}\end{cases}\]
Montrer que \(X_0\) réalise un minimum global de \(J\).
Python. On représente les données du
problème :
un tableau monodimensionnel de type array
alpha contenant les valeurs \(\alpha_1, \dots, \alpha_k\),
un tableau monodimensionnel de type array Y contenant le vecteur \(Y\),
un paramètre lda de type flottant représentant un
réel \(\lambda\) supposé
positif,
un paramètre epsilon de type flottant représentant
un réel \(\varepsilon>0\).
Écrire une fonction FoncSom(alpha,Y,lda) qui prend
comme arguments alpha, Y contenant le vecteur
\(Y\), lda et qui renvoie
la valeur \(F(\lambda)\).
Écrire une fonction CalcBeta(alpha,Y,epsilon) qui
prend comme arguments alpha, Y contenant le
vecteur \(Y\), epsilon et
qui renvoie une valeur approchée \(\beta_{{a}}\) du réel \(\beta\) à \(\varepsilon\), trouvée par une méthode de
dichotomie dans l’intervalle \(\left[0,\displaystyle \frac{1}{4} \sum_{i=1}^k
y_i^2\right]\) quand \(\rho(Y)>1\).
Écrire une fonction CalcSolution(alpha,Y,epsilon)
qui prend les mêmes arguments que la fonction CalcBeta et
qui renvoie un tableau monodimensionnel contenant la solution \(X_0\) ci-dessus.
import numpy as np
np.linspace(a,b,n) | Crée une matrice ligne de $n$ valeurs |
|---|---|
| uniformément réparties entre a et b (inclus). | |
np.zeros([n,m]) | Crée la matrice nulle de taille $n \times m$. |
np.zeros(n) | Crée la matrice ligne nulle de taille $n$. |
np.arange(a,b,eps) | Renvoie la liste des flottants de $a$ à $b$ (non compris) |
de pas constant eps. | |
np.shape(M) | Donne la taille de la matrice $M$ sous forme d'un tuple. |
| (couple). | |
np.transpose(M) | Renvoie la transposée de M. |
np.dot(M,P), M.dot(P), M \@ P | 3 instructions synonymes, evaluant le produit matriciel $MP$. |
import nump.linalg as al
al.inv(M) | Renvoie l'inverse de la matrice $M$. |
|---|---|
al.matrix_rank(M) | Renvoie le rang de la matrice $M$. |
al.matrix_power(M,n) | Renvoie la $n$-ième puissance de la matrice $M$. |
import numpy.random as rd
rd. exponential(a,[q, r]) | Simule une réalisation d'une matrice (resp. d'un vecteur) |
|---|---|
rd.exponential(a,n) | aléatoire de dimension $(q, r)$ (resp. $n$) dont les coefficients |
| sont des variables aléatoires indépendantes | |
| qui suivent la loi $\mathcal{E}(\frac{1}{a})$. | |
rd.normal(m,d,[q,r]) | Simule une réalisation d'une matrice (resp. d'un vecteur) |
rd.normal(m,d,n) | aléatoire de dimension $( q, r)$ (resp. $n$) dont les coefficients |
| sont des variables aléatoires indépendantes | |
| qui suivent la loi $\mathcal{N}(m, d^2)$ | |
rd.gamma(m,a,[q,r]) | Simule une réalisation d'une matrice (resp. d'un vecteur) |
rd.gamma(m,a,n) | aléatoire de dimension $( q, r)$ (resp. $n$) dont les coefficients |
| sont des variables aléatoires indépendantes | |
| qui suivent la loi $\Gamma(m, a)$. |
import matplotlib.pyplot as plt
plt.plot(X,Y,options) | Génère la courbe des points définis par les listes $X$ et $Y$ suivant les |
|---|---|
| options graphiques définies par la chaine de caractère options. | |
plt.grid() | Affiche le quadrillage |
plt.show() | Affiche le graphique. |
FIN
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.
Un très joli sujet proposé cette année par l'ESSEC et HEC.
Globalement très difficile, mais il contient un certain nombre de questions "abordables".
Un bon entraînement pour se préparer aux épreuves HEC-ESSEC.