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