X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=pr%C3%A9sentation%2FSlides_ProjetOptimRO.tex;h=1c920ddfcc0c49ceff45ac95848cb95223ea6283;hb=075207e7e81486da2c3a7c8f8b827a820f858ae1;hp=dea680c3201f66db0911632423f01c7af902f2f9;hpb=09448b62fdf29dbdf5137bafb6120d36f2e97ff4;p=Projet_Recherche_Operationnelle.git diff --git "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" index dea680c..1c920dd 100644 --- "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" +++ "b/pr\303\251sentation/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}