From 5362d389988afb2750d27e7e6c5d401571dfba6e Mon Sep 17 00:00:00 2001
From: Jan Aalmoes <jan.aalmoes@inria.fr>
Date: Mon, 23 Sep 2024 20:54:42 +0200
Subject: Fini du background, ne manque plus que la relecture

---
 background/opti.tex | 57 ++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 43 insertions(+), 14 deletions(-)

(limited to 'background/opti.tex')

diff --git a/background/opti.tex b/background/opti.tex
index 03d01a6..0472d26 100644
--- a/background/opti.tex
+++ b/background/opti.tex
@@ -6,26 +6,32 @@ Cela permet l'entraînement de modèle d'apprantissage automatique à l'aide d'u
 Le second problème reprend le premier mais y ajoute des contraintes.
 C'est à dire, comme minimise-t'on le coût tout en garantissant certaines conditions ?
 
-\subsubsection{Optimisation sant contrainte : Descente de gradient}
+\subsubsection{Optimisation sans contrainte : Descente de gradient}
 \label{sec:background-opti-sgd}
 Nous appellons fonctionelles les fonctions $\mathbb{R}^n$ dans $\mathbb{R}$.
 Soit $J$ une fonctionelle convexe, nous cherchons à trouver $x\in\mathbb{R}$ tel que $J(x) = \text{inf}\{J(t)\mid t\in\mathbb{R}\}$.
 Pour simplifier cette rapide présentation, nous supposerons que $J$ à toujours les conditions de régularité (diférentiabilié) suffisante pour les opérations que nous appliquerons.
 Pour trouver $x$ qui minimise $J$ une des méthode les plus utilisé en apprentissage automatique est la descente de gradient.
-Il s'agit de construire une suite $(x_k)_{k\in\mathbb{N}}$ telle que $J(x_k)$ soit strictement décroissante ($\forall k\in\mathbb{N}~J(x_{k+1})<J(x_k)$).
+Il s'agit de construire une suite $(x_k)_{k\in\mathbb{N}}$ telle que à chauqe étape la direction de descente soit optimale.
+L'idée pour arriver à cela et de considérer une approximation de l'accroissement de $J$ en utiliant la définition du gradient.
 
-Pour cela, nous remarquons  
-\begin{align*}
-    J(x_k+h) = J(x_k)+\langle \nabla J(x_k),h\rangle + ||h||\varepsilon(h)\\
-    \iff J(x_k+h) - J(x_k) = \langle \nabla J(x_k),h\rangle + ||h||\varepsilon(h)
-\end{align*}
-Et donc un considérant la partie principale
+On cherche $h$  tel que $||h||=1$ et $J(x_k+h)$ soit minimal.
+D'après la définition du gradient
 \begin{equation*}
-    |J(x_k+h) - J(x_k)|\leq ||\nabla J(x_k)||||h||
+    J(x_k+h) = J(x_k) + \langle\nabla J(x_k),h\rangle + ||h||\epsilon(h)
 \end{equation*}
-D'éprès l'inégalitée de Cauchy-Schwartz. 
-L'égalité est obtenu si et seulment si il existe $l_k$ tel que
-$h=l_k\nabla J(x_k)$.
+On cherche alors à résoudre (*) : $min_{||h||=1}\langle\nabla J(x_k),h\rangle$.
+D'après l'inégalite de Cauchy-Schwartz 
+\begin{equation*}
+\forall h~||h||=1\implies~|\langle\nabla J(x_k),h\rangle |\leq ||\nabla J(x_k)||
+\end{equation*}
+Et aussi
+\begin{equation*}
+    \forall h~||h||=1\implies~\left(|\langle\nabla J(x_k),h\rangle | =||\nabla J(x_k)||
+    \iff h = \pm \frac{\nabla J(x_k)}{||\nabla J(x_k)||}\right)
+\end{equation*}
+$h=-\frac{\nabla J(x_k)}{||\nabla J(x_k)||}$ est donc solution de (*) pour que $\langle\nabla J(x_k),h\rangle$ soit négatif.
+
 Ainsi la méthode de déscente de gradient est définit par la suite
 $x_{k+1}=x_k-l_k\nabla J(x_k)$.
 $l_k$ est appelé le pas.
@@ -54,13 +60,36 @@ Avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum
 
 
 \subsubsection{Optimisation sous contraintes : multiplicateurs de Lagrange}
+\label{ref:background-opti-sous}
 Pour expliquer ce qu'est l'optimisation sous contraintes, represnons les mots de Philipe G. Ciarlet :
 \textquote{On s'interesse au problème suivant : trouver des conditions \emph{nécessaires}, et des conditions \emph{suffisantes}, pour qu'un point d'un ensemble $U$ soit un extremum relatif de la restriction à l'ensemble $U$ d'une fonction $J$ définie sur un ensemble "plus grands". [...]
 Un premier exemple est celui des \emph{extremums relatifs liés}, où l'ensemble $U$ est de la forme 
 \begin{equation*}
-    U=\{v\in Q \mid \forall i\in m-1~\psi_i(v)=0\}
+    U=\{v\in V \mid \forall i\in m-1~\varphi_i(v)\leq 0\}
 \end{equation*}
 }
-Pour une présentation plus complète des multiplicateurs de Lagrange voir la Section 7.2 de~\cite{ciarlet}
+
+On introduit le Lagrangien de ce problèmes par la formule suivante:
+\begin{equation*}
+    L:\left\{
+        \begin{matrix}
+            V\times\mathbb{R}^m_+\\
+            (v,\mu)\mapsto J(v)+\sum_{i=0}^{m-1}\mu_i\varphi(v)
+        \end{matrix}
+        \right.
+\end{equation*}
+
+Pour respecter les contrainte du problèmes, la méthode consiste à chercher un point selle de $L$,
+c'est-à-dire, un point $(u,\lambda)\in V\times \mathbb{R}^m_+$ tel que 
+\begin{equation*}
+    sup L(\square,\lambda)=L(u,\lambda)\wedge inf L(u,\square)=L(u,\lambda)
+\end{equation*}
+
+$u$ est alors solution du problème.
+Il est donc suffisant de connaitre $\lambda$ appelé \emph{multiplicateurs de Lagrange} pour pouvoir trouver $u$ en se ramensant au cas sans contraintes de la section précédente.
+Trouver $\lambda$ s'apelle le \emph{problème dual} en contrepartie de la recheche de $u$ qui est le \emph{problème primal}.
+Le problème dual bénéficie du fait que ces contraintes sont plus simples car il sagi uniquement de la positivité des multiplicateur de Lagrange.
+Le problème dual s'écrit donc $sup (inf_{v\in V}L(v,\square))$.
+Pour une présentation plus complète des multiplicateurs de Lagrange et de la dualité voir les Sections 7.2 et 9.3 du Livre de Ciarlet~\cite{ciarlet}
 
 
-- 
cgit v1.2.3