[Projet_Recherche_Operationnelle.git] / présentation / Slides_ProjetOptimRO.tex

\documentclass[9pt,blackandwhite,roman,handout]{beamer}
\usepackage{etex}

\usefonttheme{professionalfonts}


% Setup appearance:
%\usetheme{Warsaw}
\usetheme{Darmstadt}

%\usecolortheme{seahorse}
%\usecolortheme{dove}
\usecolortheme{seagull}
%\usefonttheme[onlylarge]{structurebold}
%\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
%\setbeamertemplate{navigation symbols}{}



% Standard packages
%\usepackage[frenchb]{babel}
%\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
\usepackage{cmbright}
\usepackage[sans]{dsfont}
\usepackage{pifont}
%calscaled=.94,
%frakscaled=.97,
\usepackage[cal=euler,scr=rsfso]{mathalfa}%bb=cm,
%frak=mma,
%scr=esstix
\usepackage{mathrsfs} % pour faire des majuscules calligraphiées \mathcal{blabla}
%\usepackage[french,lined]{algorithm2e} % rajouter linesnumbered dans les arguments pour numéroter les lignes des algos, boxed pour l'encadrement
%\usepackage{extsizes}
%\usepackage{MnSymbol}
\usepackage{graphicx}
\usepackage{mathabx}
\usepackage[all]{xy}
\usepackage{ulem}

\usepackage{DotArrow}
%\usepackage[varg]{txfonts}
%\usepackage{matptmx}
\usepackage{extpfeil}
%\usepackage{MyMnSymbol}
\usepackage{comment}
%\usepackage{etex}
%\usepackage{mathtools}
%\usepackage{fourier}

\usepackage{ragged2e}

% Setup TikZ
\usepackage{tikz}
\usetikzlibrary{matrix,arrows}
\tikzstyle{block}=[draw opacity=0.7,line width=1.4cm]

\newcommand{\gk}{$g_k = \left \{ \begin{array}{ll}
                q^k+q^{k-1}-q^\frac{k+1}{2} - 2q^\frac{k-1}{2}+1 & \mbox{si } k \equiv 1 \pmod 2,\\
                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.
                \end{array} \right .$}

\newcommand{\ext}{\xymatrix{
    \FF= \Fq(x)(y) \ar@{-}[d]^{<\infty} \\ \Fq(x) \ar@{-}[d] \\ \Fq} }

\newcommand{\twoheaddownarrow}{%
\mathrel{\reflectbox{\rotatebox[origin=c]{-90}{$\xtwoheadrightarrow[ \; ]{   \reflectbox{\rotatebox[origin=c]{-90}{$\pi_Q \ $}} \ \  }$}}}}

\newcommand{\longdownmapsto}{%
\mathrel{\reflectbox{\rotatebox[origin=c]{-90}{$\xmapsto{ \ \ \ \reflectbox{\rotatebox[origin=c]{-90}{$\pi_Q \ $}} \ \ \ }$}}}}

\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{}}_?}

