Add the missing bits on quadratic problems solving.

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

diff --git a/présentation/Slides_ProjetOptimRO.tex b/présentation/Slides_ProjetOptimRO.tex
index 02182bfd3492d3f05b43beb6864fa9148d60fcf4..1c920ddfcc0c49ceff45ac95848cb95223ea6283 100644 (file)
--- a/présentation/Slides_ProjetOptimRO.tex
+++ b/présentation/Slides_ProjetOptimRO.tex
@@ -480,8 +480,59 @@ $}}
 \subsection{Optimisation quadratique sous contraintes linéaires}
 
 %%%%% SLIDE 16
-\begin{frame}{}
- \begin{block}{ALGORITHME OPTIMAL}
+\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}