From 075207e7e81486da2c3a7c8f8b827a820f858ae1 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sun, 2 Dec 2018 22:25:05 +0100 Subject: [PATCH] Add the missing bits on quadratic problems solving. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- .../Slides_ProjetOptimRO.tex" | 55 +++++++- rapport/ProjetOptimRO.tex | 118 ++++++++++++++++-- 2 files changed, 159 insertions(+), 14 deletions(-) diff --git "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" index 02182bf..1c920dd 100644 --- "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" +++ "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" @@ -480,8 +480,59 @@ $}} \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} diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index 2791db0..7207b7b 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -577,13 +577,84 @@ $$ \right . $$ où $$ \mathcal{Q} \in \mathcal{M}_n(\mathbb{R}) \ symétrique, c \in \mathbb{R}^n, A \in \mathcal{M}_{n,p}(\mathbb{R}), b \in \mathbb{R}^p, A^\prime \in \mathcal{M}_{n,q}(\mathbb{R}), b^\prime \in \mathbb{R}^q $$ -Or -$$ A^{\prime^\top} x + b^\prime = 0 \iff A^{\prime^\top} x + b^\prime \leq 0 \land -A^{\prime^\top} x - b^\prime \leq 0 $$ -Donc le problème se ramène à : +% Or +% $$ A^{\prime^\top} x + b^\prime = 0 \iff A^{\prime^\top} x + b^\prime \leq 0 \land -A^{\prime^\top} x - b^\prime \leq 0 $$ +On peut ramener le problème à : +$$ + \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 + z = 0 \\ + A^{\prime^\top} x + b^\prime = 0 + \end{array} + \right . +$$ +où $$ z \in \mathbb{R}^p $$ +On peut donc ramener l'étude de ce type de problème à : +$$ + \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étrique, c \in \mathbb{R}^n, A \in \mathcal{M}_{n,p}(\mathbb{R}), b \in \mathbb{R}^p $$ +Conditions \textit{KKT} appliquées à $ \mathcal{PQ} $ : +$$ + \begin{array}{r c l} + \mathcal{Q} x + A \lambda^\ast & = & - c \\ + A^\top x & = & -b \\ + \end{array} +$$ +On obtient donc : +$$ \lambda^\ast = (A^\top \mathcal{Q} A)^{-1} A^\top \mathcal{Q} c $$ +En posant $ \mathcal{Q} = Id_{\mathbb{R}^n} $, on a une bonne évaluation de $ \lambda^\ast $ : +$$ \lambda^\ast = (A^\top A)^{-1} A^\top c $$ -\subsubsection{Algorithme 1} +\subsubsection{Méthode des points intérieurs} -\subsubsection{Algorithme 2} +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 $$ +\hrulefill +\newline +ALGORITHME DES POINTS INTÉRIEURS. +\newline +\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} + +\hrulefill +\newline +On note que c'est un algorithme de descente avec recherche d'un pas optimal. +La détermination de $ \sigma_{min} $ et $ \sigma_{max} $ se fait dans l'intervalle ouvert $ ]0, 1[ $. Il existe d'autres méthodes de résolution du problème $ \mathcal{PQ} $ mais celle-ci à l'avantage de passer à l'échelle et a des vitesses de convergence efficientes. La résolution du système linéaire d'équations peut être faite soit directement, soit en utilisant une méthode itérative de résolution de problèmes d'algèbre linéaire. \subsection{Algorithmes Newtoniens} @@ -608,9 +679,9 @@ Les conditions d’optimalité de Lagrange (ou \textit{KKT}) s’écrivent : $$ \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) = 0 \iff \nabla L(x,\lambda) = 0 $$ donc $ \mathcal{P} $ devient : $$ \begin{pmatrix} - \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) \\ - h(x) - \end {pmatrix} = 0 $$ + \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) \\ + h(x) + \end{pmatrix} = 0 $$ Pour résoudre ce système d’équations, utilisons la méthode de Newton dont une itération s’écrit ici : $$ H[L](x_k,\lambda_k)\begin{pmatrix} x_{k+1} - x_k \\ @@ -726,7 +797,17 @@ et à l'ordre 1 pour les contraintes : $$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$ $$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$ En posant $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $, on obtient le sous problème quadratique $ \mathcal{PQ}_k $ : - +$$ + \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(x_k) + \nabla g(x_k)^\top d \leq 0 \\ + h(x_k) + \nabla h(x_k)^\top d = 0 + \end{array} + \right . +$$ +Comme pour la cas précédent, on résoud alors le sous problème quadratique $ \mathcal{PQ}_k $ qui est plus simple avec une méthode vue plus haut en posant $ \mathcal{Q} = H_k = H[L](x_k,\lambda_k,\mu_k) $. +\newpage \hrulefill \newline ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ. @@ -758,7 +839,7 @@ ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ. \newline Afin que le sous-programme quadratique $ \mathcal{PQ}_k $ admette une unique solution, la plupart des implémentations actuelles de PQS utilisent une approximation du hessien $ H_k $ du Lagrangien qui soit définie positive, en particulier celle fournie par les techniques quasi-newtonienne (BFGS) par exemple. \newline -Etant une méthode newtonienne, l’algorithme PQS converge localement quadratiquement pourvu que les points initiaux $ (x_0,\lambda_0 ) $ (resp. $ (x_0,\lambda_0,\mu_0) $) soient dans un voisinage d’un point stationnaire $ \overline{x} $ et de ses multiplicateurs associés $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu}) $). Bien entendu, il est possible de globaliser l’algorithme en ajoutant une étape de recherche linéaire. +Étant une méthode newtonienne, l’algorithme PQS converge localement quadratiquement pourvu que les points initiaux $ (x_0,\lambda_0 ) $ (resp. $ (x_0,\lambda_0,\mu_0) $) soient dans un voisinage d’un point stationnaire $ \overline{x} $ et de ses multiplicateurs associés $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu}) $). Bien entendu, il est possible de globaliser l’algorithme en ajoutant une étape de recherche linéaire. \subsection{Stratégie d'approximation de la hessienne} @@ -776,8 +857,21 @@ Dans les deux cas, les équations de quasi-Newton forment un système sous-déte \newline Une stratégie commune est de calculer $ (x_{k+1},\lambda_{k+1},\mu_{k+1}) $ pour une matrice $ H_k $ donnée et faire une mise à jour de $ H_k $ de rang 1 ou 2 : $$ H_{k+1} = H_k + U_k $$ -% \subsubsection{Mises à jour DFP et BFGS} -Les méthodes de mises à jour DFP et BFGS suivent par exemple cette stratégie. +Les méthodes de mises à jour PSB et BFGS suivent par exemple cette stratégie. + +\subsubsection{Mises à jour PSB} + +$$ H_{k+1} = H_k + \frac{1}{d^\top d} ((y - H_k d)d^\top + d(y - H_k d)^\top) - \frac{(y - H_k d)^\top d}{(d^\top d)^2}d^\top d $$ +où +$$ d = x_{k+1} - x_k $$ +$$ y = \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) $$ + +\subsubsection{Mises à jour BFGS} + +$$ H_{k+1} = H_k + \frac{y y^\top}{y^\top d} - \frac{H_k d d^\top H_k}{d^\top H_k d}$$ +où +$$ d = x_{k+1} - x_k $$ +$$ y = \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) $$ \subsection{Exemple d'utilisation de PQS} -- 2.34.1