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 dea680c3201f66db0911632423f01c7af902f2f9..1c920ddfcc0c49ceff45ac95848cb95223ea6283 100644 (file)
--- a/présentation/Slides_ProjetOptimRO.tex
+++ b/présentation/Slides_ProjetOptimRO.tex
@@ -265,8 +265,8 @@ $}}
   \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 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}
@@ -406,7 +406,7 @@ $}}
  \begin{defin}
   Une méthode de descente est dite Newtonienne si
   $$ d_k = -H[J](x_k)^{-1} \nabla J(x_k). $$
-  Elles conduisent aux \textit{algorithmes Newtoniens}.
+  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 :
 
@@ -473,15 +473,66 @@ $}}
   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 $ est la valeur optimale de direction de descente.
+  $ \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}{}
- \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}