| 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 | Elles conduisent 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 $ 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}{} |
| 484 | \begin{block}{ALGORITHME OPTIMAL} |
| 485 | \end{block} |
| 486 | \end{frame} |
| 487 | |
| 488 | %%%%% SLIDE DE FIN |
| 489 | |
| 490 | \begin{frame}[plain] |
| 491 | \begin{beamerboxesrounded}% |
| 492 | [lower=block title, % |
| 493 | upper=block title,% |
| 494 | shadow=true]{} |
| 495 | \begin{center} |
| 496 | {\Large \textbf{{\color{mycvblue}Merci pour votre attention.}}}\\ |
| 497 | \vspace{3em} |
| 498 | {\Large \textbf{{\color{mycvblue}Questions?}}}\\ |
| 499 | \end{center} |
| 500 | \end{beamerboxesrounded} |
| 501 | \end{frame} |
| 502 | |
| 503 | \end{document} |