Commit | Line | Data |
---|---|---|
f471c8ba JB |
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} | |
3f5da2c3 | 49 | %\usepackage{mathtools} |
f471c8ba JB |
50 | %\usepackage{fourier} |
51 | ||
52 | \usepackage{ragged2e} | |
f471c8ba JB |
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 | ||
3f5da2c3 | 85 | \newcommand{\norme}[1]{\left\Vert #1 \right\Vert} |
f471c8ba JB |
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 | ||
3f5da2c3 | 107 | \title[]{\LARGE{\textsc{Méthode de Programmation Quadratique Séquentielle ou PQS\\ en\\ Optimisation non linéraire sous contraintes}}} |
f471c8ba | 108 | |
3f5da2c3 | 109 | \author[Jérôme {\textsc Benoit} \& Sylvain {\textsc Papa}]{\textbf{Jérôme {\textsc Benoit}\\ \textbf{Sylvain {\textsc Papa}}}} |
f471c8ba | 110 | |
3f5da2c3 | 111 | \date[]{{\bf HUGo}\\ {\bf Polytech'Marseille} \\{\small Novembre 2018}} |
f471c8ba JB |
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}}} | |
3f5da2c3 JB |
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 | % } | |
f471c8ba JB |
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 | ||
3f5da2c3 | 199 | \subsection{Principe général} |
f471c8ba JB |
200 | |
201 | %%%%% SLIDE 1 | |
3f5da2c3 JB |
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} | |
f471c8ba JB |
216 | \end{frame} |
217 | ||
3f5da2c3 JB |
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} | |
f471c8ba JB |
229 | \end{frame} |
230 | ||
231 | %%%%% SLIDE 3 | |
3f5da2c3 JB |
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} | |
f471c8ba JB |
247 | \end{frame} |
248 | ||
3f5da2c3 JB |
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} | |
f471c8ba JB |
277 | \end{frame} |
278 | ||
3f5da2c3 JB |
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} | |
f471c8ba JB |
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} | |
3f5da2c3 | 401 | {\Large \textbf{{\color{mycvblue}Merci pour votre attention.}}}\\ |
f471c8ba JB |
402 | \vspace{3em} |
403 | {\Large \textbf{{\color{mycvblue}Questions?}}}\\ | |
404 | \end{center} | |
405 | \end{beamerboxesrounded} | |
f471c8ba JB |
406 | \end{frame} |
407 | ||
408 | \end{document} |