From c207a96fe97af0c4d38688ce110768bc3513026d Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Fri, 9 Nov 2018 12:19:33 +0100 Subject: [PATCH] Finish the slides. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- .../Slides_ProjetOptimRO.tex" | 258 +++++++++--------- rapport/ProjetOptimRO.tex | 2 +- 2 files changed, 133 insertions(+), 127 deletions(-) diff --git "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" index 4f9d807..eade499 100644 --- "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" +++ "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" @@ -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] diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index e66ed41..372670f 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -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 : -- 2.34.1