Current work on the example
[Projet_Recherche_Operationnelle.git] / présentation / Slides_ProjetOptimRO.tex
CommitLineData
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}