présentation/Slides_ProjetOptimRO.tex

   1 \documentclass[9pt,blackandwhite,roman,handout]{beamer}
   2 \usepackage{etex}
   3
   4 \usefonttheme{professionalfonts}
   5
   6 % Setup appearance:
   7 %\usetheme{Warsaw}
   8 \usetheme{Darmstadt}
   9
  10 %\usecolortheme{seahorse}
  11 %\usecolortheme{dove}
  12 \usecolortheme{seagull}
  13 %\usefonttheme[onlylarge]{structurebold}
  14 %\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
  15 %\setbeamertemplate{navigation symbols}{}
  16
  17
  18
  19 % Standard packages
  20 %\usepackage[frenchb]{babel}
  21 %\usepackage[english]{babel}
  22 \usepackage[utf8]{inputenc}
  23 %\usepackage[T1]{fontenc}
  24 \usepackage{cmbright}
  25 \usepackage[sans]{dsfont}
  26 \usepackage{pifont}
  27 %calscaled=.94,
  28 %frakscaled=.97,
  29 \usepackage[cal=euler,scr=rsfso]{mathalfa}%bb=cm,
  30 %frak=mma,
  31 %scr=esstix
  32 \usepackage{mathrsfs} % pour faire des majuscules calligraphiées \mathcal{blabla}
  33 %\usepackage[french,lined]{algorithm2e} % rajouter linesnumbered dans les arguments pour numéroter les lignes des algos, boxed pour l'encadrement
  34 %\usepackage{extsizes}
  35 %\usepackage{MnSymbol}
  36 \usepackage{graphicx}
  37 \usepackage{mathabx}
  38 \usepackage[all]{xy}
  39 \usepackage{ulem}
  40
  41 \usepackage{DotArrow}
  42 %\usepackage[varg]{txfonts}
  43 %\usepackage{matptmx}
  44 \usepackage{extpfeil}
  45 %\usepackage{MyMnSymbol}
  46 \usepackage{comment}
  47 %\usepackage{etex}
  48 %\usepackage{mathtools}
  49 %\usepackage{fourier}
  50
  51 \usepackage{ragged2e}
  52
  53 % Setup TikZ
  54 \usepackage{tikz}
  55 \usetikzlibrary{matrix,arrows}
  56 \tikzstyle{block}=[draw opacity=0.7,line width=1.4cm]
  57
  58 \newcommand{\gk}{$g_k = \left \{ \begin{array}{ll}
  59                 q^k+q^{k-1}-q^\frac{k+1}{2} - 2q^\frac{k-1}{2}+1 & \mbox{si } k \equiv 1 \pmod 2,\\
  60                 q^k+q^{k-1}-\frac{1}{2}q^{\frac{k}{2}+1} - \frac{3}{2}q^{\frac{k}{2}}-q^{\frac{k}{2}-1} +1& \mbox{si } k \equiv 0 \pmod 2.
  61                 \end{array} \right .$}
  62
  63 \newcommand{\ext}{\xymatrix{
  64     \FF= \Fq(x)(y) \ar@{-}[d]^{<\infty} \\ \Fq(x) \ar@{-}[d] \\ \Fq} }
  65
  66 \newcommand{\twoheaddownarrow}{%
  67 \mathrel{\reflectbox{\rotatebox[origin=c]{-90}{$\xtwoheadrightarrow[ \; ]{   \reflectbox{\rotatebox[origin=c]{-90}{$\pi_Q \ $}} \ \  }$}}}}
  68
  69 \newcommand{\longdownmapsto}{%
  70 \mathrel{\reflectbox{\rotatebox[origin=c]{-90}{$\xmapsto{ \ \ \ \reflectbox{\rotatebox[origin=c]{-90}{$\pi_Q \ $}} \ \ \ }$}}}}
  71
  72 \newcommand{\bigubrace}[1]{\underbrace{\mbox{}f(P_i), f'(P_i), \ldots, f^{(\ell_i-1)}(P_i)\vphantom{\sum_0^0}\hspace{#1}\mbox{}}_?}
  73
  74 \newcommand{\myubrace}[2]{\rotatebox[origin=c]{90}{$
  75 \rotatebox[origin=c]{-90}{#1} \left \{
  76 \begin{array}{l}
  77          \vspace{#2} \\
  78 \end{array}
  79 \right . \hspace{-1em}
  80 $}}
  81
  82 \newcommand{\bluebrace}{{\color{blue}\left\{}}
  83
  84 \newcommand{\norme}[1]{\left\Vert #1 \right\Vert}
  85
  86 \definecolor{mycvblue}{rgb}{0.302,0.537,0.737}
  87
  88 \setbeamercolor{structure}{fg=mycvblue}
  89 \setbeamercolor{palette primary}{fg=mycvblue}
  90 \setbeamercolor{subsection in head/foot}{parent=palette primary}
  91
  92 \setbeamertemplate{navigation symbols}{
  93 %      \insertslidenavigationsymbol
  94 %      \insertframenavigationsymbol
  95 %      \insertsubsectionnavigationsymbol
  96 %      \insertsectionnavigationsymbol
  97 %      \insertdocnavigationsymbol
  98 %      \insertbackfindforwardnavigationsymbol
  99 }
 100
 101 %\renewcommand{\item}{\item[$\bullet$]}
 102
 103 \title[]{\LARGE{\textsc{Méthode de Programmation Quadratique Séquentielle ou PQS\\ en\\ Optimisation non linéraire sous contraintes}}}
 104
 105 \author[Jérôme {\textsc Benoit} \& Sylvain {\textsc Papa}]{\textbf{Jérôme {\textsc Benoit}\\ \textbf{Sylvain {\textsc Papa}}}}
 106
 107 \date[]{{\bf HUGo}\\ {\bf Polytech'Marseille} \\{\small Novembre 2018}}
 108
 109 \newtheorem{defin}{Définition}
 110 \newtheorem{theoreme}{Théorème}
 111 \newtheorem{lemme}{Lemme}
 112 \newtheorem{corollaire}{Corollaire}
 113 \newtheorem{proposition}{Proposition}
 114 \newtheorem{propriete}{Propriété}
 115 %\newtheorem{exemple}[definition]{Exemple}
 116
 117 \newcommand{\NN}{\ensuremath{\mathbb{N}}}
 118 \newcommand{\CC}{\ensuremath{\mathbb{C}}}
 119 \newcommand{\ZZ}{\ensuremath{\mathbb{Z}}}
 120 \newcommand{\PF}{\mathbf{P}_F}
 121 \newcommand{\DF}{\mathsf{Div}(F)}
 122 \newcommand{\Jac}{\ensuremath{\mathcal{J}\mathsf{ac}(F/\Fq)}}
 123 \newcommand{\Fqr}[2][q]{\mathds{F}_{\!{#1}^{#2}}}
 124 \newcommand{\Fq}{\Fqr{}}
 125 \newcommand{\F}{\mathds{F}}
 126 \newcommand{\FF}{\mathsf{F}}
 127 \newcommand{\Fqn}{\Fqr{n}}
 128 \newcommand{\D}[1][D]{\ensuremath{\mathcal{#1}}}
 129 \newcommand{\Ld}[1][\D]{\ensuremath{\mathscr{L}\!\!\left(#1\right)}} % utilisation :  \Ld ou \Ld[A] pour un diviseur A au lieu de D
 130 \newcommand{\Ak}[1][k]{\ensuremath{\mathbb{A}_{#1}}}
 131 \newcommand{\A}{\ensuremath{\mathsf{A}}}
 132 \newcommand{\Cl}{\ensuremath{\mathsf{Cl}}}
 133 \newcommand{\mus}{\ensuremath{\mu^\mathsf{sym}}}
 134 \newcommand{\Ms}{\ensuremath{M^\mathsf{sym}}}
 135 \newcommand{\ms}{\ensuremath{m^\mathsf{sym}}}
 136 \newcommand{\chch}{{C}hudnovsky-{C}hudnovsky}
 137 \newcommand{\ch}{{C}hudnovsky}
 138
 139 \addtobeamertemplate{footline}{\texttt{\hfill\insertframenumber/{\inserttotalframenumber}}}
 140
 141 % \AtBeginSubsection[] {
 142 % \begin{frame}<beamer>
 143 % \frametitle{Plan}
 144 % \tableofcontents[currentsection,currentsubsection]
 145 % \end{frame}
 146 % }
 147 % \AtBeginSection[] {
 148 % \begin{frame}<beamer>
 149 % \frametitle{Plan}
 150 % \tableofcontents[currentsection]%,currentsubsection]
 151 % \end{frame}
 152 % }
 153
 154 \setbeamertemplate{sections/subsections in toc}[sections numbered]
 155 %\setbeamertemplate{sections in toc}[sections numbered]
 156
 157 \begin{document}
 158
 159 % \begin{frame}[plain]
 160 %
 161 %  \begin{center}
 162 %
 163 %   {\bf Institut de Mathématiques de Marseille}\\
 164 %
 165 %   {\bf Equipe Analyse, Géométrie et Topologie (AGT) }\\
 166 %
 167 %   \vspace{2em}
 168 %
 169 %   {\bf Séminaire de Géométrie Complexe}\\
 170 %   Mardi 12 Juin 2018
 171 %  \end{center}
 172 %
 173 %  \begin{center}
 174 %
 175 %  \end{center}
 176 %
 177 % \end{frame}
 178
 179 \begin{frame}[plain]
 180
 181  \titlepage
 182
 183 \end{frame}
 184
 185 \begin{frame}[plain]{Plan}
 186
 187  \tableofcontents
 188
 189 \end{frame}
 190
 191 \section{Introduction}
 192
 193 \subsection{Définition de la problèmatique}
 194
 195 %%%%% SLIDE 1
 196 \begin{frame}{Définition de la problèmatique}
 197  \begin{defin}
 198   Résoudre le problème $ \mathcal{P} $ :
 199   $$
 200    \mathcal{P} \left \{
 201    \begin{array}{l}
 202     \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
 203     g(x) \leq 0                                 \\
 204     h(x) = 0
 205    \end{array}
 206    \right .
 207   $$
 208   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} $$
 209  \end{defin}
 210  \centerline{à l'aide de méthodes numériques itératives.}
 211 \end{frame}
 212
 213 \section{Méthode de descente}
 214
 215 \subsection{Définition}
 216
 217 %%%%% SLIDE 2
 218 \begin{frame}{Définition d'une méthode de descente}
 219  \begin{defin}
 220   Générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ avec :
 221   \centerline{$ x_0 \in \mathbb{R}^n $ arbitraire,}
 222   \centerline{$ x_{k+1} = x_k + s_kd_k $ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $}
 223   et
 224   $$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
 225  \end{defin}
 226 \end{frame}
 227
 228 \subsection{Algorithme}
 229
 230 %%%%% SLIDE 3
 231 \begin{frame}{Algorithme de descente modèle}
 232  \begin{block}{ALGORITHME DE DESCENTE MODÈLE.}
 233   \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
 234   \newline
 235   \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
 236   \begin{enumerate}
 237    \item $ k := 0 $.
 238    \item Tant que "test d’arrêt" non satisfait,
 239          \begin{enumerate}
 240           \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
 241           \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). $$
 242           \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
 243          \end{enumerate}
 244    \item Retourner $ x_k $.
 245   \end{enumerate}
 246  \end{block}
 247 \end{frame}
 248
 249 \subsubsection{Direction de descente}
 250
 251 %%%%% SLIDE 4
 252 \begin{frame}{Direction de descente}
 253  Deux grandes stratégies :
 254  \begin{itemize}
 255   \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}.
 256   \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}.
 257  \end{itemize}
 258 \end{frame}
 259
 260 \subsubsection{Critère d'arrêt}
 261
 262 %%%%% SLIDE 5
 263 \begin{frame}{Critère d'arrêt}
 264  \centerline{Critère d’arrêt =}
 265  \begin{tabular}{c}
 266   Test d’optimalité satisfait($\norme{\nabla J(x_k)} < \varepsilon$)                             \\
 267   OU (Stagnation de la valeur courante($ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $) \\
 268   ET Stagnation de la solution($ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $))          \\
 269   OU Nombre d’itérations maximum autorisé dépassé($ k < IterMax $)
 270  \end{tabular}
 271 \end{frame}
 272
 273 \subsubsection{Recherche linéaire}
 274
 275 %%%%% SLIDE 6
 276 \begin{frame}{Recherche linéaire}
 277  \begin{block}{RECHERCHE LINÉAIRE : PAS FIXE.}
 278   $ s_k = s_{k-1} $
 279  \end{block}
 280  \begin{block}{RECHERCHE LINÉAIRE : PAS OPTIMAL.}
 281   $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
 282  \end{block}
 283 \end{frame}
 284
 285 \subsubsection{Méthode Newtonienne}
 286
 287 %%%%% SLIDE 7
 288 \begin{frame}{Méthode Newtonienne I}
 289  Choix de la direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ solution unique du problème :
 290
 291  $$ \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 $$
 292
 293  $ \iff d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
 294 \end{frame}
 295
 296 %%%%% SLIDE 8
 297 \begin{frame}{Méthode Newtonienne II}
 298  \begin{tabular}{|p{15em}|p{15em}|}
 299   \hline
 300   Avantages                                                                                           & Inconvénients                                                                                                                                                     \\
 301   \hline
 302   sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). &                                                                                                                                                                   \\
 303   \hline
 304                                                                                                       & 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. \\
 305   \hline
 306                                                                                                       & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $.                                                                          \\
 307   \hline
 308                                                                                                       & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la    hessienne est singulière.                                                  \\
 309   \hline
 310                                                                                                       & pas de distinction entre minima, maxima et points stationnaires.                                                                                                  \\
 311   \hline
 312  \end{tabular}
 313 \end{frame}
 314
 315 \section{Méthode PQS}
 316
 317 \subsection{Principe général}
 318
 319 %%%%% SLIDE 9
 320 \begin{frame}{Principe général I}
 321  \begin{defin}
 322   Résoudre le problème $ \mathcal{P} $ :
 323   $$
 324    \mathcal{P} \left \{
 325    \begin{array}{l}
 326     \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
 327     g(x) \leq 0                                 \\
 328     h(x) = 0
 329    \end{array}
 330    \right .
 331   $$
 332   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}\ de\ classe\ \mathcal{C}^2. $$
 333  \end{defin}
 334 \end{frame}
 335
 336 %%%%% SLIDE 10
 337 \begin{frame}{Principe général II}
 338  \begin{enumerate}
 339   \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} $).
 340   \item Approximation quadratique du Lagrangien $ L $ de $ \mathcal{P} $ par Taylor-Young à l'ordre 2 en $ x_k $:
 341         $$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) $$
 342         $$ + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$
 343   \item Approximation linéaire de $ g $ et $ h $ par Taylor-Young à l'ordre 1 en $ x_k $ :
 344         $$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
 345         $$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
 346   \item Condition d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
 347         $$ \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) $$
 348  \end{enumerate}
 349 \end{frame}
 350
 351 %%%%% SLIDE 11
 352 \begin{frame}{Principe général III}
 353  \begin{block}{}
 354   Résoudre le sous-problème quadratique $ \mathcal{PQ}_k $ avec contraintes linéaires :
 355   $$
 356    \mathcal{PQ}_k \left \{
 357    \begin{array}{l}
 358     \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 359     g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\}              \\
 360     h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 361    \end{array}
 362    \right .
 363   $$
 364   où $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $ symétrique (Schwarz).
 365  \end{block}
 366  \centerline{$ \implies $ La solution $  d_k $ est la valeur optimale de direction de descente.}
 367 \end{frame}
 368
 369 \subsection{Algorithme PQS}
 370
 371 %%%%% SLIDE 12
 372 \begin{frame}{Algorithme PQS}
 373  \begin{block}{ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.}
 374   \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.
 375   \newline
 376   \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
 377   \begin{enumerate}
 378    \item $ k := 0 $.
 379    \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $,
 380          \begin{enumerate}
 381           \item Résoudre le sous-problème quadratique :
 382                 $$
 383                  \mathcal{PQ}_k \left \{
 384                  \begin{array}{l}
 385                   \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 386                   g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\}              \\
 387                   h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 388                  \end{array}
 389                  \right .
 390                 $$
 391                 et obtenir la solution primale $ d_k $ et les multiplicateurs $ \lambda^{\prime} $ et $ \mu^{\prime} $ associé aux contraintes d’inégalité et d’égalité respectivement.
 392           \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $.
 393          \end{enumerate}
 394    \item Retourner $ x_k $.
 395   \end{enumerate}
 396  \end{block}
 397 \end{frame}
 398
 399 %%%%% SLIDE DE FIN
 400
 401 \begin{frame}[plain]
 402  \begin{beamerboxesrounded}%
 403   [lower=block title, %
 404    upper=block title,%
 405    shadow=true]{}
 406   \begin{center}
 407    {\Large  \textbf{{\color{mycvblue}Merci pour votre attention.}}}\\
 408    \vspace{3em}
 409    {\Large  \textbf{{\color{mycvblue}Questions?}}}\\
 410   \end{center}
 411  \end{beamerboxesrounded}
 412 \end{frame}
 413
 414 \end{document}