From: Jérôme Benoit Date: Mon, 5 Nov 2018 09:52:40 +0000 (+0100) Subject: More code cleanups. X-Git-Url: https://git.piment-noir.org/?p=Projet_Recherche_Operationnelle.git;a=commitdiff_plain;h=a5f09ac40f68d6b2b4814007afd02527ea370283 More code cleanups. Signed-off-by: Jérôme Benoit --- diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index e10b20c..6ffc1f6 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -276,7 +276,7 @@ Définissons quelques notions supplémentaires de base nécessaires à la suite \] \end{Def} \begin{Rmq} - $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $ + $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle = \nabla f(x^\ast)^\top h $ \end{Rmq} \begin{Def} Soit $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ un fonction de classe $ \mathcal{C}^2 $. @@ -305,7 +305,7 @@ Définissons quelques notions supplémentaires de base nécessaires à la suite \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 $. +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 @@ -453,8 +453,7 @@ RECHERCHE LINÉAIRE : PAS OPTIMAL. $ s_k $ solution du problème $ \displaystyle \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. +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. \begin{Def} On appelle $ \varphi : s \in \mathbb{R} \longmapsto J(x + sd)$ la fonction mérite associée à $ J $ en $ x $. \end{Def} @@ -486,7 +485,7 @@ $$ 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 $. +À 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 : @@ -522,10 +521,9 @@ Nous ne répondrons pas à ces questions qui sont hors du cadre de ce projet. Ce \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é}. +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} +\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}} $ (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} $.