Finish the slides.
authorJérôme Benoit <jerome.benoit@piment-noir.org>
Fri, 9 Nov 2018 11:19:33 +0000 (12:19 +0100)
committerJérôme Benoit <jerome.benoit@piment-noir.org>
Fri, 9 Nov 2018 11:19:33 +0000 (12:19 +0100)
Signed-off-by: Jérôme Benoit <jerome.benoit@piment-noir.org>
présentation/Slides_ProjetOptimRO.tex
rapport/ProjetOptimRO.tex

index 4f9d807de186352458dce0e8b575c4cf706883ff..eade499f142b328ca34df222514b268e7a9192d9 100644 (file)
@@ -3,7 +3,6 @@
 
 \usefonttheme{professionalfonts}
 
-
 % Setup appearance:
 %\usetheme{Warsaw}
 \usetheme{Darmstadt}
@@ -86,7 +85,6 @@ $}}
 
 \definecolor{mycvblue}{rgb}{0.302,0.537,0.737}
 
-
 \setbeamercolor{structure}{fg=mycvblue}
 \setbeamercolor{palette primary}{fg=mycvblue}
 \setbeamercolor{subsection in head/foot}{parent=palette primary}
@@ -102,8 +100,6 @@ $}}
 
 %\renewcommand{\item}{\item[$\bullet$]}
 
-
-
 \title[]{\LARGE{\textsc{Méthode de Programmation Quadratique Séquentielle ou PQS\\ en\\ Optimisation non linéraire sous contraintes}}}
 
 \author[Jérôme {\textsc Benoit} \& Sylvain {\textsc Papa}]{\textbf{Jérôme {\textsc Benoit}\\ \textbf{Sylvain {\textsc Papa}}}}
@@ -140,8 +136,6 @@ $}}
 \newcommand{\chch}{{C}hudnovsky-{C}hudnovsky}
 \newcommand{\ch}{{C}hudnovsky}
 
-
-
 \addtobeamertemplate{footline}{\texttt{\hfill\insertframenumber/{\inserttotalframenumber}}}
 
 % \AtBeginSubsection[] {
@@ -196,9 +190,133 @@ $}}
 
 \section{Introduction}
 
-\subsection{Principe général}
+\subsection{Définition de la problèmatique}
 
 %%%%% SLIDE 1
