Correction dans la structure de la trace d'execution.

Elle a besoin de plus de travail pour ressembler à une trace.

Fix a mismerge.
Amend the slides with some of the comments.

Signed-off-by: Jérôme Benoit <jerome.benoit@piment-noir.org>

diff --git a/présentation/Slides_ProjetOptimRO.tex b/présentation/Slides_ProjetOptimRO.tex
index eade499f142b328ca34df222514b268e7a9192d9..5d73666c4f37079f9731908a2c3fdd7cf7caf817 100644 (file)
--- a/présentation/Slides_ProjetOptimRO.tex
+++ b/présentation/Slides_ProjetOptimRO.tex
@@ -205,12 +205,24 @@ $}}
    \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} $$
+  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}
- \centerline{à l'aide de méthodes numériques itératives.}
 \end{frame}
 
-\section{Méthode de descente}
+\subsection{Prérequis mathématiques}
+
+\section{La méthode PQS est une méthode de descente}
 
 \subsection{Définition}
 
@@ -218,10 +230,22 @@ $}}
 \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 :
-  \centerline{$ x_0 \in \mathbb{R}^n $ arbitraire,}
-  \centerline{$ x_{k+1} = x_k + s_kd_k $ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $}
-  et
+  \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}
 

diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex
index 872306379b8b8bba624aced3a1e28f0023c273c0..85ec36eaedc21ee8a665d2c8ac7a828d83df3cb4 100644 (file)
--- a/rapport/ProjetOptimRO.tex
+++ b/rapport/ProjetOptimRO.tex
@@ -722,7 +722,7 @@ En posant $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $, on obtient le
 
 \hrulefill
 \newline
-ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ.
+ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.
 \newline
 \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
@@ -736,7 +736,7 @@ ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ.
                \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\}                 \\
+                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 .
@@ -783,7 +783,7 @@ $$
  \end{array}
  \right .
 $$
-où $$ (r,r_1,r_2) \in \mathbb{R}_+^3. $$
+où $$ (r,r_1,r_2) \in \mathbb{R}_+^{*^3} \land r < r_1 \land r < r_2. $$
 \textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $ la précision, $ (x_0,y_0,z_0) = $ point initial et $ (\lambda_{0_1},\lambda_{0_2}) = $ multiplicateur initial.
 \newline
 Le Lagrangien $ L $ de $ \mathcal{P} $ : $$ L((x,y,z),(\lambda_1,\lambda_2)) = x^2 + y^2 + z^2 -r^2 + \lambda_1(x^2 + y^2 - r_1^2) + \lambda_2(x^2 + z^2 -r_2^2). $$
@@ -810,98 +810,83 @@ La matrice hessienne de $ J $ : $$ H[J](x,y,z) =
  \end{pmatrix} = 2Id_{\mathbb{R}^3} $$
 On en déduit que $ H[J](x,y,z) $ est inversible et que $ H[J](x,y,z)^{-1} = \frac{1}{2}Id_{\mathbb{R}^3} $.
 
