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