+\begin{frame}{Définition de la problèmatique}
+ \begin{defin}
+  Résoudre le problème $ \mathcal{P} $ :
+  $$
+   \mathcal{P} \left \{
+   \begin{array}{l}
+    \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
+    g(x) \leq 0                                 \\
+    h(x) = 0
+   \end{array}
+   \right .
+  $$
+  où $$ g: \mathbb{R}^n \longrightarrow \mathbb{R}^p,\ h: \mathbb{R}^n \longrightarrow \mathbb{R}^q\ et\ J: \mathbb{R}^n \longrightarrow \mathbb{R} $$
+ \end{defin}
+ \centerline{à l'aide de méthodes numériques itératives.}
+\end{frame}
+
+\section{Méthode de descente}
+
+\subsection{Définition}
+
+%%%%% SLIDE 2
+\begin{frame}{Définition d'une méthode de descente}
+ \begin{defin}
+  Générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ avec :
+  \centerline{$ x_0 \in \mathbb{R}^n $ arbitraire,}
+  \centerline{$ x_{k+1} = x_k + s_kd_k $ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $}
+  et
+  $$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
+ \end{defin}
+\end{frame}
+
+\subsection{Algorithme}
+
+%%%%% SLIDE 3
+\begin{frame}{Algorithme de descente modèle}
+ \begin{block}{ALGORITHME DE DESCENTE MODÈLE.}
+  \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
+  \newline
+  \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
+  \begin{enumerate}
+   \item $ k := 0 $.
+   \item Tant que "test d’arrêt" non satisfait,
+         \begin{enumerate}
+          \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
+          \item \textit{Recherche linéaire} : Choisir un pas $ s_k > 0 $ à faire dans cette direction et tel que : $$ J(x_k + s_kd_k) < J(x_k). $$
+          \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
+         \end{enumerate}
+   \item Retourner $ x_k $.
+  \end{enumerate}
+ \end{block}
+\end{frame}
+
+\subsubsection{Direction de descente}
+
+%%%%% SLIDE 4
+\begin{frame}{Direction de descente}
+ Deux grandes stratégies :
+ \begin{itemize}
+  \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}.
+  \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}.
+ \end{itemize}
+\end{frame}
+
+\subsubsection{Critère d'arrêt}
+
+%%%%% SLIDE 5
+\begin{frame}{Critère d'arrêt}
+ \centerline{Critère d’arrêt =}
+ \begin{tabular}{c}
+  Test d’optimalité satisfait($\norme{\nabla J(x_k)} < \varepsilon$)                             \\
+  OU (Stagnation de la valeur courante($ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $) \\
+  ET Stagnation de la solution($ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $))          \\
+  OU Nombre d’itérations maximum autorisé dépassé($ k < IterMax $)
+ \end{tabular}
+\end{frame}
+
+\subsubsection{Recherche linéaire}
+
+%%%%% SLIDE 6
+\begin{frame}{Recherche linéaire}
+ \begin{block}{RECHERCHE LINÉAIRE : PAS FIXE.}
+  $ s_k = s_{k-1} $
+ \end{block}
+ \begin{block}{RECHERCHE LINÉAIRE : PAS OPTIMAL.}
+  $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
+ \end{block}
+\end{frame}
+
+\subsubsection{Méthode Newtonienne}
+
+%%%%% SLIDE 7
+\begin{frame}{Méthode Newtonienne I}
+ Choix de la direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ solution unique du problème :
+
+ $$ \underset{d \in \mathbb{R}^n}{\mathrm{argmin}} \ J(x_k) + \langle \nabla J(x_k),d \rangle + \frac{1}{2}\langle H[J](x_k)d,d \rangle $$
+
+ $ \iff d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
+\end{frame}
+
+%%%%% SLIDE 8
+\begin{frame}{Méthode Newtonienne II}
+ \begin{tabular}{|p{15em}|p{15em}|}
+  \hline
+  Avantages                                                                                           & Inconvénients                                                                                                                                                     \\
+  \hline
+  sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). &                                                                                                                                                                   \\
+  \hline
+                                                                                                      & les difficultés et le coût de calcul de la hessienne $ H[J](x_k) $ : l’expression analytique des dérivées secondes est rarement disponible dans les applications. \\
+  \hline
+                                                                                                      & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $.                                                                          \\
+  \hline
+                                                                                                      & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la    hessienne est singulière.                                                  \\
+  \hline
+                                                                                                      & pas de distinction entre minima, maxima et points stationnaires.                                                                                                  \\
+  \hline
+ \end{tabular}
+\end{frame}
+
+\section{Méthode PQS}
+
+\subsection{Principe général}
+
+%%%%% SLIDE 9
 \begin{frame}{Principe général I}
  \begin{defin}
   Résoudre le problème $ \mathcal{P} $ :
@@ -215,7 +333,7 @@ $}}
  \end{defin}
 \end{frame}
 
-%%%%% SLIDE 1
+%%%%% SLIDE 10
 \begin{frame}{Principe général II}
  \begin{enumerate}
   \item Conditions nécessaires et suffisantes d'existence et d'unicité d'une solution (\textit{KKT}, $ H[J] $ définie positive et convexité de $ \mathcal{P} $).
@@ -225,12 +343,13 @@ $}}
   \item Approximation linéaire de $ g $ et $ h $ par Taylor-Young à l'ordre 1 en $ x_k $ :
         $$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
         $$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
+  \item Condition d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
+        $$ \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$
  \end{enumerate}
 \end{frame}
 
-%%%%% SLIDE 3
+%%%%% SLIDE 11
 \begin{frame}{Principe général III}
- Conditions d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
  \begin{block}{}
   Résoudre le sous-problème quadratique $ \mathcal{PQ}_k $ avec contraintes linéaires :
   $$
@@ -244,11 +363,12 @@ $}}
   $$
   où $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $ symétrique (Schwarz).
  \end{block}
+ \centerline{$ \implies $ La solution $  d_k $ est la valeur optimale de direction de descente.}
 \end{frame}
 
-\section{Algorithme PQS}
+\subsection{Algorithme PQS}
 