-\hrulefill
-
-\subsection{Trace d'éxécution de PQS}
+\subsection{Trace d'éxécution de l'algorithme PQS}
 
-Utilisons le problème $ \mathcal{P} $ précédent :
-
-$$
- \mathcal{P} \left \{
- \begin{array}{l}
-  \displaystyle\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2       \\
-  g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 \\
- \end{array}
- \right .
-$$
-où $$ (r,r_1,r_2) \in \mathbb{R}_+^3. $$
-\textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $, $ (x_0,y_0,z_0) = (80, 20 ,60)$  et $(\lambda_{0_1},\lambda_{0_2}) = (1 , 1)$, les rayons : $r= 40$  et $r1 = r2 = 10$.
+En utilisant le problème $ \mathcal{P} $ précédent :
 \newline
-Le Lagrangien $ L $ de $ \mathcal{P} $ : $$ L((x,y,z),(\lambda_1,\lambda_2)) = x^2 + y^2 + z^2 -r^2 + \lambda_1(x^2 + y^2 - r_1^2) + \lambda_2(x^2 + z^2 -r_2^2). $$
+\textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $, $ (x_0,y_0,z_0) = (80, 20, 60)$  et $(\lambda_{0_1},\lambda_{0_2}) = (1, 1)$, les rayons : $r = 40$ et $r_1 = r_2 = 10$.
+\newline
+Calcul du Lagrangien $ L $ de $ \mathcal{P} $ en $ (x_0,y_0,z_0)$ :
+\newline
+$ L((80,20,60),(1,1)) = 80^2 + 20^2 + 60^2 -60^2 + 1 * (80^2 +20y^2 - 30^2) + \lambda_2(80^2 + 60^2 -30^2), $
 \newline
-Le Lagrangien $ L $ de $ \mathcal{P} $ avec les valeurs :
- $ L((80,20,60),(1,1)) = 80^2 + 20^2 + 60^2 -60^2 + 1 * (80^2 +20y^2 - 30^2) + \lambda_2(80^2 + 60^2 -30^2). $
- $ L((80,20,60),(1,1)) = 6400 + 400 + 3600 - 3600 + (6400 + 400 - 900) + (6400 + 3600 -900). $
- $ L((80,20,60),(1,1)) = 21800. $
+$ L((80,20,60),(1,1)) = 6400 + 400 + 3600 - 3600 + (6400 + 400 - 900) + (6400 + 3600 -900), $
+\newline
+$ L((80,20,60),(1,1)) = 21800. $
 
- \begin{algorithm}
- \caption {PQS du problème $ \mathcal{P} $}
+\begin{algorithm}
+ \caption {Algorithme PQS pour $ \mathcal{P} $}
  \begin{algorithmic}
- \REQUIRE $g(x,y,z)\leq 0$, $(x_0,y_0,z_0) = (80, 20 ,60)$
- \ENSURE $\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2$ and \newline $g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 $
- \STATE \textbf{Data :}
- \STATE $k \leftarrow 0$
- \STATE $x_k \leftarrow 80$
- \STATE $y_k \leftarrow 20$
- \STATE $z_k \leftarrow 60$
- \STATE $x_a \leftarrow 30$
- \STATE $y_a \leftarrow 10$
- \STATE $z_a \leftarrow 40$
- \STATE $r \leftarrow 40$
- \STATE $r_1 \leftarrow 10$
- \STATE $r_2 \leftarrow 10$
- \STATE $\varepsilon \leftarrow 0.01$
- \STATE $\lambda_1 = \lambda_2 = 1$
- \STATE $ H[J](x,y,z)^{-1}\leftarrow  \begin{pmatrix}
-  0.5 & 0 & 0 \\
-  0 & 0.5 & 0 \\
-  0 & 0 & 0.5 \\ \end{pmatrix} $
-\newline
-
- \STATE{//Calcule du gradient de $ J $ :}
- \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$  \hfill $  // résultat : (160,40,120) $
-\newline
- \STATE {//calcule des deux sous partie de du gradient de $ g $: }
- \STATE $ // \nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
- \STATE $ \nabla g_1(x_a,y_a,z_a) = ((2x_a,2y_a,0)$  \hfill $ //résultat : (60, 20, 0)$
- \STATE $ \nabla g_2(x_a,y_a,z_a) = (2x_a,0,2z_a))$  \hfill $ //résultat : (60, 0, 80)$
-\newline
- \WHILE{$ (\norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $ or k $ < 10)$}
-
- \STATE { //première itération :}
-
-\STATE {//Calcule du gradient de $ L $ : }
-\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (280, 60, 200)$
- \STATE $  \nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = (x_L , y_L, z_L) $
-\newline
- \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
- \STATE $ d_k = -H[J](x,y,z)^{-1}*\nabla J(x,y,z)$ \hfill $ //résultat : (-(80,20,60))$
- \newline
- \STATE {//Calcul nouvelles valeurs des coordonnées}
- \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0,0,0)$
- \newline
- \STATE {//Incrémentation de k}
- \STATE $ k \leftarrow k+1$
+  \REQUIRE $\varepsilon = 0.01$, $g(x,y,z)\leq 0$, $(x_0,y_0,z_0) = (80, 20 ,60)$, $(\lambda_{0_1},\lambda_{0_2}) = (1, 1)$, $r = 40$ et $r_1 = r_2 = 10$.
+  \ENSURE $\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2$ and \newline
+  $g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 $
+
+  \STATE \textbf{Data :}
+  \STATE $k \leftarrow 0$
+  \STATE $(x_k,y_k,z_k) \leftarrow (80,20,60)$
+  \STATE $ H[J](x,y,z)^{-1} \leftarrow
+   \begin{pmatrix}
+    0.5 & 0   & 0   \\
+    0   & 0.5 & 0   \\
+    0   & 0   & 0.5 \\
+   \end{pmatrix} $
+
+  \WHILE{($\norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon$ or $k < 10$)}
+
+  \STATE {//Première itération :}
+
+  \STATE{//Calcul du gradient de $ J $ :}
+  \STATE $\nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (160,40,120) $
+
+  \STATE {//Calcul des deux composantes du gradient de $ g $ :}
+  \STATE $\nabla g_1(x_k,y_k,z_k) = ((2x_k,2y_k,0)$ \hfill $ //résultat : (60, 20, 0)$
+  \STATE $\nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k))$ \hfill $ //résultat : (60, 0, 80)$
+  \STATE $\nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
+
+  \STATE {//Calcul du gradient de $ L $ :}
+  \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k) $ \hfill $ //résultat : (280, 60, 200)$
+
+  \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
+  \STATE $ d_k = -H[J](x,y,z)^{-1}*\nabla J(x,y,z)$ \hfill $ //résultat : (-(80,20,60))$
+
+  \STATE {//Calcul des nouvelles valeurs des coordonnées :}
+  \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0,0,0)$
+
+  \STATE {//Deuxième itération :}
+
+  \STATE {//Incrémentation de k}
+  \STATE $ k \leftarrow k+1$ \hfill $ //résultat : 1$
+
+  \STATE{//Calcul du gradient de $ J $ :}
+  \STATE $\nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (0,0,0) $
 
+  \STATE {//Calcul des deux composantes du gradient de $ g $ :}
+  \STATE $\nabla g_1(x_k,y_k,z_k) = ((2x_k,2y_k,0)$ \hfill $ //résultat : (60, 20, 0)$
+  \STATE $\nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k))$ \hfill $ //résultat : (60, 0, 80)$
+  \STATE $\nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
 
- \STATE {//Deuxième itération :}
- \STATE{//Calcule du gradient de $ J $ :}
- \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$  \hfill $  // résultat : (0,0,0) $
+  \STATE {//Calcul du gradient de $ L $ :}
+  \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $ //résultat : (160, 20, 30)$
 
-\STATE {//Calcule du gradient de $ L $ : }
-\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (160, 20, 30)$
- \STATE $ (\varepsilon ,\varepsilon ,\varepsilon ) = \nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) $
+  \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
+  \STATE $ d_k = -H[J](x_k,y_k,z_k)^{-1} * \nabla J(x,y,z)$ \hfill $ //résultat : (-(0,0,0))$
 
- \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
- \STATE $ d_k = -H[J](x,y,z)^{-1}*\nabla J(x,y,z)$ \hfill $ //résultat : (-(0,0,0))$
- \STATE {//Calcul nouvelles valeurs des coordonnées}
- \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0,0,0)$
- \STATE {//Incrémentation de k}
-\STATE $ k \leftarrow k+1$\hfill $ //k = 1$
+  \STATE {//Calcul des nouvelles valeurs des coordonnées :}
+  \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0,0,0)$
 
- \ENDWHILE
+  \ENDWHILE
 
-\end{algorithmic}
+ \end{algorithmic}
 \end{algorithm}
 
 

diff --git a/rapport/stdlib_sbphilo.bib b/rapport/stdlib_sbphilo.bib
index 6ffdc4880cf3b42f282d6824941e6bdec9f54c7a..dfd3a3404085589defe074cbef634ade08b850b4 100644 (file)
--- a/rapport/stdlib_sbphilo.bib
+++ b/rapport/stdlib_sbphilo.bib
@@ -32,7 +32,7 @@ journal="",
 volume=" ",
 number="",
 pages="",
-publisher="Ecole Normale Supérieure de Lyon",
+publisher="École Normale Supérieure de Lyon",
 year="2005",
 }