Merge branch 'master' of git.piment-noir.org:Projet_Recherche_Operationnelle
[Projet_Recherche_Operationnelle.git] / 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}