[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.
  \newline
  On définit $ \mathcal{C} $ l'ensemble des contraintes par :
  $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$
 \end{defin}
\end{frame}

\subsection{Prérequis mathématiques}

%%%%% SLIDE 2
\begin{frame}{Prérequis mathématiques I}
 \begin{defin}
  On définit le Lagrangien associé à $ \mathcal{P} $ par :
  $$ \begin{array}{r c l}
    L : \mathbb{R}^n \times \mathbb{R}^q \times \mathbb{R}_+^p & \longrightarrow & \mathbb{R}                                                                                                      \\
    (x,\lambda,\mu)                                            & \longmapsto     & L(x,\lambda,\mu) = J(x) + \sum\limits_{i=1}^{q} \lambda_i h_i(x) + \sum\limits_{j=1}^{p} \mu_j g_j(x)           \\
                                                               &                 & L(x,\lambda,\mu) = J(x) + \langle \lambda,h(x) \rangle_{\mathbb{R}^q} + \langle \mu,g(x) \rangle_{\mathbb{R}^p}
   \end{array} $$
  où l’on note $ \lambda $  et $ \mu $ les vecteurs de coordonnées respectives $ (\lambda_1,\ldots,\lambda_q) $ et $ (\mu_1,\ldots,\mu_p) $.
 \end{defin}
 \begin{defin}
  Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
  \newline
  Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
  \[
   \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
  \]
 \end{defin}
\end{frame}

%%%%% SLIDE 3
\begin{frame}{Prérequis mathématiques II : Conditions nécessaires d'optimalité de Karuch-Kuhn-Tucker ou \textit{KKT}}
 \begin{theoreme}
  Soient $ J, g, h $ de classe $ \mathcal{C}^1 $, $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
  \newline
  Les conditions nécessaires pour que $ x^\ast \in \mathcal{C}$ soit un minimum local de $ J $ sont :
  \begin{center}
   $ \{ \nabla g_1(x^\ast),\ldots,\nabla g_p(x^\ast),\nabla h_1(x^\ast),\ldots,\nabla h_q(x^\ast) \} $ sont linéairement indépendants.
  \end{center}
  et
  \begin{center}
   $ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} $ tels que :
  \end{center}
  \begin{center}
   $ \nabla J(x^\ast) + \sum\limits_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum\limits_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $
  \end{center}
  \begin{center}
   $ \iff \nabla L(x^\ast,\lambda,\mu) = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $ où $ \lambda = (\lambda_1,\ldots,\lambda_q) $ et $ \mu = (\mu_1,\ldots,\mu_p) $.
  \end{center}
  % On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
  % \newline
  On nomme également les conditions \textit{KTT} conditions nécessaires d'optimalité du premier ordre.
 \end{theoreme}
\end{frame}

%%%%% SLIDE 4
\begin{frame}{Prérequis mathématiques II : Conditions suffisantes d'optimalité}
\end{frame}

\section{Méthode PQS}

\subsection{Algorithme PQS}

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

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

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

%%%%% SLIDE 7
\begin{frame}{Caractérisation d'une direction de descente}
 \begin{proposition}
  Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $.
  \newline
  d est un vecteur de descente de $ J $ en $ x_0 \in \mathbb{R}^n $ ssi :
  $$ \nabla J(x_0)^\top d < 0 $$
  De plus
  $$ \forall \beta < 1 \in \mathbb{R}_{+} \ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) + t\beta \nabla J(x_0)^\top d < J(x_0) $$
 \end{proposition}
\end{frame}

%%%%% SLIDE 8
\begin{frame}{Algorithme de descente générique}
 \begin{block}{ALGORITHME DE DESCENTE GÉNÉRIQUE.}
  \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}

%%%%% SLIDE 9
\begin{frame}{Critère d'arrêt}
 \begin{block}{}
  \begin{center}
   Critère d’arrêt $$ \parallel $$
  \end{center}
  \begin{tabular}{l l}
      & 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{block}
\end{frame}

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

%%%%% SLIDE 11
\begin{frame}{Application à l'algorithme PQS}
 \begin{block}{Cas de l'algorithme PQS}
  \begin{enumerate}
   \item le critère d'arrêt est $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $;
   \item le pas $ s_k $ est fixe tel que $ \forall k \in \mathbb{N} \ s_k = 1 $. Il est possible d'ajouter une étape de recherche linéaire d'un pas optimal;
   \item la direction de descente $ d_k $ est une approximation de $ -H[J](x_k)^{-1} \nabla J(x_k) $.
  \end{enumerate}
 \end{block}
\end{frame}

\subsection{La méthode PQS est une méthode Newtonienne}

%%%%% SLIDE 12
\begin{frame}{Méthode Newtonienne I}
 \begin{defin}
  Une méthode de descente est dite Newtonienne si
  $$ d_k = -H[J](x_k)^{-1} \nabla J(x_k). $$
  Ce type de méthodes conduit aux \textit{algorithmes Newtoniens}.
 \end{defin}
 La direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ est l'unique solution 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 13
\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}

\subsection{Principe général de la méthode PQS}

%%%%% SLIDE 14
\begin{frame}{Principe général I}
 Principe de résolution du problème $ \mathcal{P} $ en utilisant la méthode PQS :
 \begin{enumerate}
  \item Établir les conditions nécessaires et suffisantes d'existence et d'unicité d'une solution :
        \begin{enumerate}
         \item Conditions suffisantes \textit{KKT};
         \item Conditions nécessaires $ H[J] $ définie positive;
         \item Condition(s) de convexité de $ \mathcal{P} $.
        \end{enumerate}
  \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 15
\begin{frame}{Principe général II}
 \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}
 \begin{center}
  $ \implies $ La solution $ d_k $ de $ \mathcal{PQ}_k $ est la valeur optimale de direction de descente.
 \end{center}
\end{frame}

\subsection{Optimisation quadratique sous contraintes linéaires}

%%%%% SLIDE 16
\begin{frame}{Problème quadratique avec contraintes linéaires}
 \begin{defin}
  $$
   \mathcal{PQ} \left \{
   \begin{array}{l}
    \displaystyle\min_{x \in \mathbb{R}^n} c^\top x + \frac{1}{2} x^\top \mathcal{Q} x \\
    A^\top x + b = 0                                                                   \\
   \end{array}
   \right .
  $$
  où $$ \mathcal{Q} \in \mathcal{M}_n(\mathbb{R}) \ sym\acute{e}trique, c \in \mathbb{R}^n, A \in  \mathcal{M}_{n,p}(\mathbb{R}), b \in \mathbb{R}^p $$
 \end{defin}
 \begin{defin}
  Soit $ F_\mu $ définit par :
  $$ F_\mu(x, \lambda, s) =
   \begin{pmatrix}
    \mathcal{Q}x - A^\top \lambda -s -c \\
    A x + b                             \\
    XS - \mu
   \end{pmatrix}
  $$
  où
  $$ X = diag(x) \in \mathcal{M}_n(\mathbb{R}), S = diag(s) \in \mathcal{M}_n(\mathbb{R}), s > 0 \ et \ \mu \in \mathbb{R}^n $$
 \end{defin}
\end{frame}

\subsection{Algorithme des points intérieurs}

%%%%% SLIDE 17
\begin{frame}{Algorithme des points intérieurs}
 \begin{block}{ALGORITHME DES POINTS INTÉRIEURS.}
  \textit{Entrées}: $ F_\mu : \mathbb{R}^n \times \mathbb{R}^p \times  \mathbb{R}^n \longrightarrow \mathcal{M}_{n,2n+p}(\mathbb{R}) $, $ (x_0,\lambda_0,s_0) \in \mathbb{R}^n \times \mathbb{R}^p \times  \mathbb{R}^n $ où $ (x_0,s_0) > 0 $ point initial arbitraire, $ \varepsilon > 0 $ précision demandée.
  \newline
  \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $, avec son coefficient $ \lambda_k $, du problème $ \mathcal{PQ} $.
  \begin{enumerate}
   \item $ k := 0 $.
   \item Tant que $ \frac{x_k^\top s_k}{n} > \varepsilon $,
         \begin{enumerate}
          \item Choisir $ \sigma_k \in [\sigma_{min},\sigma_{max}]$
          \item Résoudre le sytème linéaire d'équations où $ J_{F_\mu}(x_k,\lambda_k,s_k) $ désigne la matrice jacobienne de $ F_\mu $:
                $$ J_{F_\mu}(x_k,\lambda_k,s_k) d = -
                 \begin{pmatrix}
                  \mathcal{Q}x - A^\top \lambda -s -c \\
                  A x + b                             \\
                  XS - \sigma_k \mu
                 \end{pmatrix} $$
                pour déterminer $ d_k = (d_{x_k},d_{\lambda_k},d_{s_k}) $.
          \item Choisir $ \alpha_{max} $ la plus grande valeur $ \alpha $ tel que $ (x_k,s_k) + \alpha(d_{x_k},d_{s_k}) > 0 $.
          \item Choisir $ \alpha_k = \min \{1, \eta_k \sigma_{max} $ tel que $ \exists \eta_k \in [0,1]\} $.
          \item $ \mu_k = \frac{x_k^\top s_k}{n} $; $ (x_{k+1},\lambda_{k+1},s_{k+1}) := (x_k,\lambda_k,s_k) + \alpha_k d_k $; $ k := k + 1 $.
         \end{enumerate}
   \item Retourner $ (x_k,\lambda_k,s_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}