From: Jérôme Benoit Date: Fri, 9 Nov 2018 19:19:43 +0000 (+0100) Subject: Correction dans la structure de la trace d'execution. X-Git-Url: https://git.piment-noir.org/?p=Projet_Recherche_Operationnelle.git;a=commitdiff_plain;h=e173772d73eae2aa041835260794b78b627f94a1 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 --- diff --git "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" index eade499..5d73666 100644 --- "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" +++ "b/pr\303\251sentation/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 8723063..85ec36e 100644 --- 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 6ffdc48..dfd3a34 100644 --- 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", }