\begin{proof}
Elle repose sur le lemme de Farkas \cite{FEA,RON}.
\end{proof}
-Il est à noter que une condition d'égalité peut se répresenter par deux conditions d'inégalité : $ \forall x \in \mathbb{R}^n \ \forall i \in \{ 1,\ldots,q \} \ h_i(x) = 0 \iff h_i(x) \leq 0 \land h_i(x) \geq 0 $ \cite{FEA}, ce qui peut permettre de réécrire le problème $ \mathcal{P} $ en éliminant les contraintes d'égalités et change la forme des conditions \textit{KKT} à vérifier mais rajoute $ 2q $ conditions d'inégalités et donc $ 2q $ multiplicateurs de Kuhn-Tucker.
+Il est à noter que une condition d'égalité peut se répresenter par deux conditions d'inégalité : $ \forall x \in \mathbb{R}^n \ \forall i \in \{ 1,\ldots,q \} \ h_i(x) = 0 \iff h_i(x) \leq 0 \land h_i(x) \geq 0 $ \cite{FEA}, ce qui peut permettre de réécrire le problème $ \mathcal{P} $ en éliminant les contraintes d'égalités et change la forme des conditions \textit{KKT} à vérifier mais rajoute $ 2q $ conditions d'inégalités et donc $ 2q $ multiplicateurs de Kuhn-Tucker.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Un vecteur $ d \in \mathbb{R}^n $ est une direction de descente pour $ J $ à partir d’un point $ x_0 \in \mathbb{R}^n $ si $ t \longmapsto f(x_0 + td) $ est strictement décroissante en $ t = 0 $, c’est-à-dire :
$$ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) $$
-Il est donc important d’analyser le comportement de la fonction $ J $ dans certaines direc-
-tions.
+Il est donc important d’analyser le comportement de la fonction $ J $ dans certaines directions.
\begin{Prop}
Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $.
\newline
\begin{proof}
Elle s'effectue en utilisant le développement de Taylor-Young de l’application $ t \longmapsto f(x_0 + td) $ à l’ordre 1.
\end{proof}
-Cette dernière inégalité garantit une décroissance minimum de la fonction $ J $ dans la
-direction $ d $ et peut se traduire par : la décroissance de la fonction $ J $, en effectuant un pas de longueur $ t $ dans la direction $ d $ , est au moins égale à la longueur du pas multipliée par une fraction de la pente. Le schéma général d’un algorithme de descente est alors le suivant :
+Cette dernière inégalité garantit une décroissance minimum de la fonction $ J $ dans la direction $ d $ et peut se traduire par : la décroissance de la fonction $ J $, en effectuant un pas de longueur $ t $ dans la direction $ d $, est au moins égale à la longueur du pas multipliée par une fraction de la pente. Le schéma général d’un algorithme de descente est alors le suivant :
\hrulefill
\newline
\newline
\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 de la solution du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
+\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
\begin{enumerate}
- \item $ k := 0 $
+ \item $ k := 0 $.
\item Tant que "test d’arrêt" non satisfait,
\begin{enumerate}
\item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
\subsection{Choix de la direction de descente}
-Une fois la théorie bien maîtrisée, calculer une direction de descente est relativement
-simple. Dans le cas différentiable, il existe deux grandes stratégies de choix de direction de
-descente :
+Une fois la théorie bien maîtrisée, calculer une direction de descente est relativement simple. Dans le cas différentiable, il existe deux grandes stratégies de choix de direction de descente :
\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}.
Soit $ x^\ast $ un minimum local de l'objectif $ J $ à optimiser. Supposons que l’on choisisse comme test d’arrêt dans l’algorithme de descente modèle, le critère idéal : "$ x_k = x^\ast $". Dans un monde idéal (i.e. en supposant tous les calculs exacts et la capacité de calcul illimitée), soit l’algorithme s’arrête après un nombre fini d’itérations, soit il construit (théoriquement) une suite infinie $ x_0,x_1,\ldots,x_k,\ldots $ de points de $ \mathbb{R}^n $ qui converge vers $ x^\ast $.
\newline
-En pratique, un test d’arrêt devra être choisi pour garantir que l’algorithme s’arrête
-toujours après un nombre fini d’itérations et que le dernier point calculé soit suffisamment
-proche de $ x^\ast $.
+En pratique, un test d’arrêt devra être choisi pour garantir que l’algorithme s’arrête toujours après un nombre fini d’itérations et que le dernier point calculé soit suffisamment proche de $ x^\ast $.
-Soit $ \varepsilon \in \mathbb{R}_{+}^{*} $ la précision demandée. Plusieurs critères sont à notre disposition : tout d’abord (et c’est le plus naturel), un critère d’optimalité basé sur les conditions nécessaires d’optimalité du premier ordre : en optimisation différentiable
-sans contrainte, on testera si
+Soit $ \varepsilon \in \mathbb{R}_{+}^{*} $ la précision demandée. Plusieurs critères sont à notre disposition : tout d’abord (et c’est le plus naturel), un critère d’optimalité basé sur les conditions nécessaires d’optimalité du premier ordre : en optimisation différentiable sans contrainte, on testera si
$$ \norme{\nabla J(x_k)} < \varepsilon, $$
auquel cas l’algorithme s’arrête et fournit l’itéré courant $ x_k $ comme solution.
-En pratique, le test d’optimalité n’est pas toujours satisfait et on devra faire appel à
-d’autres critères fondés sur l’expérience du numérique :
+En pratique, le test d’optimalité n’est pas toujours satisfait et on devra faire appel à d’autres critères fondés sur l’expérience du numérique :
\begin{itemize}
\item Stagnation de la solution : $ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $.
\item Stagnation de la valeur courante : $ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $.
\newline
Soit $ x_0 \in \mathbb{R}^n $ un point non critique et $ d $ une direction de descente de $ J $ en $ x_0 $. Nous cherchons à calculer un pas $ s > 0 $ de sorte que :
$$ J(x_0 + sd) < J(x_0). $$
-Le choix de ce pas répond généralement à deux objectifs souvent contradictoires : trouver
-le meilleur pas possible et effectuer le moins de calculs possibles. Ces deux objectifs ont
-donné naissance à deux grandes familles : les algorithmes à pas fixe et ceux à pas optimal.
+Le choix de ce pas répond généralement à deux objectifs souvent contradictoires : trouver le meilleur pas possible et effectuer le moins de calculs possibles. Ces deux objectifs ont donné naissance à deux grandes familles : les algorithmes à pas fixe et ceux à pas optimal.
\hrulefill
\newline
\hrulefill
\newline
Illustrées par les méthodes de descente de gradient, aucune de ces deux stratégies ne
-s’est révélée réellement convaincante : si la première peut être “risquée” du point de vue de
-la convergence, la seconde est souvent loin d’être triviale à mettre en oeuvre (sauf dans le
-cas quadratique) et généralement inutilement coûteuse : en effet, à quoi bon calculer très
-précisément un pas optimal dans une direction qui n’est peut-être pas la bonne ? (comme
-c’est par exemple le cas pour la méthode de plus profonde descente). Les recherches
-linéaires modernes reposent sur l’idée qu’un pas de descente acceptable est un pas qui fait
-“suffisamment” décroître la fonction objectif. Reste alors à définir les pas qui sont
-acceptables et ceux qui ne le sont pas.
+s’est révélée réellement convaincante : si la première peut être “risquée” du point de vue de la convergence, la seconde est souvent loin d’être triviale à mettre en oeuvre (sauf dans le cas quadratique) et généralement inutilement coûteuse : en effet, à quoi bon calculer très précisément un pas optimal dans une direction qui n’est peut-être pas la bonne ? (comme c’est par exemple le cas pour la méthode de plus profonde descente). Les recherches linéaires modernes reposent sur l’idée qu’un pas de descente acceptable est un pas qui fait “suffisamment” décroître la fonction objectif. Reste alors à définir les pas qui sont acceptables et ceux qui ne le sont pas.
\begin{Def}
On appelle $ \varphi : s \in \mathbb{R} \longmapsto J(x + sd)$ la fonction mérite associée à $ J $ en $ x $.
\end{Def}
\subsubsection{Principe de démonstration de convergence}
-Une technique classique en optimisation pour obtenir des résultats de convergence glo-
-bale consiste à montrer que l’algorithme de descente considéré vérifie une inégalité du
-type :
+Une technique classique en optimisation pour obtenir des résultats de convergence globale consiste à montrer que l’algorithme de descente considéré vérifie une inégalité du type :
$$ J(x_k) - J(x_{k+1}) \geq c\norme{\nabla J(x_k)}^2, $$
-où $ c $ est un constante réelle.
+où $ c $ est une constante réelle.
\newline
En sommant ces inégalités pour $ k $ variant de $ 0 $ à $ N - 1 $, on obtient :
$$ \forall N \in \mathbb{N} \ J(x_0) - J(x_N) \geq c \sum_{i=0}^{N-1}\norme{\nabla J(x_i)}^2 $$
\section{Méthode Newtonienne}
-Les hypothèses sur $ \mathcal{P} $ de la section précédente restent les mêmes dans cette section. L’algorithme de Newton en optimisation est une application directe de l’algorithme de
-Newton pour la résolution d’équations du type : $ F(x) = 0 $. En optimisation sans contrainte,
-l’algorithme de Newton cherche les solutions de l’équation :
+Les hypothèses sur $ \mathcal{P} $ de la section précédente restent les mêmes dans cette section. L’algorithme de Newton en optimisation est une application directe de l’algorithme de Newton pour la résolution d’équations du type : $ F(x) = 0 $. En optimisation sans contrainte, l’algorithme de Newton cherche les solutions de l’équation :
$$ \nabla J(x) = 0, $$
autrement dit, les points critiques de la fonction $ J $ à minimiser.
\newline
$$ x_{k+1} = x_k - H[J](x_k)^{-1} \nabla J(x_k), $$
où $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ est appelée direction de Newton. La direction $ d_k $ est également 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 $$
-Autrement dit, $ d_k $ est le point de minimum global de l’approximation de second ordre de
-$ J $ au voisinage du point courant $ x_k $.
-A condition que la matrice $ H[J](x_k) $ soit définie positive à chaque itération, la méthode
-de Newton est bien une méthode de descente à pas fixe égal à $ 1 $.
+Autrement dit, $ d_k $ est le point de minimum global de l’approximation de second ordre de $ J $ au voisinage du point courant $ x_k $.
+A condition que la matrice $ H[J](x_k) $ soit définie positive à chaque itération, la méthode de Newton est bien une méthode de descente à pas fixe égal à $ 1 $.
\newline
Les propriétés remarquables de cet algorithme sont :
\hline
\end{tabular}
\newline
-La question que l’on se pose est donc : comment forcer la convergence globale de l’algorithme de Newton ? L’idée des méthodes de type Newton consiste à reprendre
-l’algorithme de Newton en remplaçant les itérations par :
+La question que l’on se pose est donc : comment forcer la convergence globale de l’algorithme de Newton ? L’idée des méthodes de type Newton consiste à reprendre l’algorithme de Newton en remplaçant les itérations par :
$$ x_{k+1} = x_k - s_k H_k^{-1} \nabla J(x_k), $$
où
\begin{itemize}
\section{Méthode PQS (ou SQP)}
Nous supposons les fonctions $ J,g,h $ à valeurs réelles et de classe $ \mathcal{C}^1 $.
-Trouver une solution d’un problème d’optimisation sous contraintes fonctionnelles consiste
-à déterminer un point optimal $ x^\ast $ et des multiplicateurs associés $ (\lambda^\ast,\mu^\ast) $. Deux grandes familles de méthodes peuvent être définies pour la résolution des problèmes d’optimisation sous contraintes : les méthodes primales et les méthodes duales. Les approches primales se concentrent sur la détermination du point $ x^\ast $, les multiplicateurs $ (\lambda,\mu) $ ne servant souvent qu’à vérifier l’optimalité de $ x^\ast $. Les méthodes duales quant à elles mettent l’accent sur la recherche d’un multiplicateur en travaillant sur un problème d’optimisation déduit du problème initial par \textit{dualité}.
+Trouver une solution d’un problème d’optimisation sous contraintes fonctionnelles consiste à déterminer un point optimal $ x^\ast $ et des multiplicateurs associés $ (\lambda^\ast,\mu^\ast) $. Deux grandes familles de méthodes peuvent être définies pour la résolution des problèmes d’optimisation sous contraintes : les méthodes primales et les méthodes duales. Les approches primales se concentrent sur la détermination du point $ x^\ast $, les multiplicateurs $ (\lambda,\mu) $ ne servant souvent qu’à vérifier l’optimalité de $ x^\ast $. Les méthodes duales quant à elles mettent l’accent sur la recherche d’un multiplicateur en travaillant sur un problème d’optimisation déduit du problème initial par \textit{dualité}.
\subsection{Algorithmes newtoniens}
-Les algorithmes newtoniens sont basés sur la linéarisation d’équations caractérisant les solutions que l’on cherche, fournies par les conditions d’optimalité d’ordre $ 1 $. Ces algorithmes sont \textit{primaux-duaux} dans le sens où ils génèrent à la fois une suite primale $ (x_k )_{k \in \mathbb{N}} $ convergeant vers une solution $ \overline{x} $ du problème considéré, et une suite duale $ (\lambda_k)_{k \in \mathbb{N}} $ de multiplicateurs convergeant vers un multiplicateur optimal $ \overline{\lambda} $ associé à $ \overline{x} $.
+Les algorithmes newtoniens sont basés sur la linéarisation d’équations caractérisant les solutions que l’on cherche, fournies par les conditions d’optimalité d’ordre $ 1 $. Ces algorithmes sont \textit{primaux-duaux} dans le sens où ils génèrent à la fois une suite primale $ (x_k )_{k \in \mathbb{N}} $ convergeant vers une solution $ \overline{x} $ du problème considéré, et une suite duale $ (\lambda_k)_{k \in \mathbb{N}} $ (resp. $ ((\lambda_k, \mu_k))_{k \in \mathbb{N}} $) de multiplicateurs convergeant vers un multiplicateur optimal $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu}) $) associé à $ \overline{x} $.
\subsection{Algorithme PQS}
h(x_k)
\end{pmatrix} $$
où $ D_h(x) $ désigne la matrice jacobienne de l’application $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ définie par :
-$$ D_h(x)^\top = [\nabla h_1(x)\ldots\nabla h_q(x)] $$
+$$ D_h(x)^\top = \begin{bmatrix} \nabla h_1(x)\ldots\nabla h_q(x) \end{bmatrix} $$
Posons : $ H_k = H_x[L](x_k,\lambda_k), \ d = x_{k+1} - x_k $ et $ \mu = \lambda_{k+1} $. L'itération s'écrit donc :
$$ \begin{pmatrix}
H_k & D_h(x_k)^\top \\
\end{array}
\right .
$$
-Or $ \nabla_x L(x_k,\lambda_k) = \nabla J(x_k) + \sum\limits_{i=1}^{q} \lambda_{k_i} \nabla h_i(x_k) $, d'où :
+Or $ \nabla_x L(x_k,\lambda_k) = \nabla J(x_k) + \sum\limits_{i=1}^{q} \lambda_{k_i} \nabla h_i(x_k) $, d'où :
$$
\left \{
\begin{array}{r c l}
\end{array}
\right .
$$
-On reconnait dans le système ci-dessus les conditions d’optimalité de Lagrange du
-problème quadratique suivant :
+On reconnait dans le système ci-dessus les conditions d’optimalité de Lagrange du problème quadratique suivant :
$$
\mathcal{PQ}_k \left \{
\begin{array}{l}
\newline
Comme son nom l’indique, la méthode PQS consiste à remplacer le problème initial par une suite de problèmes quadratiques sous contraintes linéaires plus faciles à résoudre. L’algorithme est le suivant :
+\hrulefill
+\newline
+ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ.
+\newline
+\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $, $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ différentiables, $ x_0 \in \mathbb{R}^n $ point initial arbitraire, $ \lambda_0 \in \mathbb{R}^q $ multiplicateur initial, $ \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)} > \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 \\
+ 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 le multiplicateur $ \lambda^{\prime} $ associé à la contrainte d’égalité.
+ \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ k := k + 1 $.
+ \end{enumerate}
+ \item Retourner $ x_k $.
+\end{enumerate}
+
+\hrulefill
+
\subsubsection{Contraintes d’inégalité}
+Intéressons nous maintenant aux problèmes avec contraintes d’égalité et d’inégalité :
+$$
+ \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ù $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $, $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables.
+\newline
+Selon le même principe qu’avec contraintes d’égalité seules, on linéarise les contraintes et on utilise une approximation quadratique du Lagrangien :
+$$ L(x,\lambda,\mu) = J(x) + \lambda^\top g(x) + \mu^\top h(x), \ \lambda \in \mathbb{R}_+^p \land \mu \in \mathbb{R}^q $$
+
+\hrulefill
+\newline
+ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ.
+\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
+\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 = 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}
+
+\hrulefill
+\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.
+
\bibliographystyle{plain}
\bibliography{stdlib_sbphilo}
repositories / Projet_Recherche_Operationnelle.git / blobdiff