From 5a3533fa3f2fb02fd3cda2b546549a61b8d0407b Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Tue, 1 Jun 2010 17:14:08 +0200
Subject: Progrès pour univers fini et début pour univers convexe
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

- introduction pour la partie univers fini
- traitement du cas avec information totale à part
- simplification du début de la preuve du résultat principal
à l'aide du cas full info
- reprise de la fin de cette preuve en tenant compte des
modifications sur le début
- appendice sur les projections sur convexes
- cas full info pour les univers convexes
---
 rapport.tex | 387 ++++++++++++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 310 insertions(+), 77 deletions(-)

(limited to 'rapport.tex')

diff --git a/rapport.tex b/rapport.tex
index 8716905..c40dae6 100644
--- a/rapport.tex
+++ b/rapport.tex
@@ -2,8 +2,9 @@
 \usepackage[french]{babel}
 \usepackage[utf8x]{inputenc}
 \usepackage[T1]{fontenc}
-\usepackage{amsmath,amssymb,amsthm,calc}
+\usepackage{calc,amsmath,amssymb,amsthm}
 \usepackage[hmargin=3.5cm]{geometry}
+\usepackage{}
 \newcommand{\trib}[1]{\mathcal{#1}}
 \newcommand{\set}[1]{\mathbf{#1}}
 \newcommand{\esp}[1]{\mathbb{E}\left[#1\right]}
@@ -12,18 +13,25 @@
 \renewcommand{\geq}{\geqslant}
 \renewcommand{\leq}{\leqslant}
 \newsavebox{\fmbox}
-  
 \newenvironment{encadre}[1]{\begin{lrbox}{\fmbox}%
 \begin{minipage}{\textwidth-3em}\vspace{\baselineskip}}{\vspace{0.5\baselineskip
 } \end{minipage} \end{lrbox} \begin{center}
 \fbox{\hspace{1em}\usebox{\fmbox}\hspace{1em}}\end{center}}
-\author{Thibaut Horel}
 
-\title{Bandits à $n$ bras}
+\author{Thibaut Horel}
+\title{Prédiction de suites individuelles}
 \date{sujet encadré par Gilles Stoltz}
 
+\newtheoremstyle{remark}
+  {}%      Space above, empty = `usual value'
+  {}%      Space below
+  {}% Body font
+  {}%         Indent amount (empty = no indent, \parindent = para indent)
+  {\scshape}% Thm head font
+  {.}%        Punctuation after thm head
+  { }%     Space after thm head: " " = normal interword space;
+  {}% Thm head spec
 
-\begin{document}
 \theoremstyle{definition}
 \newtheorem{prop}{Proposition}[section]
 \newtheorem{thm}[prop]{Théorème}
@@ -31,16 +39,68 @@
 \newtheorem{lem}[prop]{Lemme}
 \newtheorem*{defi}{Définition}
 
+\theoremstyle{remark}
+\newtheorem*{rem}{Remarque}
+
+\begin{document}
+
 \maketitle
 
-\section{Bandits à $N$ bras déterministes}
+\section{Prédiction randomisée dans un univers fini}
 
-\subsection{Stratégie et résultat}
-On utilise la stratégie de prédiction suivante :
+\subsection{Introduction (A DETAILLER)}
+$N$ le nombre d'actions.
+
+Une stratégie est une suite de lois de probabilités
+$(\mathbf{p_t})_{t\in\set{N}^*}$ avec $\mathbf{p_t}\in\set{R}^N$.
+
+La stratégie de l'adversaire est une suite de vecteur de pertes
+$(\mathbf{l_t})_{t\in\set{N}^*}$ avec $\mathbf{l_t}\in\set{R}^N$.
+
+À chaque tour, on tire $I_t$ suivant la loi $\mathbf{p_t}$.
+
+On définit le regret pour la stratégie $\mathbf{p}$ contre la stratégie
+$\mathbf{l}$ :
+\[
+R_T(\mathbf{p},\mathbf{l})=\sum_{t=1}^T l_{I_t,t}-\min_{1\leq i\leq N}L_{i,T}
+\]
+et le regret espéré :
+\[
+R_T^*(\mathbf{p},\mathbf{l}) =
+\sum_{t=1}^T\sum_{i=1}^N p_{i,t}l_{i,t}
+-\min_{1\leq i\leq N}L_{i,T}
+\]
+
+Si l'on souhaite raisonner avec les gains, en posant $g_{i,t}=1-l_{i,t}$, on
+définit le regret en terme de gains :
+\[
+R_T(\mathbf{p},\mathbf{g})=
+\max_{1\leq i\leq N}G_{i,T}
+-\sum_{t=1}^T g_{I_t,t}
+\]
+et le regret espéré en termes de gains :
+\[
+R_T^*(\mathbf{p},\mathbf{g}) =
+\max_{1\leq i\leq N}G_{i,T}
+-\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}
+\]
+
+\begin{rem}
+Les symboles $R_T$ et $R_T^*$ n'ont pas la même définition suivant que l'on
+parle de gains et de pertes. Si $\mathbf{g}$ est la suite de gains associée à
+la suite de pertes $\mathbf{l}$, on a les égalités :
+\[
+R_T(\mathbf{p},\mathbf{l})=R_T(\mathbf{p},\mathbf{g})
+\quad\mathrm{et}\quad
+R_T^*(\mathbf{p},\mathbf{l})=R_T^*(\mathbf{p},\mathbf{g})
+\]
+\end{rem}
+
+\subsection{Stratégie exponentielle et information totale}
 
 \begin{encadre}{\textwidth}
 \begin{center}
-\textbf{Algorithme Exp3.P}
+\textbf{Stratégie par poids exponentiels}
 \end{center}
 
 \textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/N$ pour
@@ -50,97 +110,159 @@ $i\in\{1,\ldots,N\}$.
 
 \begin{enumerate}
 \item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
-$(p_{1,t},\ldots,p_{N,t})$.
-\item On estime les gains $(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{N,t})$ à
-partir du gain observé $g_{I_t,t}$
-\[
-\widetilde{g}_{i,t}=\frac{1}{p_{i,t}}\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}
-+\beta\right)
-\]
-
+$\mathbf{p_t}=(p_{1,t},\ldots,p_{N,t})$.
+\item On observe les gains $\mathbf{g_t}=(g_{1,t},\ldots,g_{N,t})$.
 \item On met à jour les poids exponentiels :
-$w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{g}_{i,t})$.
+$w_{i,t}=w_{i,t-1}\exp(\eta g_{i,t})$.
 \item On calcule la distribution pour le tour suivant :
-\[p_{i,t+1}=(1-\gamma)\frac{w_{i,t}}{W_t}+\frac{\gamma}{N}
-\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)\]
+\[
+p_{i,t+1}=w_{i,t}/W_t
+\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)
+.\]
 \end{enumerate}
 \end{encadre}
 
-
-\begin{thm}
-Avec  :
-\[\beta\leq 1,\quad
-\gamma\leq \frac{1}{2},\quad
-\eta\leq \frac{\gamma}{2N}
+\begin{thm}\label{infototale}
+On suppose que les gains sont bornés par $K\geq 0$, alors, pour tout $\eta$ tel
+que $\eta K\leq 1$ :
+\[
+R_n^* \leq\frac{\ln N}{\eta}
++\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2
 \]
 \end{thm}
 
-\subsection{Preuve}
-
-\paragraph{Étape 1}On commence comme dans le cas de l'information
-totale en minorant puis en majorant le log-rapport :
+\begin{proof}
+On minore puis on majore le log-rapport :
 \[
 \ln\left(\frac{W_T}{W_{0}}\right)
-=\ln\left(\sum_{i=1}^N\exp(\eta\widetilde{G}_{i,T})\right)-\ln N \\
-\geq \eta \max_{1\leq i\leq N}\widetilde{G}_{i,T}-\ln N
+=\ln\left(\sum_{i=1}^N\exp(\eta G_{i,T})\right)-\ln N \\
+\geq \eta \max_{1\leq i\leq N}G_{i,T}-\ln N
 \]
 
 Pour la majoration, on remarque que :
 \[
 \ln\left(\frac{W_t}{W_{t-1}}\right)
 =\ln\left(\sum_{i=1}^N
-\frac{w_{i,t-1}}{W_{t-1}}\exp(\eta\widetilde{g}_{i,t})\right)
+\frac{w_{i,t-1}}{W_{t-1}}\exp(g_{i,t})\right)
 =\ln\esp{\exp(\eta X)}
 \]
-où $X$ est une variable aléatoire qui vaut $\widetilde{g}_{i,t}$ avec
-probabilité $q_{i,t}=w_{i,t-1}/W_{t-1}$. On peut donc appliquer le lemme
+où $X$ est une variable aléatoire qui vaut $g_{i,t}$ avec
+probabilité $p_{i,t}$. On peut donc appliquer le lemme
 \ref{espexp}, on obtient :
 \[
 \ln\left(\frac{W_t}{W_{t-1}}\right)
-\leq\eta\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}
-+\eta^2\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2
+\leq\eta\sum_{i=1}^N p_{i,t}g_{i,t}
++\eta^2\sum_{i=1}^N p_{i,t}g_{i,t}^2
 \]
 
 On somme pour $t\in\{1,\ldots,N\}$ et on combine avec la minoration :
 \[
-\eta \max_{1\leq i\leq N}\widetilde{G}_{i,T}-\ln N 
-\leq \eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}
-+\eta^2 \sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2
+\eta \max_{1\leq i\leq N}G_{i,T}-\ln N 
+\leq \eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}
++\eta^2 \sum_{t=1}^T\sum_{i=1}^N p_{i,t}g_{i,t}^2
 .\]
 
-\paragraph{Étape 2} On remarque que $q_{i,t}\leq p_{i,t}/(1-\gamma)$ d'où
+Enfin on réordonne et on divise par $\eta$.
+\end{proof}
+
+\subsection{Bandits à $N$ bras}
+On utilise la stratégie de prédiction suivante :
+
+\begin{encadre}{\textwidth}
+\begin{center}
+\textbf{Algorithme Exp3.P}
+\end{center}
+
+\textbf{Initialisation :} On pose $w_{i,0}=1$ et $p_{i,1}=1/N$ pour
+$i\in\{1,\ldots,N\}$.
+
+À chaque tour $t\geq 1$ :
+
+\begin{enumerate}
+\item On tire $I_t\in\{1,\ldots,N\}$ suivant la loi
+$\mathbf{p_t}=(p_{1,t},\ldots,p_{N,t})$.
+\item On estime les gains
+$\mathbf{\widetilde{g}}=(\widetilde{g}_{1,t},\ldots,\widetilde{g}_{N,t})$ à
+partir du gain observé $g_{I_t,t}$
+\[
+\widetilde{g}_{i,t}=\frac{1}{p_{i,t}}\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}
++\beta\right)
+\]
+
+\item On met à jour les poids exponentiels :
+$w_{i,t}=w_{i,t-1}\exp(\eta\widetilde{g}_{i,t})$.
+\item On calcule la distribution pour le tour suivant :
+\[p_{i,t+1}=(1-\gamma)\frac{w_{i,t}}{W_t}+\frac{\gamma}{N}
+\quad\bigg(\mathrm{avec}\ W_t=\sum_{i=1}^{N}w_{i,t}\bigg)\]
+\end{enumerate}
+\end{encadre}
+
+\begin{thm}
+Avec  :
+\[\beta\leq 1,\quad
+\gamma\leq \frac{1}{2},\quad
+\eta\leq \frac{\gamma}{2N}
+\]
+\end{thm}
+
+\newpage
+
+\subsection{Preuve}
+On a une information totale sur les gains estimés, donc en notant
+$q_{i,t}=w_{i,t}/W_t$ et en appliquant le résultat du théorème \ref{infototale}
+: 
+\begin{equation}\label{fullinfo}
+R_T^*(\mathbf{q},\mathbf{\widetilde{g}})\leq\frac{\ln N}{\eta}
++\eta\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}^2
+\end{equation}
+
+puis en utilisant que $p_{i,t}\geq q_{i,t}(1-\gamma)$
 \[
-\eta \max_{1\leq i\leq N}\widetilde{G}_{i,T}-\ln N
-\leq\frac{\eta}{1-\gamma}\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
-+\frac{\eta^2}{1-\gamma}\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
+\begin{split}
+R_T^*(\mathbf{p},\mathbf{\widetilde{g}})
+&\leq\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+-(1-\gamma)\sum_{t=1}^T\sum_{i=1}^N q_{i,t}\widetilde{g}_{i,t}\\
+&=(1-\gamma)R_n^*(\mathbf{q},\mathbf{\widetilde{g}})
++\gamma\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+\end{split}
 \]
-puis en multipliant par $(1-\gamma)/\eta$ :
+et en utilisant \eqref{fullinfo} :
 \begin{equation}\label{base}
-(1-\gamma)\max_{1\leq i\leq N}\widetilde{G}_{i,T} -\frac{1-\gamma}{\eta}\ln N
-\leq \sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
-+\eta \sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
+R_T^*(\mathbf{p},\mathbf{\widetilde{g}})
+\leq \frac{\ln N}{\eta}
++\eta\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
++\gamma\max_{1\leq i\leq N}\widetilde{G}_{i,T}
 \end{equation}
 
 Vu le choix de l'estimateur de gain, on a :
 \[
-\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
-=\sum_{i=1}^N
-\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)=g_{I_t,t}+N\beta
+\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}
+=\sum_{t=1}^T\sum_{i=1}^N
+\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)=\sum_{t=1}^T g_{I_t,t}
++TN\beta
 \]
 et :
 \[
-\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2=\sum_{i=1}^N
-\widetilde{g}_{i,t}\left(g_{I_t,t}\mathbf{1}_{\{I_t=i\}}+\beta\right)
-\leq(1+\beta)\sum_{i=1}^N \widetilde{g}_{i,t}
+\sum_{t=1}^T\sum_{i=1}^N p_{i,t}\widetilde{g}_{i,t}^2
+\leq(1+\beta)\sum_{i=1}^N\widetilde{G}_{i,t}
+\leq(1+\beta)N\max_{1\leq i\leq N}\widetilde{G}_{i,t}
 \]
 
-D'où on déduit de \eqref{base} :
+D'où on déduit de \eqref{base}, en posant $C=\gamma+\eta(1+\beta)N$:
+\[
+R_T(\mathbf{p},\mathbf{g})
++\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+-\max_{1\leq i\leq N}G_{i,T}
+\leq \frac{\ln N}{\eta}
++TN\beta
++C\max_{1\leq i\leq N}\widetilde{G}_{i,t}
+\]
 \begin{equation}\label{etape2}
-\begin{split}
-(1-\gamma)\max_{1\leq i\leq N}\widetilde{G}_{i,T} -\frac{1-\gamma}{\eta}\ln N
-&\leq G_T + TN\beta +\eta(1+\beta)\sum_{i=1}^N\widetilde{G}_{i,T}\\
-&\leq G_T + TN\beta +\eta(1+\beta)N\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\end{split}
+R_T(\mathbf{p},\mathbf{g})
+\leq \frac{\ln N}{\eta}
++TN\beta
++\max_{1\leq i\leq N}G_{i,T}
++(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,t}
 \end{equation}
 
 % On souhaite maintenant relier les gains estimés aux gains
@@ -154,41 +276,103 @@ D'où on déduit de \eqref{base} :
 % ,\]
 % est une suite d'accroissements de martingale.
 
-\paragraph{Étape 3}On souhaite maintenant relier les gains estimés aux gains
+On souhaite maintenant relier les gains estimés aux gains
 réels. On choisit $\beta=\sqrt{\ln(N/\delta)/TN}$, alors avec probabilité
 supérieure à $1-\delta$ :
 \[
 \max_{1\leq i\leq N} G_{i,T}-\max_{1\leq i\leq N}\widetilde{G}_{i,T}
 \leq TN\beta = \sqrt{TN\ln\left(\frac{N}{\delta}\right)}
 \]
+d'où en remarquant que $0\leq 1-C\leq 1$ :
+\[
+(1-C)\max_{1\leq i\leq N} G_{i,T}
++(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+\leq TN\beta
+\]
+puis, vu que $\max_{1\leq i\leq N} G_{i,T}\leq T$ :
+\[
+\max_{1\leq i\leq N} G_{i,T}
++(C-1)\max_{1\leq i\leq N}\widetilde{G}_{i,T}
+\leq TN\beta+CT
+\]
+en injectant cette dernière majoration dans \eqref{etape2}, on obtient
+finalement :
+\[
+R_T(\mathbf{p},\mathbf{g})
+\leq \frac{\ln N}{\eta}
++2TN\beta+\big(\gamma+\eta(1+\beta)\big)T
+\]
+
+\section{Prédiction dans un univers convexe}
+Soit $F$ un convexe compact de $\set{R}^n$. À chaque tour on choisit un
+élément $x_t$ dans $F$ tandis que l'adversaire choisit une fonction de perte
+convexe $l_t : F\longrightarrow \set{R}^+$.
 
-\paragraph{Étape 4}On repart de \eqref{etape2} :
+On définit le regret par rapport à une stratégie fixe :
 \[
-\left[1-\gamma-\eta(1+\beta)N\right]\max_{1\leq i\leq N}\widetilde{G}_{i,T}
-\leq G_T+TN\beta+\frac{1-\gamma}{\eta}\ln N 
+R_T(\mathbf{x},\mathbf{l})=\sum_{t=1}^T l_t(x_t) - \min_{x\in F}\sum_{t=1}^T
+l_t(x)
 \]
-puis en utilisant l'étape 3, en remarquant que $0\leq
-1-\gamma-\eta(1+\beta)N\leq 1$ :
+
+On veut obtenir des bornes sur le regret valables pour toute stratégie de
+l'adversaire.
+
+\subsection{Réduction au cas des pertes linéaires}
+
+\begin{prop}
+Pour toute stratégie convexe $\mathbf{l}$ de l'adversaire, il existe une
+stratégie linéaire $\mathbf{l'}$ de l'adversaire telle que :
 \[
-\left[1-\gamma-\eta(1+\beta)N\right]\left(\max_{1\leq i\leq N}G_{i,T}-TN\beta
-\right)
-\leq G_T+TN\beta+\frac{1-\gamma}{\eta}\ln N 
+R_T(\mathbf{x},\mathbf{l})\leq R_T(\mathbf{x},\mathbf{l'})
 \]
+\end{prop}
+
+\begin{proof} (A PRECISER)
+Il suffit de considérer une suite de sous-gradients des fonctions $l_t$.
+\end{proof}
+
+On peut donc se restreindre à l'étude du regret pour des fonctions de perte
+linéaire. Dans ce cas on identifie la fonction de perte est représentée par un
+vecteur que l'on nomme également $l_t$. On a donc $l_t(x_t)=l_t\cdot x_t$.
+
+\subsection{Cas de l'information totale}
+
+On considère ici qu'à chaque tour on observe le vecteur $l_t$ (et pas seulement
+$l_t\cdot x_t$).
+On fixe une suite $(\eta_t)_{t\in\set{N}^*}$. On utilise alors la stratégie
+suivante :
 \[
-\left[1-\gamma-\eta(1+\beta)N\right]\max_{1\leq i\leq N}G_{i,T}
-\leq G_T+2TN\beta+\frac{1-\gamma}{\eta}\ln N 
+x_{t+1}=p_F(x_t-\eta_t l_t)
 \]
-On exprime maintenant cette inégalité en termes de pertes :
+où $p_F$ est la projection sur le convexe fermé $F$ comme rappelée en
+appendice.
+
+Dans le cas d'une fonction de perte linéaire, le vecteur $l_t$ s'identifie au
+gradient de la fonction de perte. La stratégie ci-dessus s'apparente donc à une
+descente de gradient gloutonne.
+
+\begin{thm}
+Si toutes les fonctions de pertes sont bornées par la même constante $K$ et que
+l'on note $D$ le diamètre du compact $F$, alors on a :
 \[
-\left[1-\gamma-\eta(1+\beta)N\right]\left(T-\min_{1\leq i\leq N}L_{i,T}\right)
-\leq T-L_T+2TN\beta+\frac{1-\gamma}{\eta}\ln N 
+R_T(\mathbf{x},\mathbf{l})
+\leq\frac{D^2}{2\eta_T}
++\frac{K^2}{2}\sum_{t=1}^T \eta_t
 \]
-d'où :
+
+En particulier, en prenant $\eta_t=\frac{1}{\sqrt{t}}$, on obtient :
 \[
-L_T - \min_{1\leq i\leq N}L_{i,T}
-\leq\left(\gamma+\eta(1+\beta)N\right)T +2TN\beta+\frac{1-\gamma}{\eta}\ln N 
+R_T(\mathbf{x},\mathbf{l})
+\leq\frac{D^2}{2}\sqrt{T}
++K^2\left(\sqrt{T}-\frac{1}{2}\right)
 \]
+\end{thm}
 
+\begin{proof} (A PRECISER) majoration du corollaire \ref{projection} +
+transformation d'Abel.
+\end{proof}
+
+ 
 \section{Appendice}
 
 \subsection{Quelques résultats d'analyse réelle}
@@ -451,4 +635,53 @@ N\leq\frac{\ln T}{\ln C}+1=\ln T\frac{(1+\ln C/\ln T)}{\ln C}
 \]
 \end{proof}
 
+\subsection{Projection sur un convexe fermé}
+
+On se place dans un espace euclidien $E$. Si $x$ et $y$ sont dans $E$, on note
+$x\cdot y$ le produit scalaire entre $x$ et $y$ et $\|x\|$ la norme euclidienne
+associée. 
+
+\begin{prop}
+Soient $F$ une partie convexe fermée non vide de $E$ et $y\in E$. Alors, il
+existe un unique $x\in F$ tel que :
+\[
+\|y-x\|=d(y,F)=\inf_{z\in F}\|y-z\|
+.\]
+
+De plus $x$ vérifie la propriété de l'angle obtus :
+\[
+\forall z\in F,\quad
+(y-x)\cdot(z-x)\leq 0
+\]
+
+On dit que $x$ est la projection de $y$ sur le convexe $F$, et on note
+$x=p_F(y)$.
+\end{prop}
+
+On en déduit notamment que pour tout $z\in F$, $\|y-p_F(y)\|\leq\|y-z\|$.
+L'inégalité de l'angle obtus permet d'obtenir une autre inégalité.
+
+\begin{cor}\label{projection}
+Soient $F$ une partie convexe fermée non vide de $E$ et $y\in E$. Alors :
+\[
+\forall z\in F,\quad
+\|z-p_F(y)\|\leq\|z-y\|
+\]
+\end{cor}
+
+\begin{proof}
+Soit $z\in F$, on part de l'inégalité de l'angle obtus :
+\[
+(y-p_F(y))\cdot(z-p_F(y))\leq 0
+\]
+d'où :
+\[
+(y-z+z-p_F(y))\cdot(z-p_F(y))
+=\|z-p_F(y)\|^2-(z-y)\cdot(z-p_F(y))\leq 0
+\]
+puis en appliquant l'inégalité de Cauchy-Schwarz :
+\[
+\|z-p_F(y)\|^2\leq\|z-y\|\|z-p_F(y)\|\qedhere
+\]
+\end{proof}
 \end{document}
-- 
cgit v1.2.3-70-g09d2

