Correction dans la structure de la trace d'execution.

[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{Définition de la problèmatique}

%%%%% SLIDE 1
\begin{frame}{Définition de la problèmatique}
 \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ù
  \begin{center}
   $ g: \mathbb{R}^n \longrightarrow \mathbb{R}^p $ représente les contraintes d'inégalité,
  \end{center}
  \begin{center}
   $ h: \mathbb{R}^n \longrightarrow \mathbb{R}^q $ représente les contraintes d'égalité,
  \end{center}
  et
  \begin{center}
   $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ est la fonction objectif ou coût.
  \end{center}
  en utilisant des méthodes numériques itératives.
 \end{defin}
\end{frame}

\subsection{Prérequis mathématiques}

\section{La méthode PQS est une méthode de descente}

\subsection{Définition}

%%%%% SLIDE 2
\begin{frame}{Définition d'une méthode de descente}
 \begin{defin}
  Générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ avec :
  \begin{center}
   $ x_0 \in \mathbb{R}^n $ arbitraire,
  \end{center}
  \begin{center}
   $ x_{k+1} = x_k + s_kd_k $,
  \end{center}
  tel que :
  $$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
  où
  \begin{center}
   $ s_k \in \mathbb{R}_{+}^{*} $ est le pas de descente
  \end{center}
  et
  \begin{center}
   $ d_k \in \mathbb{R}^n $ est la direction de descente.
  \end{center}
 \end{defin}
\end{frame}

\subsection{Algorithme}

%%%%% SLIDE 3
\begin{frame}{Algorithme de descente modèle}
 \begin{block}{ALGORITHME DE DESCENTE MODÈLE.}
  \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
  \newline
  \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
  \begin{enumerate}
   \item $ k := 0 $.
   \item Tant que "test d’arrêt" non satisfait,
         \begin{enumerate}
          \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
          \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). $$
          \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
         \end{enumerate}
   \item Retourner $ x_k $.
  \end{enumerate}
 \end{block}
\end{frame}

\subsubsection{Direction de descente}

%%%%% SLIDE 4
\begin{frame}{Direction de descente}
 Deux grandes stratégies :
 \begin{itemize}
  \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}.
  \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}.
 \end{itemize}
\end{frame}

\subsubsection{Critère d'arrêt}

%%%%% SLIDE 5
\begin{frame}{Critère d'arrêt}
 \centerline{Critère d’arrêt =}
 \begin{tabular}{c}
  Test d’optimalité satisfait($\norme{\nabla J(x_k)} < \varepsilon$)                             \\
  OU (Stagnation de la valeur courante($ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $) \\
  ET Stagnation de la solution($ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $))          \\
  OU Nombre d’itérations maximum autorisé dépassé($ k < IterMax $)
 \end{tabular}
\end{frame}

\subsubsection{Recherche linéaire}

%%%%% SLIDE 6
\begin{frame}{Recherche linéaire}
 \begin{block}{RECHERCHE LINÉAIRE : PAS FIXE.}
  $ s_k = s_{k-1} $
 \end{block}
 \begin{block}{RECHERCHE LINÉAIRE : PAS OPTIMAL.}
  $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
 \end{block}
\end{frame}

\subsubsection{Méthode Newtonienne}

%%%%% SLIDE 7
\begin{frame}{Méthode Newtonienne I}
 Choix de la direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ solution unique du problème :

 $$ \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 $$

 $ \iff d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
\end{frame}

%%%%% SLIDE 8
\begin{frame}{Méthode Newtonienne II}
 \begin{tabular}{|p{15em}|p{15em}|}
  \hline
  Avantages                                                                                           & Inconvénients                                                                                                                                                     \\
  \hline
  sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). &                                                                                                                                                                   \\
  \hline
                                                                                                      & 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. \\
  \hline
                                                                                                      & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $.                                                                          \\
  \hline
                                                                                                      & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la    hessienne est singulière.                                                  \\
  \hline
                                                                                                      & pas de distinction entre minima, maxima et points stationnaires.                                                                                                  \\
  \hline
 \end{tabular}
\end{frame}

\section{Méthode PQS}

\subsection{Principe général}

%%%%% SLIDE 9
\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 10
\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) $$
  \item Condition d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
        $$ \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) $$
 \end{enumerate}
\end{frame}

%%%%% SLIDE 11
\begin{frame}{Principe général III}
 \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}
 \centerline{$ \implies $ La solution $  d_k $ est la valeur optimale de direction de descente.}
\end{frame}

\subsection{Algorithme PQS}

%%%%% SLIDE 12
\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 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}