X-Git-Url: https://git.piment-noir.org/?p=Projet_Recherche_Operationnelle.git;a=blobdiff_plain;f=pr%C3%A9sentation%2FSlides_ProjetOptimRO.tex;fp=pr%C3%A9sentation%2FSlides_ProjetOptimRO.tex;h=dea680c3201f66db0911632423f01c7af902f2f9;hp=5d73666c4f37079f9731908a2c3fdd7cf7caf817;hb=09448b62fdf29dbdf5137bafb6120d36f2e97ff4;hpb=e173772d73eae2aa041835260794b78b627f94a1 diff --git "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" index 5d73666..dea680c 100644 --- "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" +++ "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" @@ -217,16 +217,99 @@ $}} $ 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. + \newline + On définit $ \mathcal{C} $ l'ensemble des contraintes par : + $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$ \end{defin} \end{frame} \subsection{Prérequis mathématiques} -\section{La méthode PQS est une méthode de descente} +%%%%% SLIDE 2 +\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} -\subsection{Définition} +%%%%% 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 2 +%%%%% 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 \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 : @@ -249,11 +332,21 @@ $}} \end{defin} \end{frame} -\subsection{Algorithme} +%%%%% SLIDE 7 +\begin{frame}{Caractérisation d'une direction de descente} + \begin{proposition} + Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $. + \newline + d est un vecteur de descente de $ J $ en $ x_0 \in \mathbb{R}^n $ ssi : + $$ \nabla J(x_0)^\top d < 0 $$ + De plus + $$ \forall \beta < 1 \in \mathbb{R}_{+} \ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) + t\beta \nabla J(x_0)^\top d < J(x_0) $$ + \end{proposition} +\end{frame} -%%%%% SLIDE 3 -\begin{frame}{Algorithme de descente modèle} - \begin{block}{ALGORITHME DE DESCENTE MODÈLE.} +%%%%% SLIDE 8 +\begin{frame}{Algorithme de descente générique} + \begin{block}{ALGORITHME DE DESCENTE GÉNÉRIQUE.} \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire. \newline \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $. @@ -270,33 +363,22 @@ $}} \end{block} \end{frame} -\subsubsection{Direction de descente} - -%%%%% SLIDE 4 -\begin{frame}{Direction de descente} - Deux grandes stratégies : - \begin{itemize} - \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}. - \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}. - \end{itemize} -\end{frame} - -\subsubsection{Critère d'arrêt} - -%%%%% SLIDE 5 +%%%%% SLIDE 9 \begin{frame}{Critère d'arrêt} - \centerline{Critère d’arrêt =} - \begin{tabular}{c} - Test d’optimalité satisfait($\norme{\nabla J(x_k)} < \varepsilon$) \\ - OU (Stagnation de la valeur courante($ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $) \\ - ET Stagnation de la solution($ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $)) \\ - OU Nombre d’itérations maximum autorisé dépassé($ k < IterMax $) - \end{tabular} + \begin{block}{} + \begin{center} + Critère d’arrêt $$ \parallel $$ + \end{center} + \begin{tabular}{l l} + & Test d’optimalité satisfait ($\norme{\nabla J(x_k)} < \varepsilon$) \\ + OU & (Stagnation de la valeur courante ($ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $) \\ + & ET Stagnation de la solution ($ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $)) \\ + OU & Nombre d’itérations maximum autorisé dépassé ($ k < IterMax $) + \end{tabular} + \end{block} \end{frame} -\subsubsection{Recherche linéaire} - -%%%%% SLIDE 6 +%%%%% SLIDE 10 \begin{frame}{Recherche linéaire} \begin{block}{RECHERCHE LINÉAIRE : PAS FIXE.} $ s_k = s_{k-1} $ @@ -306,18 +388,34 @@ $}} \end{block} \end{frame} -\subsubsection{Méthode Newtonienne} +%%%%% SLIDE 11 +\begin{frame}{Application à l'algorithme PQS} + \begin{block}{Cas de l'algorithme PQS} + \begin{enumerate} + \item le critère d'arrêt est $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $; + \item le pas $ s_k $ est fixe tel que $ \forall k \in \mathbb{N} \ s_k = 1 $. Il est possible d'ajouter une étape de recherche linéaire d'un pas optimal; + \item la direction de descente $ d_k $ est une approximation de $ -H[J](x_k)^{-1} \nabla J(x_k) $. + \end{enumerate} + \end{block} +\end{frame} + +\subsection{La méthode PQS est une méthode Newtonienne} -%%%%% SLIDE 7 +%%%%% SLIDE 12 \begin{frame}{Méthode Newtonienne I} - Choix de la direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ solution unique du problème : + \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}. + \end{defin} + La direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ est l'unique solution du problème : $$ \underset{d \in \mathbb{R}^n}{\mathrm{argmin}} \ J(x_k) + \langle \nabla J(x_k),d \rangle + \frac{1}{2}\langle H[J](x_k)d,d \rangle $$ $ \iff d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $. \end{frame} -%%%%% SLIDE 8 +%%%%% SLIDE 13 \begin{frame}{Méthode Newtonienne II} \begin{tabular}{|p{15em}|p{15em}|} \hline @@ -329,38 +427,25 @@ $}} \hline & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $. \\ \hline - & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la hessienne est singulière. \\ + & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la hessienne est singulière. \\ \hline & pas de distinction entre minima, maxima et points stationnaires. \\ \hline \end{tabular} \end{frame} -\section{Méthode PQS} +\subsection{Principe général de la méthode PQS} -\subsection{Principe général} - -%%%%% SLIDE 9 +%%%%% SLIDE 14 \begin{frame}{Principe général I} - \begin{defin} - Résoudre le problème $ \mathcal{P} $ : - $$ - \mathcal{P} \left \{ - \begin{array}{l} - \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\ - g(x) \leq 0 \\ - h(x) = 0 - \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}\ de\ classe\ \mathcal{C}^2. $$ - \end{defin} -\end{frame} - -%%%%% SLIDE 10 -\begin{frame}{Principe général II} + Principe de résolution du problème $ \mathcal{P} $ en utilisant la méthode PQS : \begin{enumerate} - \item Conditions nécessaires et suffisantes d'existence et d'unicité d'une solution (\textit{KKT}, $ H[J] $ définie positive et convexité de $ \mathcal{P} $). + \item Établir les conditions nécessaires et suffisantes d'existence et d'unicité d'une solution : + \begin{enumerate} + \item Conditions suffisantes \textit{KKT}; + \item Conditions nécessaires $ H[J] $ définie positive; + \item Condition(s) de convexité de $ \mathcal{P} $. + \end{enumerate} \item Approximation quadratique du Lagrangien $ L $ de $ \mathcal{P} $ par Taylor-Young à l'ordre 2 en $ x_k $: $$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) $$ $$ + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$ @@ -372,8 +457,8 @@ $}} \end{enumerate} \end{frame} -%%%%% SLIDE 11 -\begin{frame}{Principe général III} +%%%%% SLIDE 15 +\begin{frame}{Principe général II} \begin{block}{} Résoudre le sous-problème quadratique $ \mathcal{PQ}_k $ avec contraintes linéaires : $$ @@ -387,36 +472,16 @@ $}} $$ où $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $ symétrique (Schwarz). \end{block} - \centerline{$ \implies $ La solution $ d_k $ est la valeur optimale de direction de descente.} + \begin{center} + $ \implies $ La solution $ d_k $ est la valeur optimale de direction de descente. + \end{center} \end{frame} -\subsection{Algorithme PQS} +\subsection{Optimisation quadratique sous contraintes linéaires} -%%%%% SLIDE 12 -\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} +%%%%% SLIDE 16 +\begin{frame}{} + \begin{block}{ALGORITHME OPTIMAL} \end{block} \end{frame}