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   \newline
 221   On définit $ \mathcal{C} $ l'ensemble des contraintes par :
 222   $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$
 223  \end{defin}
 224 \end{frame}
 225
 226 \subsection{Prérequis mathématiques}
 227
 228 %%%%% SLIDE 2
 229 \begin{frame}{Prérequis mathématiques I}
 230  \begin{defin}
 231   On définit le Lagrangien associé à $ \mathcal{P} $ par :
 232   $$ \begin{array}{r c l}
 233     L : \mathbb{R}^n \times \mathbb{R}^q \times \mathbb{R}_+^p & \longrightarrow & \mathbb{R}                                                                                                      \\
 234     (x,\lambda,\mu)                                            & \longmapsto     & L(x,\lambda,\mu) = J(x) + \sum\limits_{i=1}^{q} \lambda_i h_i(x) + \sum\limits_{j=1}^{p} \mu_j g_j(x)           \\
 235                                                                &                 & L(x,\lambda,\mu) = J(x) + \langle \lambda,h(x) \rangle_{\mathbb{R}^q} + \langle \mu,g(x) \rangle_{\mathbb{R}^p}
 236    \end{array} $$
 237   où l’on note $ \lambda $  et $ \mu $ les vecteurs de coordonnées respectives $ (\lambda_1,\ldots,\lambda_q) $ et $ (\mu_1,\ldots,\mu_p) $.
 238  \end{defin}
 239  \begin{defin}
 240   Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
 241   \newline
 242   Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
 243   \[
 244    \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
 245   \]
 246  \end{defin}
 247 \end{frame}
 248
 249 %%%%% SLIDE 3
 250 \begin{frame}{Prérequis mathématiques II : Conditions nécessaires d'optimalité de Karuch-Kuhn-Tucker ou \textit{KKT}}
 251  \begin{theoreme}
 252   Soient $ J, g, h $ de classe $ \mathcal{C}^1 $, $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
 253   \newline
 254   Les conditions nécessaires pour que $ x^\ast \in \mathcal{C}$ soit un minimum local de $ J $ sont :
 255   \begin{center}
 256    $ \{ \nabla g_1(x^\ast),\ldots,\nabla g_p(x^\ast),\nabla h_1(x^\ast),\ldots,\nabla h_q(x^\ast) \} $ sont linéairement indépendants.
 257   \end{center}
 258   et
 259   \begin{center}
 260    $ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} $ tels que :
 261   \end{center}
 262   \begin{center}
 263    $ \nabla J(x^\ast) + \sum\limits_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum\limits_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $
 264   \end{center}
 265   \begin{center}
 266    $ \iff \nabla L(x^\ast,\lambda,\mu) = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $ où $ \lambda = (\lambda_1,\ldots,\lambda_q) $ et $ \mu = (\mu_1,\ldots,\mu_p) $.
 267   \end{center}
 268   % On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
 269   % \newline
 270   On nomme également les conditions \textit{KTT} conditions nécessaires d'optimalité du premier ordre.
 271  \end{theoreme}
 272 \end{frame}
 273
 274 %%%%% SLIDE 4
 275 \begin{frame}{Prérequis mathématiques II : Conditions suffisantes d'optimalité}
 276 \end{frame}
 277
 278 \section{Méthode PQS}
 279
 280 \subsection{Algorithme PQS}
 281
 282 %%%%% SLIDE 5
 283 \begin{frame}{Algorithme PQS}
 284  \begin{block}{ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.}
 285   \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.
 286   \newline
 287   \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
 288   \begin{enumerate}
 289    \item $ k := 0 $.
 290    \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $,
 291          \begin{enumerate}
 292           \item Résoudre le sous-problème quadratique :
 293                 $$
 294                  \mathcal{PQ}_k \left \{
 295                  \begin{array}{l}
 296                   \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 297                   g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\}              \\
 298                   h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 299                  \end{array}
 300                  \right .
 301                 $$
 302                 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.
 303           \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $.
 304          \end{enumerate}
 305    \item Retourner $ x_k $.
 306   \end{enumerate}
 307  \end{block}
 308 \end{frame}
 309
 310 \subsection{La méthode PQS est une méthode de descente}
 311
 312 %%%%% SLIDE 6
 313 \begin{frame}{Définition d'une méthode de descente}
 314  \begin{defin}
 315   Générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ avec :
 316   \begin{center}
 317    $ x_0 \in \mathbb{R}^n $ arbitraire,
 318   \end{center}
 319   \begin{center}
 320    $ x_{k+1} = x_k + s_kd_k $,
 321   \end{center}
 322   tel que :
 323   $$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
 324   où
 325   \begin{center}
 326    $ s_k \in \mathbb{R}_{+}^{*} $ est le pas de descente
 327   \end{center}
 328   et
 329   \begin{center}
 330    $ d_k \in \mathbb{R}^n $ est la direction de descente.
 331   \end{center}
 332  \end{defin}
 333 \end{frame}
 334
 335 %%%%% SLIDE 7
 336 \begin{frame}{Caractérisation d'une direction de descente}
 337  \begin{proposition}
 338   Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $.
 339   \newline
 340   d est un vecteur de descente de $ J $ en $ x_0 \in \mathbb{R}^n $ ssi :
 341   $$ \nabla J(x_0)^\top d < 0 $$
 342   De plus
 343   $$ \forall \beta < 1 \in \mathbb{R}_{+} \ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) + t\beta \nabla J(x_0)^\top d < J(x_0) $$
 344  \end{proposition}
 345 \end{frame}
 346
 347 %%%%% SLIDE 8
 348 \begin{frame}{Algorithme de descente générique}
 349  \begin{block}{ALGORITHME DE DESCENTE GÉNÉRIQUE.}
 350   \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
 351   \newline
 352   \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
 353   \begin{enumerate}
 354    \item $ k := 0 $.
 355    \item Tant que "test d’arrêt" non satisfait,
 356          \begin{enumerate}
 357           \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
 358           \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). $$
 359           \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
 360          \end{enumerate}
 361    \item Retourner $ x_k $.
 362   \end{enumerate}
 363  \end{block}
 364 \end{frame}
 365
 366 %%%%% SLIDE 9
 367 \begin{frame}{Critère d'arrêt}
 368  \begin{block}{}
 369   \begin{center}
 370    Critère d’arrêt $$ \parallel $$
 371   \end{center}
 372   \begin{tabular}{l l}
 373       & Test d’optimalité satisfait ($\norme{\nabla J(x_k)} < \varepsilon$)                          \\
 374    OU & (Stagnation de la valeur courante ($ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $) \\
 375       & ET Stagnation de la solution ($ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $))       \\
 376    OU & Nombre d’itérations maximum autorisé dépassé ($ k < IterMax $)
 377   \end{tabular}
 378  \end{block}
 379 \end{frame}
 380
 381 %%%%% SLIDE 10
 382 \begin{frame}{Recherche linéaire}
 383  \begin{block}{RECHERCHE LINÉAIRE : PAS FIXE.}
 384   $ s_k = s_{k-1} $
 385  \end{block}
 386  \begin{block}{RECHERCHE LINÉAIRE : PAS OPTIMAL.}
 387   $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
 388  \end{block}
 389 \end{frame}
 390
 391 %%%%% SLIDE 11
 392 \begin{frame}{Application à l'algorithme PQS}
 393  \begin{block}{Cas de l'algorithme PQS}
 394   \begin{enumerate}
 395    \item le critère d'arrêt est $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $;
 396    \item le pas $ s_k $ est fixe tel que $ \forall k \in \mathbb{N} \ s_k = 1 $. Il est possible d'ajouter une étape de recherche linéaire d'un pas optimal;
 397    \item la direction de descente $ d_k $ est une approximation de $ -H[J](x_k)^{-1} \nabla J(x_k) $.
 398   \end{enumerate}
 399  \end{block}
 400 \end{frame}
 401
 402 \subsection{La méthode PQS est une méthode Newtonienne}
 403
 404 %%%%% SLIDE 12
 405 \begin{frame}{Méthode Newtonienne I}
 406  \begin{defin}
 407   Une méthode de descente est dite Newtonienne si
 408   $$ d_k = -H[J](x_k)^{-1} \nabla J(x_k). $$
 409   Ce type de méthodes conduit aux \textit{algorithmes Newtoniens}.
 410  \end{defin}
 411  La direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ est l'unique solution du problème :
 412
 413  $$ \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 $$
 414
 415  $ \iff d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
 416 \end{frame}
 417
 418 %%%%% SLIDE 13
 419 \begin{frame}{Méthode Newtonienne II}
 420  \begin{tabular}{|p{15em}|p{15em}|}
 421   \hline
 422   Avantages                                                                                           & Inconvénients                                                                                                                                                     \\
 423   \hline
 424   sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). &                                                                                                                                                                   \\
 425   \hline
 426                                                                                                       & 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. \\
 427   \hline
 428                                                                                                       & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $.                                                                          \\
 429   \hline
 430                                                                                                       & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la hessienne est singulière.                                                     \\
 431   \hline
 432                                                                                                       & pas de distinction entre minima, maxima et points stationnaires.                                                                                                  \\
 433   \hline
 434  \end{tabular}
 435 \end{frame}
 436
 437 \subsection{Principe général de la méthode PQS}
 438
 439 %%%%% SLIDE 14
 440 \begin{frame}{Principe général I}
 441  Principe de résolution du problème $ \mathcal{P} $ en utilisant la méthode PQS :
 442  \begin{enumerate}
 443   \item Établir les conditions nécessaires et suffisantes d'existence et d'unicité d'une solution :
 444         \begin{enumerate}
 445          \item Conditions suffisantes \textit{KKT};
 446          \item Conditions nécessaires $ H[J] $ définie positive;
 447          \item Condition(s) de convexité de $ \mathcal{P} $.
 448         \end{enumerate}
 449   \item Approximation quadratique du Lagrangien $ L $ de $ \mathcal{P} $ par Taylor-Young à l'ordre 2 en $ x_k $:
 450         $$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) $$
 451         $$ + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$
 452   \item Approximation linéaire de $ g $ et $ h $ par Taylor-Young à l'ordre 1 en $ x_k $ :
 453         $$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
 454         $$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
 455   \item Condition d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
 456         $$ \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) $$
 457  \end{enumerate}
 458 \end{frame}
 459
 460 %%%%% SLIDE 15
 461 \begin{frame}{Principe général II}
 462  \begin{block}{}
 463   Résoudre le sous-problème quadratique $ \mathcal{PQ}_k $ avec contraintes linéaires :
 464   $$
 465    \mathcal{PQ}_k \left \{
 466    \begin{array}{l}
 467     \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 468     g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\}              \\
 469     h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 470    \end{array}
 471    \right .
 472   $$
 473   où $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $ symétrique (Schwarz).
 474  \end{block}
 475  \begin{center}
 476   $ \implies $ La solution $ d_k $ de $ \mathcal{PQ}_k $ est la valeur optimale de direction de descente.
 477  \end{center}
 478 \end{frame}
 479
 480 \subsection{Optimisation quadratique sous contraintes linéaires}
 481
 482 %%%%% SLIDE 16
 483 \begin{frame}{Problème quadratique avec contraintes linéaires}
 484  \begin{defin}
 485   $$
 486    \mathcal{PQ} \left \{
 487    \begin{array}{l}
 488     \displaystyle\min_{x \in \mathbb{R}^n} c^\top x + \frac{1}{2} x^\top \mathcal{Q} x \\
 489     A^\top x + b = 0                                                                   \\
 490    \end{array}
 491    \right .
 492   $$
 493   où $$ \mathcal{Q} \in \mathcal{M}_n(\mathbb{R}) \ sym\acute{e}trique, c \in \mathbb{R}^n, A \in  \mathcal{M}_{n,p}(\mathbb{R}), b \in \mathbb{R}^p $$
 494  \end{defin}
 495  \begin{defin}
 496   Soit $ F_\mu $ définit par :
 497   $$ F_\mu(x, \lambda, s) =
 498    \begin{pmatrix}
 499     \mathcal{Q}x - A^\top \lambda -s -c \\
 500     A x + b                             \\
 501     XS - \mu
 502    \end{pmatrix}
 503   $$
 504   où
 505   $$ X = diag(x) \in \mathcal{M}_n(\mathbb{R}), S = diag(s) \in \mathcal{M}_n(\mathbb{R}), s > 0 \ et \ \mu \in \mathbb{R}^n $$
 506  \end{defin}
 507 \end{frame}
 508
 509 \subsection{Algorithme des points intérieurs}
 510
 511 %%%%% SLIDE 17
 512 \begin{frame}{Algorithme des points intérieurs}
 513  \begin{block}{ALGORITHME DES POINTS INTÉRIEURS.}
 514   \textit{Entrées}: $ F_\mu : \mathbb{R}^n \times \mathbb{R}^p \times  \mathbb{R}^n \longrightarrow \mathcal{M}_{n,2n+p}(\mathbb{R}) $, $ (x_0,\lambda_0,s_0) \in \mathbb{R}^n \times \mathbb{R}^p \times  \mathbb{R}^n $ où $ (x_0,s_0) > 0 $ point initial arbitraire, $ \varepsilon > 0 $ précision demandée.
 515   \newline
 516   \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $, avec son coefficient $ \lambda_k $, du problème $ \mathcal{PQ} $.
 517   \begin{enumerate}
 518    \item $ k := 0 $.
 519    \item Tant que $ \frac{x_k^\top s_k}{n} > \varepsilon $,
 520          \begin{enumerate}
 521           \item Choisir $ \sigma_k \in [\sigma_{min},\sigma_{max}]$
 522           \item Résoudre le sytème linéaire d'équations où $ J_{F_\mu}(x_k,\lambda_k,s_k) $ désigne la matrice jacobienne de $ F_\mu $:
 523                 $$ J_{F_\mu}(x_k,\lambda_k,s_k) d = -
 524                  \begin{pmatrix}
 525                   \mathcal{Q}x - A^\top \lambda -s -c \\
 526                   A x + b                             \\
 527                   XS - \sigma_k \mu
 528                  \end{pmatrix} $$
 529                 pour déterminer $ d_k = (d_{x_k},d_{\lambda_k},d_{s_k}) $.
 530           \item Choisir $ \alpha_{max} $ la plus grande valeur $ \alpha $ tel que $ (x_k,s_k) + \alpha(d_{x_k},d_{s_k}) > 0 $.
 531           \item Choisir $ \alpha_k = \min \{1, \eta_k \sigma_{max} $ tel que $ \exists \eta_k \in [0,1]\} $.
 532           \item $ \mu_k = \frac{x_k^\top s_k}{n} $; $ (x_{k+1},\lambda_{k+1},s_{k+1}) := (x_k,\lambda_k,s_k) + \alpha_k d_k $; $ k := k + 1 $.
 533          \end{enumerate}
 534    \item Retourner $ (x_k,\lambda_k,s_k) $.
 535   \end{enumerate}
 536  \end{block}
 537 \end{frame}
 538
 539 %%%%% SLIDE DE FIN
 540
 541 \begin{frame}[plain]
 542  \begin{beamerboxesrounded}%
 543   [lower=block title, %
 544    upper=block title,%
 545    shadow=true]{}
 546   \begin{center}
 547    {\Large  \textbf{{\color{mycvblue}Merci pour votre attention.}}}\\
 548    \vspace{3em}
 549    {\Large  \textbf{{\color{mycvblue}Questions?}}}\\
 550   \end{center}
 551  \end{beamerboxesrounded}
 552 \end{frame}
 553
 554 \end{document}