-%%%%% SLIDE 4
+%%%%% SLIDE 12
 \begin{frame}{Algorithme PQS}
  \begin{block}{ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.}
   \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $, $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$, $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ différentiables, $ x_0 \in \mathbb{R}^n $ point initial arbitraire, $ \lambda_0 \in \mathbb{R}_+^p $ et $ \mu_0 \in \mathbb{R}_+^q $ multiplicateurs initiaux, $ \varepsilon > 0 $ précision demandée.
@@ -276,120 +396,6 @@ $}}
  \end{block}
 \end{frame}
 
-% %%%%% SLIDE 6
-% \begin{frame}
-%
-% \end{frame}
-%
-% \section{Algorithme de D.V. et G.V. Chudnovsky (1987)}
-%
-% \subsection{Avec des places rationnelles}
-%
-% %%%%% SLIDE 9
-% \begin{frame}{Algorithme original de Chudnovsky et Chudnovsky}
-%
-% \end{frame}
-%
-% \subsection{Principe}
-%
-% %%%%% SLIDE 8
-% \begin{frame}{Principe pour multiplier avec l'algorithme de Chudnovsky}
-%
-% \end{frame}
-%
-% \subsection{Avec des places de degré un et deux}
-%
-% %%%%% SLIDE 10
-% \begin{frame}{Evaluations sur des places de degré 1 et 2}
-%
-% \end{frame}
-%
-% \section{Conditions permettant l'utilisation de l'algorithme}
-%
-% \subsection{Conditions principales}
-%
-% %%%%% SLIDE 11
-% \begin{frame}{Conditions suffisantes pour appliquer l'algorithme}
-%
-% \end{frame}
-%
-% \subsection{Applications}
-%
-% %%%%% SLIDE 11
-% \begin{frame}{Le cas des extensions de petits degré}
-%
-% \end{frame}
-%
-% \begin{frame}{Algorithme de Chudnovsky sur un corps de fonctions hyperelliptique de genre 2}
-%
-% \end{frame}
-%
-%
-% \begin{frame}{Exemple pour les \textit{petites} extensions $\F_{16^n}$ de $\F_{16}$}
-%
-% \end{frame}
-%
-% \setbeamercovered{transparent}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% %%%%%%%%%%%%% T  %%%%%%%%%%%%%%%
-%
-%
-% %%%%%%%%%%%%% T  %%%%%%%%%%%%%%%
-%
-%
-% %%%%%%%%%%%%% T  %%%%%%%%%%%%%%%
-%
-% \section{Nouveau résultats}
-%
-% \subsection{Bornes uniformes connues}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% \subsection{Nouvelles bornes uniformes}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% %%%%% SLIDE 14
-% \begin{frame}{Corps de fonctions sur $\F_{p^2}$}
-%
-% \end{frame}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% %%%%%%%%%%%%% T  %%%%%%%%%%%%%%%
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% \section{Conclusions et perspectives}
-%
-% \subsection{Problèmes et/ou travail en cours}
-%
-% %%%%% SLIDE 15
-%
-% \begin{frame}{Conclusion}
-%
-% \end{frame}
-%
-% \begin{frame}
-%
-% \end{frame}
-
 %%%%% SLIDE DE FIN
 
 \begin{frame}[plain]
index e66ed414bfb00df88cb30fd0168800a8dfaa0fa9..372670f6167b036fa74ce7f8913ff20c2a746fdd 100644 (file)
@@ -514,7 +514,7 @@ En supposant $ J $ de classe $ \mathcal{C}^2 $ et la matrice hessienne $ H[J](x_
 $$ x_{k+1} = x_k - H[J](x_k)^{-1} \nabla J(x_k), $$
 où $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ est appelée direction de Newton. La direction $ d_k $ est également l’unique solution du problème :
 $$ \underset{d \in \mathbb{R}^n}{\mathrm{argmin}} \ J(x_k) + \langle \nabla J(x_k),d \rangle + \frac{1}{2}\langle H[J](x_k)d,d \rangle $$
-Autrement dit, $ d_k $ est le point de minimum global de l’approximation de second ordre de $ J $ au voisinage du point courant $ x_k $.
+Autrement dit, $ d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
 À condition que la matrice $ H[J](x_k) $ soit définie positive à chaque itération, la méthode de Newton est bien une méthode de descente à pas fixe égal à $ 1 $.
 \newline
 Les propriétés remarquables de cet algorithme sont :