\usepackage{fancyhdr}
\usepackage{tocbibind}
\usepackage{lmodern}
+\usepackage{enumitem}
%%%%%Marges & en-t\^etes
\newtheorem{Cor}[Th]{Corollaire}
\newtheorem{Rmq}{Remarque}
-\newcommand{\norme}[1]{\left\Vert #1\right\Vert}
+\newcommand{\norme}[1]{\left\Vert #1 \right\Vert}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{tabular}{c}
\hline
- ~ \\
- \LARGE\textbf {Programmation Séquentielle Quadratique ou PQS} \\
- \LARGE\textbf {en} \\
- \LARGE\textbf {Optimisation non linéraire sous contraintes} \\
- ~ \\
+ ~ \\
+ \LARGE\textbf {Programmation Quadratique Séquentielle ou PQS} \\
+ \LARGE\textbf {en} \\
+ \LARGE\textbf {Optimisation non linéraire sous contraintes} \\
+ ~ \\
\hline
\end{tabular}
La problèmatique $ \mathcal{P} $ se définit par :
$$
\mathcal{P} \left \{
- \begin{array}{r}
+ \begin{array}{l}
\displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
g(x) \leq 0 \\
h(x) = 0
Définissons quelques notions supplémentaires de base nécessaires à la suite :
\begin{Def}
-Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
-\newline
-On dit que $ x^\ast $ est \textbf{intérieur} à $ A $ si $ A $ est un voisinage de $ x^\ast $. On appelle intérieur de $ A $ l'ensemble des points intérieurs à $ A $ et on le note $ \mathring{A} $.
+ 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{Def}
\begin{Def}
-Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
-\newline
-On dit que $ x^\ast $ est \textbf{adhérent} à $ A $ si et seulement si $ \forall V \in \mathcal{V}(x^\ast) \ A \cap V \neq \emptyset $. On appelle adhérence de $ A $ l'ensemble des points adhérents à $ A $ et on le note $ \overline{A} $.
+ Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
+ \newline
+ On dit que $ x^\ast $ est \textbf{intérieur} à $ A $ si $ A $ est un voisinage de $ x^\ast $. On appelle intérieur de $ A $ l'ensemble des points intérieurs à $ A $ et on le note $ \mathring{A} $.
\end{Def}
+\begin{Rmq}
+ $ A \subset \mathbb{R}^n $ est un ouvert $ \iff A = \mathring{A} $.
+\end{Rmq}
\begin{Def}
-Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $.
-\newline
-On dit que $ f $ est continue en $ x^\ast $ si
-$$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+}^{*} \ \forall x \in \mathbb{R}^n \ \norme{x - x^\ast} \leq \alpha \implies |f(x) - f(x^\ast)| \leq \varepsilon $$
+ Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
+ \newline
+ On dit que $ x^\ast $ est \textbf{adhérent} à $ A $ si et seulement si $ \forall V \in \mathcal{V}(x^\ast) \ A \cap V \neq \emptyset $. On appelle adhérence de $ A $ l'ensemble des points adhérents à $ A $ et on le note $ \overline{A} $.
+\end{Def}
+\begin{Rmq}
+ $ A \subset \mathbb{R}^n $ est un fermé $ \iff A = \overline{A} $.
+\end{Rmq}
+\begin{Def}
+ Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $.
+ \newline
+ On dit que $ f $ est continue en $ x^\ast $ si
+ $$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+}^{*} \ \forall x \in \mathbb{R}^n \ \norme{x - x^\ast} \leq \alpha \implies |f(x) - f(x^\ast)| \leq \varepsilon $$
\end{Def}
\begin{Def}
Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $.
\begin{Rmq}
$ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $
\end{Rmq}
+\begin{Def}
+ Soit $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ un fonction de classe $ \mathcal{C}^2 $.
+ On définit la matrice hessienne de $ f $ en $ x^\ast $ par :
+ $$ H[f](x^\ast) =
+ \begin{pmatrix}
+ \frac{\partial^2 f}{\partial x_1^2}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n}(x^\ast) \\
+ \vdots & & \vdots \\
+ \frac{\partial^2 f}{\partial x_n\partial x_1}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_n^2}(x^\ast)
+ \end{pmatrix} $$
+\end{Def}
+\begin{Prop}
+ \begin{enumerate}
+ \item $ H[f](x^\ast) $ est une matrice symétrique (Théorème de symétrie de Schwarz).
+ \item On a le développement de Taylor-Young à l'ordre 2 en $ x^\ast $ suivant :
+ $$ f(x^\ast + v) = f(x^\ast) + \langle \nabla f(x^\ast),v \rangle + \frac{1}{2} v^\top H[f](x^\ast) v + \varepsilon(v) $$
+ ou
+ $$ f(x^\ast + v) = f(x^\ast) + \langle \nabla f(x^\ast),v \rangle + \frac{1}{2} \langle H[f](x^\ast)v,v \rangle + \varepsilon(v) $$
+ avec $ \frac{|\varepsilon(v)|}{\norme{v}} \rightarrow 0 $ quand $ \norme{v} \rightarrow 0 $.
+ \end{enumerate}
+\end{Prop}
+\begin{proof}
+ Elle repose entièrement sur deux autres théorèmes dont les preuves sont connues et de la réécriture de formulation de résultat.
+\end{proof}
\subsection{Conditions d'existence d'un extremum}
On peut démontrer que $ \mathcal{C }$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues.
On peut en déduire que si $ J $ est continue, $ \mathcal{C }$ est un ensemble fermé et borné de $ \mathbb{R}^n $.
\begin{Th}[Théorème de Weierstrass]
-Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue.
-\newline
-Alors : $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$
-Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $.
-\newline
-De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $.
+ Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue.
+ \newline
+ Alors : $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$
+ Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $.
+ \newline
+ De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $.
\end{Th}
On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues \cite{LJK,RON}. L'étude de la convexité de $ J $ sur $ \mathcal{C} $ permet d'explorer l'unicité de la solution \cite{LJK,RON}.
\subsection{Conditions de caractérisation d'un extremum}
-Dans le cas où $ J, g, h $ sont continûment différentiable et ses dérivées sont continues (c'est à dire de classe $ \mathcal{C}^1 $), la recherche du mimimum consiste à faire une descente par gradient [section \ref{descente}] de $ J $ sur $ \mathcal{C} $ avec comme critère d'arrêt : $ x_i = \displaystyle\min_{x \in \mathcal{C}} J(x) \iff \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \norme{\nabla J(x_i)} < \varepsilon $, $ i \in \mathbb{N} $ \cite{FEA}.
+Dans le cas où $ J, g, h $ sont continûment différentiable et ses dérivées sont continues (c'est à dire de classe $ \mathcal{C}^1 $), la recherche du mimimum consiste à faire des descentes par gradient [section \ref{descente}] de $ J $ sur $ \mathcal{C} $ avec comme critère d'arrêt : $ x_i = \displaystyle\min_{x \in \mathcal{C}} J(x) \iff \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \norme{\nabla J(x_i)} < \varepsilon $, $ i \in \mathbb{N} $ \cite{FEA}.
\newline
-On peut en déduire que une condition nécessaire et suffisante pour que $ x^\ast \in \mathring{\mathcal{C}} $ soit un des extremums locaux de $ J $ est que $ \nabla J(x^\ast) = 0 $. Mais si $ x^\ast \in \overline{\mathcal{C}}\setminus\mathring{\mathcal{C}} $ (la frontière de $ \mathcal{C} $) alors $ \nabla J(x^\ast) $ n'est pas nécessairement nul. Il sera par conséquent nécessaire de trouver d'autres caratérisations d'un extremum \cite{FEA,WAL}.
+On peut en déduire que une condition nécessaire et suffisante pour que $ x^\ast \in \mathring{\mathcal{C}} $ soit un des extremums locaux de $ J $ est que $ \nabla J(x^\ast) = 0 $. Mais si $ x^\ast \in \overline{\mathcal{C}}\setminus\mathring{\mathcal{C}} $ (la frontière de $ \mathcal{C} $) alors $ \nabla J(x^\ast) $ n'est pas nécessairement nul. Il sera par conséquent nécessaire de trouver d'autres caratérisations d'un extremum local \cite{FEA,WAL}.
\subsubsection{Conditions de Karuch-Kuhn-Tucker}\label{KKT}
\begin{Th}
-Soient $ 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 :
-\newline
-\newline
-\centerline{$ \{ \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.}
-\newline
-\newline
-et
-$$ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} \ \nabla J(x^\ast) + \sum_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $$
-On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
+ Soient $ 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 :
+ \newline
+ \newline
+ \centerline{$ \{ \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.}
+ \newline
+ \newline
+ et
+ $$ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} \ \nabla J(x^\ast) + \sum_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $$
+ On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
\end{Th}
\begin{proof}
-Elle repose sur le lemme de Farkas \cite{FEA,RON}.
+ 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.
\section{Methode de descente}\label{descente}
+Nous supposons que le domaine des contraintes de $ \mathcal{P} $ est un ouvert de $ \mathbb{R}^n $ (c'est à dire que nous n'avons pas de contraintes) et $ J $ est une fonction définie sur $ \mathbb{R}^n $ à valeurs réelles supposée différentiable, voire même deux fois différentiable. Les conditions nécessaires d’optimalité du premier et du second ordre expriment le fait qu’il n’est pas possible de “descendre” à partir d’un point de minimum (local ou global). Cette observation va servir de point de départ à l’élaboration des méthodes dites de descente.
+
Partant d’un point $ x_0 \in \mathbb{R}^n $ arbitrairement choisi, un algorithme de descente va chercher à générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ définie par :
-$$ x_{k+1} = x_k + s_kd_k $$ où $ s_k,d_k \in \mathbb{R}^n $ et avec
+$$ x_{k+1} = x_k + s_kd_k $$ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $ et avec
$$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
Un tel algorithme est ainsi déterminé par deux éléments à chaque étape $ k $ : le choix de la direction $ d_k $ appelée direction de descente, et le choix de la taille du pas $ s_k $ à faire dans la direction $ d_k $. Cette étape est appelée \textit{recherche linéaire}.
\subsection{Définition d'une direction de descente}
-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 décroissante en $ t = 0 $, c’est-à-dire :
+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.
\begin{Prop}
-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) $$
+ 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{Prop}
\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.
+ 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 :
\begin{enumerate}
\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 $.
- \item \textit{Recherche linéaire} : Choisir un pas $ s_k > 0 $ à faire dans cette direction et tel que : $$ J(x_k + s_kd_k) < J(x_k) $$.
- \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
- \end{enumerate}
- \item Retouner $ x_k $.
+ \begin{enumerate}
+ \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
+ \item \textit{Recherche linéaire} : Choisir un pas $ s_k > 0 $ à faire dans cette direction et tel que : $$ J(x_k + s_kd_k) < J(x_k). $$
+ \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
+ \end{enumerate}
+ \item Retourner $ x_k $.
\end{enumerate}
\hrulefill
\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}
-Remarquons que si $ x_k $ est un point stationnaire ($ \nabla J(x_k) = 0 $) non optimal alors toutes ces directions sont nulles et aucun de ces algorithmes ne pourra progresser. Ce problème
-peut être résolu en utilisant des approches de type région de confiance qui ne seront pas
-étudiées dans le cadre de ce projet.
+Remarquons que si $ x_k $ est un point stationnaire ($ \iff \nabla J(x_k) = 0 $) non optimal alors toutes ces directions sont nulles et aucun de ces algorithmes ne pourra progresser. Ce problème peut être résolu en utilisant des approches de type région de confiance qui ne seront pas étudiées dans le cadre de ce projet.
\subsection{Critère d’arrêt}
-Soit $ x^\ast $ un minimum local du critère $ 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 $.
+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
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) :
+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
Critère d’arrêt =
\begin{tabular}{l}
- Test d’optimalité satisfait \\
+ Test d’optimalité satisfait \\
OU (Stagnation de la valeur courante ET Stagnation de la solution) \\
OU Nombre d’itérations maximum autorisé dépassé
\end{tabular}
On appelle $ \varphi : s \in \mathbb{R} \longmapsto J(x + sd)$ la fonction mérite associée à $ J $ en $ x $.
\end{Def}
\begin{Def}
- Dans le cas où $ J, g, h $ sont de classe $ \mathcal{C}^1 $, on dit que un algorithme de descente converge ssi
+ Dans le cas où $ J $ est différentiable sur $ \mathcal{C} $, on dit que un algorithme de descente converge ssi
$$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$
\end{Def}
\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 $$
-Si $ J $ est bornée inférieurement, alors nécessairement $ J(x_0 ) - J(x_N) $ est majorée et donc la somme partielle est majorée, et donc la série $ (\sum_{i=0}^{N-1}\norme{\nabla J(x_i)}^2)_{N \in \mathbb{N}} $ converge, ce qui implique :
+Si $ J $ est bornée inférieurement, alors nécessairement $ J(x_0 ) - J(x_N) $ est majorée et donc la somme partielle est majorée, et donc la série $ (\sum\limits_{i=0}^{N-1}\norme{\nabla J(x_i)}^2)_{N \in \mathbb{N}} $ converge, ce qui implique :
$$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$
L'étude plus détaillée de différents algorithmes de descente qui utilisent différentes méthodes de recherche linéaire pour optimiser $ \varphi $ et le choix d'une direction ainsi que leurs convergences sort du cadre de ce projet.
\section{Méthode Newtonienne}
-L’algorithme de Newton en optimisation est une application directe de l’algorithme de
+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, $$
\newline
En supposant $ J $ de classe $ \mathcal{C}^2 $ et la matrice hessienne $ H[J](x_k) $ inversible, une itération de l’algorithme de Newton s’écrit :
$$ 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.
+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 $.
+\newline
+Les propriétés remarquables de cet algorithme sont :
+
+\begin{tabular}{|p{20em}|p{20em}|}
+ \hline
+ Avantages & Inconvénients \\
+ \hline
+ sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). & \\
+ \hline
+ & les difficultés et le coût de calcul de la hessienne $ H[J](x_k) $ : l’expression analytique des dérivées secondes est rarement disponible dans les applications. \\
+ \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. \\
+ \hline
+ & pas de distinction entre minima, maxima et points stationnaires. \\
+ \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 :
+$$ x_{k+1} = x_k - s_k H_k^{-1} \nabla J(x_k), $$
+où
+\begin{itemize}
+ \item la matrice $ H_k $ est une approximation de la hessienne $ H[J](x_k) $.
+ \item $ s_k > 0 $ est le pas calculé par une recherche linéaire bien choisie.
+\end{itemize}
+Plusieurs questions se posent alors :
+\begin{itemize}
+ \item Comment déterminer une matrice $ H_k $ qui soit une “bonne” approximation de la hessienne à l’itération $ k $ sans utiliser les informations de second ordre et garantir que $ H_k^{-1} \nabla J(x_k) $ soit bien une direction de descente de $ J $ en $ x_k $, sachant que la direction de Newton, si elle existe, n’en est pas nécessairement une ?
+ \item Comment conserver les bonnes propriétés de l’algorithme de Newton ?
+\end{itemize}
+Nous ne répondrons pas à ces questions qui sont hors du cadre de ce projet. Cette section permet d'introduire certains prérequis pour l'étude de la méthode PQS et de rendre compte de sa filiation.
\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é}.
+
+\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} $.
+
+\subsection{Algorithme PQS}
+
+\subsubsection{Contraintes d’égalité}
+
+Considérons un problème d’optimisation différentiable $ \mathcal{P} $ avec contraintes d’égalité :
+$$
+ \mathcal{P} \left \{
+ \begin{array}{l}
+ \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
+ h(x) = 0
+ \end{array}
+ \right .
+$$
+où $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables.
+\newline
+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 $$
+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 \\
+ \lambda_{k+1} - \lambda_k
+ \end{pmatrix} = -\nabla L(x_k,\lambda_k) $$
+soit :
+$$ \begin{pmatrix}
+ H_x[L](x_k,\lambda_k) & D_h(x_k)^\top \\
+ D_h(x_k) & 0
+ \end{pmatrix} \begin{pmatrix}
+ x_{k+1} - x_k \\
+ \lambda_{k+1} - \lambda_k
+ \end{pmatrix} = -\begin{pmatrix}
+ \nabla_x L(x_k,\lambda_k) \\
+ 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)] $$
+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 \\
+ D_h(x_k) & 0
+ \end{pmatrix} \begin{pmatrix}
+ d \\
+ \mu - \lambda_k
+ \end{pmatrix} = -\begin{pmatrix}
+ \nabla_x L(x_k,\lambda_k) \\
+ h(x_k)
+ \end{pmatrix} $$
+et est bien définie à condition que la matrice $ H_x[L](x_k,\lambda_k) $ soit inversible. Ce sera le cas si :
+\begin{enumerate}[label=(\roman*)]
+ \item Les colonnes $ \nabla h_1(x_k),\ldots,\nabla h_q(x_k) $ de $ D_h(x_k)^\top $ sont linéairement indépendants : c’est l’hypothèse de qualification des contraintes.
+ \item Quel que soit $ d \neq 0 $ tel que $ D_h(x_k)d = 0, \ d^\top H_k d > 0 $ : c’est la condition suffisante d’optimalité du second ordre dans le cas de contraintes d’égalité.
+\end{enumerate}
+Revenons à l’itération. Elle s’écrit encore :
+$$
+ \left \{
+ \begin{array}{r c l}
+ H_kd + \sum\limits_{i=1}^q(\mu_i - \lambda_{k_i})\nabla h_i(x_k) & = & -\nabla_x L(x_k,\lambda_k) \\
+ \nabla h_i(x_k)^\top d + h_i(x_k) & = & 0, \ \forall i \in \{1,\ldots,q\}
+ \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ù :
+$$
+ \left \{
+ \begin{array}{r c l}
+ H_kd + \sum\limits_{i=1}^q\mu_i\nabla h_i(x_k) & = & -\nabla J(x_k) \\
+ \nabla h_i(x_k)^\top d + h_i(x_k) & = & 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+$$
+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}
+ \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 .
+$$
+Le problème $ \mathcal{PQ}_k $ peut être vu comme la minimisation d’une approximation quadratique du Lagrangien de $ \mathcal{P} $ avec une approximation linéaire des contraintes.
+\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 :
+
+\subsubsection{Contraintes d’inégalité}
+
\bibliographystyle{plain}
\bibliography{stdlib_sbphilo}
repositories / Projet_Recherche_Operationnelle.git / blobdiff