\newcommand{\myubrace}[2]{\rotatebox[origin=c]{90}{$
\rotatebox[origin=c]{-90}{#1} \left \{
\begin{array}{l}
         \vspace{#2} \\
\end{array}
\right . \hspace{-1em}
$}}

\newcommand{\bluebrace}{{\color{blue}\left\{}}

\newcommand{\norme}[1]{\left\Vert #1 \right\Vert}

\definecolor{mycvblue}{rgb}{0.302,0.537,0.737}


\setbeamercolor{structure}{fg=mycvblue}
\setbeamercolor{palette primary}{fg=mycvblue}
\setbeamercolor{subsection in head/foot}{parent=palette primary}

\setbeamertemplate{navigation symbols}{
%      \insertslidenavigationsymbol
%      \insertframenavigationsymbol
%      \insertsubsectionnavigationsymbol
%      \insertsectionnavigationsymbol
%      \insertdocnavigationsymbol
%      \insertbackfindforwardnavigationsymbol
}

%\renewcommand{\item}{\item[$\bullet$]}



\title[]{\LARGE{\textsc{Méthode de Programmation Quadratique Séquentielle ou PQS\\ en\\ Optimisation non linéraire sous contraintes}}}

\author[Jérôme {\textsc Benoit} \& Sylvain {\textsc Papa}]{\textbf{Jérôme {\textsc Benoit}\\ \textbf{Sylvain {\textsc Papa}}}}

\date[]{{\bf HUGo}\\ {\bf Polytech'Marseille} \\{\small Novembre 2018}}

\newtheorem{defin}{Définition}
\newtheorem{theoreme}{Théorème}
\newtheorem{lemme}{Lemme}
\newtheorem{corollaire}{Corollaire}
\newtheorem{proposition}{Proposition}
\newtheorem{propriete}{Propriété}
%\newtheorem{exemple}[definition]{Exemple}

\newcommand{\NN}{\ensuremath{\mathbb{N}}}
\newcommand{\CC}{\ensuremath{\mathbb{C}}}
\newcommand{\ZZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\PF}{\mathbf{P}_F}
\newcommand{\DF}{\mathsf{Div}(F)}
\newcommand{\Jac}{\ensuremath{\mathcal{J}\mathsf{ac}(F/\Fq)}}
\newcommand{\Fqr}[2][q]{\mathds{F}_{\!{#1}^{#2}}}
\newcommand{\Fq}{\Fqr{}}
\newcommand{\F}{\mathds{F}}
\newcommand{\FF}{\mathsf{F}}
\newcommand{\Fqn}{\Fqr{n}}
\newcommand{\D}[1][D]{\ensuremath{\mathcal{#1}}}
\newcommand{\Ld}[1][\D]{\ensuremath{\mathscr{L}\!\!\left(#1\right)}} % utilisation :  \Ld ou \Ld[A] pour un diviseur A au lieu de D
\newcommand{\Ak}[1][k]{\ensuremath{\mathbb{A}_{#1}}}
\newcommand{\A}{\ensuremath{\mathsf{A}}}
\newcommand{\Cl}{\ensuremath{\mathsf{Cl}}}
\newcommand{\mus}{\ensuremath{\mu^\mathsf{sym}}}
\newcommand{\Ms}{\ensuremath{M^\mathsf{sym}}}
\newcommand{\ms}{\ensuremath{m^\mathsf{sym}}}
\newcommand{\chch}{{C}hudnovsky-{C}hudnovsky}
\newcommand{\ch}{{C}hudnovsky}



\addtobeamertemplate{footline}{\texttt{\hfill\insertframenumber/{\inserttotalframenumber}}}

% \AtBeginSubsection[] {
% \begin{frame}<beamer>
% \frametitle{Plan}
% \tableofcontents[currentsection,currentsubsection]
% \end{frame}
% }
% \AtBeginSection[] {
% \begin{frame}<beamer>
% \frametitle{Plan}
% \tableofcontents[currentsection]%,currentsubsection]
% \end{frame}
% }

\setbeamertemplate{sections/subsections in toc}[sections numbered]
%\setbeamertemplate{sections in toc}[sections numbered]

\begin{document}

% \begin{frame}[plain]
%
%  \begin{center}
%
%   {\bf Institut de Mathématiques de Marseille}\\
%
%   {\bf Equipe Analyse, Géométrie et Topologie (AGT) }\\
%
%   \vspace{2em}
%
%   {\bf Séminaire de Géométrie Complexe}\\
%   Mardi 12 Juin 2018
%  \end{center}
%
%  \begin{center}
%
%  \end{center}
%
% \end{frame}

\begin{frame}[plain]

 \titlepage

\end{frame}

\begin{frame}[plain]{Plan}

 \tableofcontents

\end{frame}

\section{Introduction}

\subsection{Principe général}

%%%%% SLIDE 1
\begin{frame}{Principe général I}
 \begin{defin}
  Résoudre le problème $ \mathcal{P} $ :
  $$
   \mathcal{P} \left \{
   \begin{array}{l}
    \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
    g(x) \leq 0                                 \\
    h(x) = 0
   \end{array}
   \right .
  $$
  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. $$
 \end{defin}
\end{frame}

%%%%% SLIDE 1
\begin{frame}{Principe général II}
 \begin{enumerate}
  \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} $).
  \item Approximation quadratique du Lagrangien $ L $ de $ \mathcal{P} $ par Taylor-Young à l'ordre 2 en $ x_k $:
        $$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \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) $$
  \item Approximation linéaire de $ g $ et $ h $ par Taylor-Young à l'ordre 1 en $ x_k $ :
        $$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
        $$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
 \end{enumerate}
\end{frame}

%%%%% SLIDE 3
\begin{frame}{Principe général III}
 Conditions d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
 \begin{block}{}
  Résoudre le sous-problème quadratique $ \mathcal{PQ}_k $ avec contraintes linéaires :
  $$
   \mathcal{PQ}_k \left \{
   \begin{array}{l}
    \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
    g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\}              \\
    h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
   \end{array}
   \right .
  $$
  où $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $ symétrique (Schwarz).
 \end{block}
\end{frame}

\section{Algorithme PQS}

%%%%% SLIDE 4
\begin{frame}{Algorithme PQS}
 \begin{block}{ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.}
  \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.
  \newline
  \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
  \begin{enumerate}
   \item $ k := 0 $.
   \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $,
         \begin{enumerate}
          \item Résoudre le sous-problème quadratique :
                $$
                 \mathcal{PQ}_k \left \{
                 \begin{array}{l}
                  \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
                  g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\}              \\
                  h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
                 \end{array}
                 \right .
                $$
                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.
          \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $.
         \end{enumerate}
   \item Retourner $ x_k $.
  \end{enumerate}
 \end{block}
\end{frame}

% %%%%% SLIDE 6
% \begin{frame}
%
% \end{frame}
%
% \section{Algorithme de D.V. et G.V. Chudnovsky (1987)}
%
% \subsection{Avec des places rationnelles}
%
% %%%%% SLIDE 9
% \begin{frame}{Algorithme original de Chudnovsky et Chudnovsky}
%
% \end{frame}
%
% \subsection{Principe}
%
% %%%%% SLIDE 8
% \begin{frame}{Principe pour multiplier avec l'algorithme de Chudnovsky}
%
% \end{frame}
%
% \subsection{Avec des places de degré un et deux}
%
% %%%%% SLIDE 10
% \begin{frame}{Evaluations sur des places de degré 1 et 2}
%
% \end{frame}
%
% \section{Conditions permettant l'utilisation de l'algorithme}
%
% \subsection{Conditions principales}
%
% %%%%% SLIDE 11
% \begin{frame}{Conditions suffisantes pour appliquer l'algorithme}
%
% \end{frame}
%
% \subsection{Applications}
%
% %%%%% SLIDE 11
% \begin{frame}{Le cas des extensions de petits degré}
%
% \end{frame}
%
% \begin{frame}{Algorithme de Chudnovsky sur un corps de fonctions hyperelliptique de genre 2}
%
% \end{frame}
%
%
% \begin{frame}{Exemple pour les \textit{petites} extensions $\F_{16^n}$ de $\F_{16}$}
%
% \end{frame}
%
% \setbeamercovered{transparent}
%
% \begin{frame}
%
% \end{frame}
%
% %%%%%%%%%%%%% T  %%%%%%%%%%%%%%%
%
%
% %%%%%%%%%%%%% T  %%%%%%%%%%%%%%%
%
%
% %%%%%%%%%%%%% T  %%%%%%%%%%%%%%%
%
% \section{Nouveau résultats}
%
% \subsection{Bornes uniformes connues}
%
% \begin{frame}
%
% \end{frame}
%
% \subsection{Nouvelles bornes uniformes}
%
% \begin{frame}
%
% \end{frame}
%
% %%%%% SLIDE 14
% \begin{frame}{Corps de fonctions sur $\F_{p^2}$}
%
% \end{frame}
%
% \begin{frame}
%
% \end{frame}
%
% %%%%%%%%%%%%% T  %%%%%%%%%%%%%%%
%
% \begin{frame}
%
% \end{frame}
%
% \begin{frame}
%
% \end{frame}
%
% \section{Conclusions et perspectives}
%
% \subsection{Problèmes et/ou travail en cours}
%
% %%%%% SLIDE 15
%
% \begin{frame}{Conclusion}
%
% \end{frame}
%
% \begin{frame}
%
% \end{frame}

%%%%% SLIDE DE FIN

\begin{frame}[plain]
 \begin{beamerboxesrounded}%
  [lower=block title, %
   upper=block title,%
   shadow=true]{}
  \begin{center}
   {\Large  \textbf{{\color{mycvblue}Merci pour votre attention.}}}\\
   \vspace{3em}
   {\Large  \textbf{{\color{mycvblue}Questions?}}}\\
  \end{center}
 \end{beamerboxesrounded}
\end{frame}

\end{document}