From 4aae3ea0427a6c9e9a8519a38d9d9d0ac5f0ec9c Mon Sep 17 00:00:00 2001
From: Jan Aalmoes <jan.aalmoes@inria.fr>
Date: Sat, 21 Sep 2024 16:27:27 +0200
Subject: fin intro

---
 background/opti.tex | 59 ++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 38 insertions(+), 21 deletions(-)

(limited to 'background/opti.tex')

diff --git a/background/opti.tex b/background/opti.tex
index 9d346d6..03d01a6 100644
--- a/background/opti.tex
+++ b/background/opti.tex
@@ -1,4 +1,4 @@
-L'optimisation est une branche est des mathématiques appliquées qui cherche à trouver les points pour lequels une fonctions réalise un certain nombre d'exigence. 
+L'optimisation est une branche des mathématiques appliquées qui cherche à trouver les points pour lequels une fonctions réalise un certain nombre d'exigences. 
 Le lecteur pourra se reférer par exemple au libre de Phillipe G. Ciarlet \textit{Introduction à l'analyse numérique matricielle et à l'optimisation}~\cite{ciarlet} pour une présentation très complète d'un grand nombre de techniques.
 Dans ce manuscrit nous ne nous interesseront qu'a deux type de problèmes liées à l'apprantissange automatique et surtout au réseaux de neuronnes.
 Le premier de ces problèmes est la minimisation sans contrainte d'une fonctionelle convexe.
@@ -6,11 +6,34 @@ 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{Descente de gradient}
+\subsubsection{Optimisation sant 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)$).
 
+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
+\begin{equation*}
+    |J(x_k+h) - J(x_k)|\leq ||\nabla J(x_k)||||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)$.
+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.
+En théorie nous pouvons lire dans le libre de Ciarlet qu'il existe de multiple manière de trouver un pas optimale ou approprié à la fonctionelle $J$.
+Cependant, en apprantissage automatique le hypothèse necessaire pour obtenir l'optimalité sont souvent absentes, en pratique le pas est souvant choisit constant $\exists c\forall k~l_k=c$.
+
+Nous montrons dans la Figure~\ref{fig:background-opti-gd} le fonctionement de la méthode de gradient à pas fixe en dimension un pour une fonctionelle convexe.
+Avec une illustration de la convergence de l'écart entre $J(x_k)$ et le minimum.
 \begin{figure}
     \centering
     \begin{subfigure}{0.45\linewidth}
@@ -23,27 +46,21 @@ Soit $J$ une fonctionelle convexe, nous cherchons à trouver $x\in\mathbb{R}$ te
         \centering
         \includegraphics[width=0.66\linewidth]{background/figure/opti/conv.pdf}
         \caption{Convergence des l'écart entre $u$ et le minimum vers $0$ en fonction des itérations.}
-        \label{fig:background-opti-gd}
     \end{subfigure}
+    \caption{Convergence de la méthode de gradient.}
+    \label{fig:background-opti-gd}
 \end{figure}
 
 
-\begin{figure}
-    \begin{subfigure}{0.3\linewidth}
-    \includegraphics[width=\linewidth]{background/figure/ml/convex/f_local3.1.pdf}
-    \caption{L'algorithme tombe dans un minimum locale ($u_0=3,1$).}
-    \end{subfigure}
-    \begin{subfigure}{0.3\linewidth}
-    \includegraphics[width=\linewidth]{background/figure/ml/convex/f_local8.28.pdf}
-    \caption{L'algorithme tombe dans un minimum globale ($u_0=8,28$).}
-    \end{subfigure}
-    \begin{subfigure}{0.3\linewidth}
-    \includegraphics[width=\linewidth]{background/figure/ml/convex/conv_local.pdf}
-    \caption{Convergence vers un minimum locale et globale.}
-    \end{subfigure}
-    \caption{Impacte de la convexité sur la convergence.}
-    \label{fig:background-opti-cvx}
-\end{figure}
-\subsubsection{Multiplicateurs de Lagrange}
 
-\paragraph{Descente de gradient exponentiée}
+\subsubsection{Optimisation sous contraintes : multiplicateurs de Lagrange}
+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\}
+\end{equation*}
+}
+Pour une présentation plus complète des multiplicateurs de Lagrange voir la Section 7.2 de~\cite{ciarlet}
+
+
-- 
cgit v1.2.3