Questions du sujet
1. Soient C \subset E un ensemble convexe. Soient f et g deux fonctions convexes de C dans \mathbb{R}.\\
(a) Montrer que f + g est convexe, et strictement convexe si l’une des deux fonctions f ou g est strictement convexe.\\
(b) On suppose f strictement convexe. Vérifier que le minimum de f est atteint sur C en au plus un point de C.
2. Soit A \in \mathcal{M}_{m,n}(\mathbb{R}) une matrice de m lignes et n colonnes. On note \langle u, v \rangle_{\mathbb{R}^n} le produit scalaire entre deux vecteurs u et v de \mathbb{R}^n et \langle \mu,\nu \rangle_{\mathbb{R}^m} celui entre deux vecteurs \mu et \nu de \mathbb{R}^m.\\
(a) Montrer que pour tout (x, \nu) \in \mathbb{R}^n \times \mathbb{R}^m, on a\\
\phantom{aaaaaa} \langle Ax, \nu \rangle_{\mathbb{R}^m} = \langle x, A^\top \nu \rangle_{\mathbb{R}^n}\\
où A^\top désigne la matrice transposée de A.\\
(b) En déduire que \ker A \subset (\operatorname{Im} A^\top)^\perp\\
où E^\perp désigne l’orthogonal de E pour le produit scalaire sur \mathbb{R}^n pour tout sous-espace vectoriel E de \mathbb{R}^n.\\
(c) Montrer que \ker A = (\operatorname{Im} A^\top)^\perp
3. On considère un ouvert U \subset \mathbb{R}^n, h : U \rightarrow \mathbb{R} une application \mathcal{C}^1 et b \in \mathbb{R}^m. On suppose qu’il existe x^\ast \in U un minimum de h sur l’ensemble V_b = \{x \in U \mid Ax + b = 0\}.\\
(a) Montrer que pour tout u \in \mathbb{R}^n tel que Au = 0 on a \langle \nabla h (x^\ast), u \rangle_{\mathbb{R}^n} = 0 où \nabla h(x) désigne le gradient de h en x.\\
(b) Montrer l’existence de \nu^\ast \in \mathbb{R}^m tel que \nabla h (x^\ast) – A^\top \nu^\ast = 0.\\
(c) En déduire que l’application L : U \times \mathbb{R}^m \rightarrow \mathbb{R} telle que L(x, \nu) = h(x) – \langle \nu, Ax + b \rangle_{\mathbb{R}^m} vérifie \frac{\partial L}{\partial x_k} (x^\ast, \nu^\ast) = 0 pour tout 1 \leq k \leq n, où \frac{\partial L}{\partial x_k}(x, \nu) désigne la dérivée partielle de L par rapport à la k-ième coordonnée de x \in \mathbb{R}^n.
4. Conclure que si U est convexe, et h convexe sur U, alors L admet un point selle en (x^\ast, \nu^\ast), c’est-à-dire que l’on a\\
L(x^\ast, \nu) \leq L(x^\ast, \nu^\ast) \leq L(x, \nu^\ast)\\
pour tout (x, \nu) \in U \times \mathbb{R}^m.
5. (a) Préciser \varphi(0).\\
(b) Vérifier que \varphi est continue, strictement convexe, positive et que \varphi(x) = 0 si et seulement si x = 1.\\
(c) Montrer que Q_X est convexe et que q \mapsto \mathrm{KL}(q, q’) est strictement convexe, positive et s’annule ssi q = q’.}
6. On définit \overline{c} : X \rightarrow \{0,1\}^* tel que pour tout x \in X, c(x) = c(x)_1 \cdot \overline{c}(x) où c(x)_1 est le premier élément du mot c(x).\\
(a) Vérifier que pour tout x \ne y \in X, si c(x)_1 = c(y)_1 alors \overline{c}(x) \ne \overline{c}(y) et \overline{c}(x) n’est pas un préfixe de \overline{c}(y).\\
(b) Pour a \in \{0,1\} on note X_a = \{x \in X \mid c(x)_1 = a\}. Montrer que si X_a contient au moins deux éléments, alors la restriction de \overline{c} à X_a est un code préfixe sur X_a.\\
(c) En déduire que \sum_{x\in X} 2^{-|c(x)|} \leq 1. \text{ (Ind. : On pourra décomposer la somme en une somme sur $X_0$ et $X_1$ et raisonner par récurrence sur $L(c) = \max\{|c(x)| \mid x \in X\}$.)}
7. Soient q = \left(2^{-|c(x)|}\right)_{x\in X} et X une variable aléatoire à valeurs dans X de loi p.\\
(a) Vérifier que \ln(2)\mathbb{E}(|c(X)|) = -\sum_{x\in X} p_x \ln(q_x).\\
(b) En déduire que \mathbb{E}(|c(X)|) \geq \dfrac{H(p)}{\ln(2)}.\\
\text{ (Ind. : On pourra chercher à exprimer $\ln(2)\mathbb{E}(|c(X)|)$ en fonction de $H(p)$ et $\mathrm{KL}(p,q)$.)}
8. Vérifier que \mathcal{F}(\alpha, \beta) est un ensemble convexe de l’espace vectoriel $E = \mathbb{R}^{I\times J}$.
9. Soient X_1 et X_2 deux variables aléatoires telles que X_1 est à valeurs dans I et X_2 à valeurs dans J.\\
(a) Vérifier que si q \in \mathcal{F}(\alpha, \beta), alors \sum_{i\in I}\sum_{j\in J} q_{ij} = 1.\\
(b) On suppose que \mathbb{P}(X_1 = i, X_2 = j) = q_{ij} avec q \in \mathcal{F}(\alpha, \beta). Calculer la loi de X_1 et celle de X_2 en fonction de \alpha et \beta.\\
(c) Que dire de X_1 et X_2 lorsque q = p~?
10. Soient C = (C_{ij})_{(i,j)\in I\times J} \in \mathbb{R}_+^{I \times J} et \varepsilon > 0. On considère $J_\varepsilon : Q \rightarrow \mathbb{R}$ définie par :\\
J_\varepsilon(q) = \sum_{ij} q_{ij}C_{ij} + \varepsilon\, \mathrm{KL}(q, p)\\
où $\mathrm{KL}(q,p)$ est définie dans la partie précédente en prenant $X = I \times J$.\\
Montrer que $J_\varepsilon$ est strictement convexe sur Q.}
11. (a) Vérifier que $\mathcal{F}(\alpha, \beta)$ est un fermé borné de $\mathbb{R}^{I\times J}$.\\
(b) Montrer qu’il existe un unique $q(\varepsilon) \in Q$ minimisant $J_\varepsilon$ sur $\mathcal{F}(\alpha, \beta)$.\\
(c) En considérant un contre-exemple simple, montrer que l’unicité n’est plus vraie si on suppose que $\varepsilon=0$.
12. (a) Vérifier que $q(\varepsilon)_{ij} > 0$ pour tout $(i,j)\in I\times J$ (\textit{Ind~: On pourra raisonner par l’absurde et considérer pour tout $t\in\,]0,1[$ $q(\varepsilon,t) = (1-t)q(\varepsilon)+tp$ puis observer le comportement de $\varphi(x)$ au voisinage de $x=0$.})\\
(b) Montrer que ceci n’est plus vrai si on suppose que $\varepsilon=0$.
13. (a) Vérifier que $Q_{>0}$ est un ouvert convexe $\mathbb{R}^{I\times J}$.\\
(b) Montrer qu’il existe $(f(\varepsilon),g(\varepsilon))\in \mathbb{R}^I\times \mathbb{R}^J$ tel que $L(q(\varepsilon),(f(\varepsilon),g(\varepsilon)))$ est un point selle de $L$.\\
(\textit{Indication~: On pourra identifier $\mathbb{R}^{I\times J}$ avec $\mathbb{R}^n$ et $\mathbb{R}^I\times \mathbb{R}^J$ avec $\mathbb{R}^m$ pour $n$ cardinal de $I\times J$ et $m$ somme des cardinaux de $I$ et $J$ puis utiliser la question~3 de la partie~I.})
14. (a) Montrer que pour tout $(f,g) \in \mathbb{R}^I \times \mathbb{R}^J$, le minimum de $q \mapsto L(q,(f,g))$ sur $Q_{>0}$ est atteint en $q(f,g)_{ij} = e^{(f_i+g_j-C_{ij})/\varepsilon}p_{ij}$.\\
(b) Calculer la valeur de $G(f,g) = L(q(f,g),(f,g))$.\\
(c) Vérifier que $G$ est concave sur $\mathbb{R}^I\times \mathbb{R}^J$.
15. Vérifier que si $f^\ast : \mathbb{R}^J \rightarrow \mathbb{R}^I$ et $g^\ast : \mathbb{R}^I \rightarrow \mathbb{R}^J$ sont définies par\\
\[
f^\ast(g)_i = -\varepsilon \ln\left(\sum_{j\in J} e^{(g_j-C_{ij})/\varepsilon}\beta_j\right)
\]
et
\[
g^\ast(f)_j = -\varepsilon \ln\left(\sum_{i\in I} e^{(f_i-C_{ij})/\varepsilon}\alpha_i\right)
\]\\
alors pour tout $(f,g)\in \mathbb{R}^I\times \mathbb{R}^J$, on a $\frac{\partial G}{\partial f_i}(f^\ast(g),g) = \frac{\partial G}{\partial g_j}(f,g^\ast(f)) = 0$ pour tout $(i,j)\in I\times J$.}
16. Soit $f^0, g^0 \in \mathbb{R}^{I\times J}$. Pour tout $k\geq 0$, on considère
\[
g^{k+1} = g^\ast(f^k)\quad\text{et}\quad f^{k+1} = f^\ast(g^{k+1})
\]
Montrer que la suite $G(f^k,g^k)_{k\geq 0}$ est croissante.
17. On suppose qu’il existe $f^\infty = (f_i^\infty)_{i\in I}$ et $g^\infty = (g_j^\infty)_{j\in J}$ tels que
\[
|f^k_i – f^\infty_i| \to 0\quad\text{et}\quad |g^k_j – g^\infty_j| \to 0
\]
pour tous $i\in I$ et $j\in J$. On note $G^\ast = \sup\{G(f,g)\mid (f,g)\in \mathbb{R}^I \times \mathbb{R}^J\}$.\\
(a) Montrer que $G(f^\infty, g^\infty) = G^\ast$.\\
(b) Montrer que $G(f(\varepsilon), g(\varepsilon)) = G^\ast$.\\
(c) Montrer qu’il existe une constante $a\in \mathbb{R}$ telle que $f(\varepsilon)_i = f^\infty_i + a$ et $g(\varepsilon)_j = g^\infty_j – a$ pour tout $(i,j)\in I\times J$.\\
(d) En déduire que $q(f^k,g^k) \to q(\varepsilon)$.}