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ù
 209   \begin{center}
 210    $ g: \mathbb{R}^n \longrightarrow \mathbb{R}^p $ représente les contraintes d'inégalité,
 211   \end{center}
 212   \begin{center}
 213    $ h: \mathbb{R}^n \longrightarrow \mathbb{R}^q $ représente les contraintes d'égalité,
 214   \end{center}
 215   et
 216   \begin{center}
 217    $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ est la fonction objectif ou coût.
 218   \end{center}
 219   en utilisant des méthodes numériques itératives.
 220  \end{defin}
 221 \end{frame}
 222
 223 \subsection{Prérequis mathématiques}
 224
 225 \section{La méthode PQS est une méthode de descente}
 226
 227 \subsection{Définition}
 228
 229 %%%%% SLIDE 2
 230 \begin{frame}{Définition d'une méthode de descente}
 231  \begin{defin}
 232   Générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ avec :
 233   \begin{center}
 234    $ x_0 \in \mathbb{R}^n $ arbitraire,
 235   \end{center}
 236   \begin{center}
 237    $ x_{k+1} = x_k + s_kd_k $,
 238   \end{center}
 239   tel que :
 240   $$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
 241   où
 242   \begin{center}
 243    $ s_k \in \mathbb{R}_{+}^{*} $ est le pas de descente
 244   \end{center}
 245   et
 246   \begin{center}
 247    $ d_k \in \mathbb{R}^n $ est la direction de descente.
 248   \end{center}
 249  \end{defin}
 250 \end{frame}
 251
 252 \subsection{Algorithme}
 253
 254 %%%%% SLIDE 3
 255 \begin{frame}{Algorithme de descente modèle}
 256  \begin{block}{ALGORITHME DE DESCENTE MODÈLE.}
 257   \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
 258   \newline
 259   \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
 260   \begin{enumerate}
 261    \item $ k := 0 $.
 262    \item Tant que "test d’arrêt" non satisfait,
 263          \begin{enumerate}
 264           \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
 265           \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). $$
 266           \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
 267          \end{enumerate}
 268    \item Retourner $ x_k $.
 269   \end{enumerate}
 270  \end{block}
 271 \end{frame}
 272
 273 \subsubsection{Direction de descente}
 274
 275 %%%%% SLIDE 4
 276 \begin{frame}{Direction de descente}
 277  Deux grandes stratégies :
 278  \begin{itemize}
 279   \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}.
 280   \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}.
 281  \end{itemize}
 282 \end{frame}
 283
 284 \subsubsection{Critère d'arrêt}
 285
 286 %%%%% SLIDE 5
 287 \begin{frame}{Critère d'arrêt}
 288  \centerline{Critère d’arrêt =}
 289  \begin{tabular}{c}
 290   Test d’optimalité satisfait($\norme{\nabla J(x_k)} < \varepsilon$)                             \\
 291   OU (Stagnation de la valeur courante($ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $) \\
 292   ET Stagnation de la solution($ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $))          \\
 293   OU Nombre d’itérations maximum autorisé dépassé($ k < IterMax $)
 294  \end{tabular}
 295 \end{frame}
 296
 297 \subsubsection{Recherche linéaire}
 298
 299 %%%%% SLIDE 6
 300 \begin{frame}{Recherche linéaire}
 301  \begin{block}{RECHERCHE LINÉAIRE : PAS FIXE.}
 302   $ s_k = s_{k-1} $
 303  \end{block}
 304  \begin{block}{RECHERCHE LINÉAIRE : PAS OPTIMAL.}
 305   $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
 306  \end{block}
 307 \end{frame}
 308
 309 \subsubsection{Méthode Newtonienne}
 310
 311 %%%%% SLIDE 7
 312 \begin{frame}{Méthode Newtonienne I}
 313  Choix de la direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ solution unique du problème :
 314
 315  $$ \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 $$
 316
 317  $ \iff d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
 318 \end{frame}
 319
 320 %%%%% SLIDE 8
 321 \begin{frame}{Méthode Newtonienne II}
 322  \begin{tabular}{|p{15em}|p{15em}|}
 323   \hline
 324   Avantages                                                                                           & Inconvénients                                                                                                                                                     \\
 325   \hline
 326   sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). &                                                                                                                                                                   \\
 327   \hline
 328                                                                                                       & 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. \\
 329   \hline
 330                                                                                                       & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $.                                                                          \\
 331   \hline
 332                                                                                                       & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la    hessienne est singulière.                                                  \\
 333   \hline
 334                                                                                                       & pas de distinction entre minima, maxima et points stationnaires.                                                                                                  \\
 335   \hline
 336  \end{tabular}
 337 \end{frame}
 338
 339 \section{Méthode PQS}
 340
 341 \subsection{Principe général}
 342
 343 %%%%% SLIDE 9
 344 \begin{frame}{Principe général I}
 345  \begin{defin}
 346   Résoudre le problème $ \mathcal{P} $ :
 347   $$
 348    \mathcal{P} \left \{
 349    \begin{array}{l}
 350     \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
 351     g(x) \leq 0                                 \\
 352     h(x) = 0
 353    \end{array}
 354    \right .
 355   $$
 356   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. $$
 357  \end{defin}
 358 \end{frame}
 359
 360 %%%%% SLIDE 10
 361 \begin{frame}{Principe général II}
 362  \begin{enumerate}
 363   \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} $).
 364   \item Approximation quadratique du Lagrangien $ L $ de $ \mathcal{P} $ par Taylor-Young à l'ordre 2 en $ x_k $:
 365         $$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) $$
 366         $$ + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$
 367   \item Approximation linéaire de $ g $ et $ h $ par Taylor-Young à l'ordre 1 en $ x_k $ :
 368         $$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
 369         $$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
 370   \item Condition d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
 371         $$ \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) $$
 372  \end{enumerate}
 373 \end{frame}
 374
 375 %%%%% SLIDE 11
 376 \begin{frame}{Principe général III}
 377  \begin{block}{}
 378   Résoudre le sous-problème quadratique $ \mathcal{PQ}_k $ avec contraintes linéaires :
 379   $$
 380    \mathcal{PQ}_k \left \{
 381    \begin{array}{l}
 382     \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 383     g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\}              \\
 384     h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 385    \end{array}
 386    \right .
 387   $$
 388   où $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $ symétrique (Schwarz).
 389  \end{block}
 390  \centerline{$ \implies $ La solution $  d_k $ est la valeur optimale de direction de descente.}
 391 \end{frame}
 392
 393 \subsection{Algorithme PQS}
 394
 395 %%%%% SLIDE 12
 396 \begin{frame}{Algorithme PQS}
 397  \begin{block}{ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.}
 398   \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.
 399   \newline
 400   \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
 401   \begin{enumerate}
 402    \item $ k := 0 $.
 403    \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $,
 404          \begin{enumerate}
 405           \item Résoudre le sous-problème quadratique :
 406                 $$
 407                  \mathcal{PQ}_k \left \{
 408                  \begin{array}{l}
 409                   \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 410                   g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\}              \\
 411                   h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 412                  \end{array}
 413                  \right .
 414                 $$
 415                 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.
 416           \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $.
 417          \end{enumerate}
 418    \item Retourner $ x_k $.
 419   \end{enumerate}
 420  \end{block}
 421 \end{frame}
 422
 423 %%%%% SLIDE DE FIN
 424
 425 \begin{frame}[plain]
 426  \begin{beamerboxesrounded}%
 427   [lower=block title, %
 428    upper=block title,%
 429    shadow=true]{}
 430   \begin{center}
 431    {\Large  \textbf{{\color{mycvblue}Merci pour votre attention.}}}\\
 432    \vspace{3em}
 433    {\Large  \textbf{{\color{mycvblue}Questions?}}}\\
 434   \end{center}
 435  \end{beamerboxesrounded}
 436 \end{frame}
 437
 438 \end{document}