1 \documentclass[12pt,oneside,
a4paper]{book
}
10 \usepackage{mathtools
}
12 \usepackage[utf8
]{inputenc}
13 \usepackage[francais
]{babel
}
18 \usepackage[T1]{fontenc}
21 \usepackage{tocbibind
}
25 %%%%%Marges & en-t\^etes
27 \geometry{hmargin=
2.3cm, vmargin=
3cm
}
28 \fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis
29 \fancyhead[FC
]{\bfseries\thepage} % N∞page centre bas
30 \fancyhead[HC
]{\footnotesize\leftmark} % chapitre centre haut
31 \renewcommand{\headrulewidth}{0.2pt
} % filet en haut
32 \addtolength{\headheight}{0.5pt
} % espace pour le filet
33 \renewcommand{\footrulewidth}{0.2pt
} % filet en bas
36 %%%%%Th\'eor\`eme et d\'efinitions
38 \newtheorem{Def
}{D\'efinition
}
39 \newtheorem{Not
}[Def
]{Notation
}
40 \newtheorem{Th
}{Th\'eor\`eme
}
41 \newtheorem{Prop
}[Th
]{Proposition
}
42 \newtheorem{Cor
}[Th
]{Corollaire
}
43 \newtheorem{Rmq
}{Remarque
}
45 \newcommand{\norme}[1]{\left\Vert #1\right\Vert}
47 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
48 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
52 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
53 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
59 %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\
60 \includegraphics[scale=
0.5]{polytech.png
}\\
65 \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\
66 \large \bf 5ème année\\
71 %\large{Master 2 Professionnel\\
72 %Math\'ematiques et Informatique des Nouvelles Technologies\\}
74 \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\
}
81 \LARGE\textbf {Programmation Séquentielle Quadratique ou PQS
} \\
83 \LARGE\textbf {Optimisation non linéraire sous contraintes
} \\
90 \includegraphics[scale=
0.4]{CE.PNG
}\\
97 %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\
100 \large {\bf Jérôme
\bsc{Benoit
} et Sylvain
\bsc{Papa
}}\\
104 % \large sous la direction de \\
108 %Eric Audureau et Thierry Masson
114 %\normalsize{Licence de Mathématiques 3ème année}
115 \normalsize{Année
2018-
2019}
119 \thispagestyle{empty
}
124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
136 %%%%%Table des mati\`eres
142 %\includegraphics{logo_fac2}
143 \includegraphics[scale=
0.04]{amu
}
150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
158 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
159 \chapter{Introduction générale
}
161 L'objectif de ce chapitre est de faire un bref rappel des définitions, notions et résultats essentiels en recherche opérationnelle ainsi que en mathématiques nécessaires à l'étude de la méthode PQS.
163 Elle est loin d'être exhaustive mais devrait suffire dans le cadre de ce projet.
167 \section{Qu'est-ce que la recherche opérationnelle?
}
169 \subsection{Présentation rapide
}
171 La recherche opérationnelle est une discipline dite "hybride" au confluent de plusieurs disciplines dont principalement les mathématiques (l'analyse numérique, les probabilités, la statistique) et l'informatique (l'algorithmie).
173 On la considère usuellement comme une sous discipline des mathématiques de la décision. Elle a de nombreuses applications, particulièrement en intelligence artificielle.
175 \subsection{Définition de la problèmatique
}
177 Définissons le problème central $
\mathcal{P
} $ que se propose de résoudre la recherche opérationnelle :
179 Soient $(n, p, q)
\in \mathbb{N
}^
3$, $x
\in \mathbb{R
}^n$, une fonction $g:
\mathbb{R
}^n
\longrightarrow \mathbb{R
}^p$ représentant les contraintes d'inégalités, une fonction $h:
\mathbb{R
}^n
\longrightarrow \mathbb{R
}^q$ représentant les contraintes d'égalités et une fonction dite objectif $J:
\mathbb{R
}^n
\longrightarrow \mathbb{R
}$.
181 La problèmatique $
\mathcal{P
} $ se définit par :
185 \displaystyle\min_{x
\in \mathbb{R
}^n
} J(x) \\
193 On définit $
\mathcal{C
} $ l'ensemble des contraintes par :
194 $$
\mathcal{C
} =
\left \
{ x
\in \mathbb{R
}^n \ | \ g(x)
\leq 0 \land h(x) =
0 \right \
} $$
196 Elle se doit de résoudre les problèmes d'existence d'une solution ($
\mathcal{C
} \neq \emptyset $ et $
\displaystyle\min_{x
\in \mathbb{R
}^n
} J(x) $ défini dans $
\mathcal{C
} $) ainsi que de construction d'une solution dans $
\mathcal{C
} $.
198 \section{Qu'est-ce que l'optimisation?
}
200 \subsection{Définition
}
202 La recherche d'une méthode permettant de trouver la solution au problème $
\mathcal{P
} $ dans $
\mathcal{C
} $ est l'activité principale de l'optimisation.
204 Si la modélisation de la problèmatique $
\mathcal{P
} $ est considérée comme un art, la recherche d'une solution au problème $
\mathcal{P
} $ dans $
\mathcal{C
} $ est, elle, une science.
206 \subsection{Quelques définitions annexes
}
208 Définissons quelques notions supplémentaires de base nécessaires à la suite :
210 Soient $
\mathbb{R
}^n $ un espace topologique, $ A
\subset \mathbb{R
}^n $ et $ x^
\ast \in \mathbb{R
}^n $.
212 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
} $.
215 $ A
\subset \mathbb{R
}^n $ est un ouvert $
\iff A =
\mathring{A
} $.
218 Soient $
\mathbb{R
}^n $ un espace topologique, $ A
\subset \mathbb{R
}^n $ et $ x^
\ast \in \mathbb{R
}^n $.
220 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
} $.
223 $ A
\subset \mathbb{R
}^n $ est un fermé $
\iff A =
\overline{A
} $.
226 Soient une fonction $ f:
\mathbb{R
}^n
\longrightarrow \mathbb{R
} $ et $ x^
\ast \in \mathbb{R
}^n $.
228 On dit que $ f $ est continue en $ x^
\ast $ si
229 $$
\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 $$
232 Soient $ k
\in \
{ 1,
\ldots,n \
} $ et une fonction $ f:
\mathbb{R
}^n
\longrightarrow \mathbb{R
} $.
234 On dit que la $ k^
{ième
} $ dérivée partielle de $ f $ existe au point $ x^
\ast \in \mathbb{R
}^n $ si l’application
235 $$ t
\longmapsto f(x^
\ast_1,
\ldots,x^
\ast_{k-
1},x^
\ast_k + t,x^
\ast_{k+
1},
\ldots,x^
\ast_n) $$
236 définie sur un voisinage de $
0 $ dans $
\mathbb{R
} $ et à valeurs dans $
\mathbb{R
} $ est dérivable en $
0 $.
239 $$
\frac{\partial f
}{\partial x_k
}(x^
\ast) $$ ou $$
\partial_k f(x^
\ast) $$
243 Soient une fonction $ f:
\mathbb{R
}^n
\longrightarrow \mathbb{R
} $
244 et $ x^
\ast, h
\in \mathbb{R
}^n $.
246 On dit que $ f $ est différentiable en $ x^
\ast $ si il existe une application linéraire $ d_
{x^
\ast}f $ de $
\mathbb{R
}^n $ dans $
\mathbb{R
} $ telle que
248 f(x^
\ast + h) = f(x^
\ast) + d_
{x^
\ast}f(h) +
\underset{h
\rightarrow 0}{\mathrm{o
}}(
\norme{h
})
250 Autrement dit il existe une application $
\varepsilon_{x^
\ast} $ définie sur le voisinage de $
0 $ dans $
\mathbb{R
}^n $ et à valeurs dans $
\mathbb{R
} $
251 telle que $
\lim\limits_{h
\rightarrow 0} \varepsilon_{x^
\ast}(h) =
0 $ et
253 f(x^
\ast + h) = f(x^
\ast) + d_
{x^
\ast}f(h) +
\norme{h
}\varepsilon_{x^
\ast}(h)
255 On appelle $ d_
{x^
\ast}f $ la différentielle de $ f $ en $ x^
\ast $.
258 On peut démontrer que : $$ d_
{x^
\ast}f =
\sum_{i=
1}^n
\frac{\partial f
}{\partial x_i
}(x^
\ast) $$.
261 Soit une fonction $ f:
\mathbb{R
}^n
\longrightarrow \mathbb{R
} $ différentiable.
263 Le gradient de $ f $, noté $
\nabla f$, en $ x^
\ast \in \mathbb{R
}^n$ se définit par :
265 \nabla f(x^
\ast) = (
\frac{\partial f
}{\partial x_1
}(x^
\ast),
\ldots,
\frac{\partial f
}{\partial x_n
}(x^
\ast))
269 $
\forall h
\in \mathbb{R
}^n \ d_
{x^
\ast}f(h) =
\langle \nabla f(x^
\ast),h
\rangle $
272 Soit $ f:
\mathbb{R
}^n
\longrightarrow \mathbb{R
} $ un fonction de classe $
\mathcal{C
}^
2 $.
273 On définit la matrice hessienne de $ f $ en $ x^
\ast $ par :
276 \frac{\partial^
2 f
}{\partial x_1^
2}(x^
\ast) &
\cdots &
\frac{\partial^
2 f
}{\partial x_1
\partial x_n
}(x^
\ast) \\
278 \frac{\partial^
2 f
}{\partial x_n
\partial x_1
}(x^
\ast) &
\cdots &
\frac{\partial^
2 f
}{\partial x_n^
2}(x^
\ast)
283 \item $ H
[f
](x^
\ast) $ est une matrice symétrique (Théorème de symétrie de Schwarz).
284 \item On a le développement de Taylor-Young à l'ordre
2 suivant :
285 $$ 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) $$
286 avec $
\frac{|
\varepsilon(v)|
}{\norme{v
}} \rightarrow 0 $ quand $
\norme{v
} \rightarrow 0 $.
290 \subsection{Conditions d'existence d'un extremum
}
292 On peut démontrer que $
\mathcal{C
}$ est un ensemble fermé de $
\mathbb{R
}^n $ si $ g $ et $ h $ sont continues.
293 On peut en déduire que si $ J $ est continue, $
\mathcal{C
}$ est un ensemble fermé et borné de $
\mathbb{R
}^n $.
294 \begin{Th
}[Théorème de Weierstrass
]
295 Soient $
\mathcal{C
} \neq \emptyset \subset \mathbb{R
}^n $ un fermé borné et $ f :
\mathcal{C
} \longrightarrow \mathbb{R
} $ une fonction continue.
297 Alors : $$
\exists x^
\ast \in \mathcal{C
} \
\forall x
\in \mathcal{C
} \ f(x)
\geq f(x^
\ast) $$
298 Autrement dit $ x^
\ast $ est un minimum global de $ J $ sur $
\mathcal{C
} $.
300 De la même façon, il existe un maximum global de $ J $ sur $
\mathcal{C
} $.
302 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
}.
304 \subsection{Conditions de caractérisation d'un extremum
}
306 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
}.
308 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
}.
310 \subsubsection{Conditions de Karuch-Kuhn-Tucker
}\label{KKT
}
313 Soient $ x^
\ast \in \mathbb{R
}^n $, $ I = \
{ 1,
\ldots,p \
} $ et $ J = \
{ 1,
\ldots,q \
} $.
315 Les conditions nécessaires pour que $ x^
\ast \in \mathcal{C
}$ soit un minimum local de $ J $ sont :
318 \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.
}
322 $$
\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 $$
323 On appelle $ (
\mu_i)_
{i
\in I
}$ les multiplicateurs de Kuhn-Tucker et $ (
\lambda_j)_
{j
\in J
}$ les multiplicateurs de Lagrange.
326 Elle repose sur le lemme de Farkas
\cite{FEA,RON
}.
328 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.
331 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
333 \chapter{Méthode de programmation quadratique séquentielle
}
335 Dans ce projet, nous nous proposons d'étudier une des méthodes d'optimisation non linéaire avec contraintes nommée programmation quadratique séquentielle ou PQS.
339 \section{Methode de descente
}\label{descente
}
341 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 :
342 $$ x_
{k+
1} = x_k + s_kd_k $$ où $ s_k
\in \mathbb{R
}_
{+
}^
{*
},d_k
\in \mathbb{R
}^n $ et avec
343 $$
\forall k
\in \mathbb{N
} \ J(x_
{k+
1})
\leq J(x_k) $$
344 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
}.
346 \subsection{Définition d'une direction de descente
}
348 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 :
349 $$
\exists \eta \in \mathbb{R
}_
{+
}^
{*
} \
\forall t
\in ]0,
\eta] \ J(x_0 + td) < J(x_0) $$
350 Il est donc important d’analyser le comportement de la fonction $ J $ dans certaines direc-
353 Soient $ J :
\mathbb{R
}^n
\longrightarrow \mathbb{R
} $ différentiable et $ d
\in \mathbb{R
}^n $.
355 d est un vecteur de descente de $ J $ en $ x_0
\in \mathbb{R
}^n $ ssi :
356 $$
\nabla J(x_0)^
\top d <
0 $$
358 $$
\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) $$
361 Elle s'effectue en utilisant le développement de Taylor-Young de l’application $ t
\longmapsto f(x_0 + td) $ à l’ordre
1.
363 Cette dernière inégalité garantit une décroissance minimum de la fonction $ J $ dans la
364 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 :
368 ALGORITHME DE DESCENTE MODÈLE.
370 \textit{Entrées
}: $ J :
\mathbb{R
}^n
\longrightarrow \mathbb{R
} $ différentiable, $ x_0
\in \mathbb{R
}^n $ point initial arbitraire.
372 \textit{Sortie
}: une approximation de la solution du problème : $
\displaystyle\min_{x
\in \mathbb{R
}^n
} J(x) $.
375 \item Tant que "test d’arrêt" non satisfait,
377 \item Trouver une direction de descente $ d_k $ telle que : $
\nabla J(x_k)^
\top d_k <
0 $.
378 \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). $$
379 \item Mise à jour : $ x_
{k+
1} = x_k + s_kd_k; \ k := k +
1 $.
381 \item Retourner $ x_k $.
386 \subsection{Choix de la direction de descente
}
388 Une fois la théorie bien maîtrisée, calculer une direction de descente est relativement
389 simple. Dans le cas différentiable, il existe deux grandes stratégies de choix de direction de
392 \item la stratégie de Cauchy : $ d_k = -
\nabla J(x_k) $, conduisant aux
\textit{algorithmes de gradient
}.
393 \item la stratégie de Newton : $ d_k = -H
[J
](x_k)^
{-
1} \nabla J(x_k) $, conduisant aux
\textit{algorithmes Newtoniens
}.
395 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.
397 \subsection{Critère d’arrêt
}
399 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 $.
401 En pratique, un test d’arrêt devra être choisi pour garantir que l’algorithme s’arrête
402 toujours après un nombre fini d’itérations et que le dernier point calculé soit suffisamment
403 proche de $ x^
\ast $.
405 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
406 sans contrainte, on testera si
407 $$
\norme{\nabla J(x_k)
} <
\varepsilon, $$
408 auquel cas l’algorithme s’arrête et fournit l’itéré courant $ x_k $ comme solution.
410 En pratique, le test d’optimalité n’est pas toujours satisfait et on devra faire appel à
411 d’autres critères fondés sur l’expérience du numérique :
413 \item Stagnation de la solution : $
\norme{x_
{k+
1} - x_k
} <
\varepsilon(
1 +
\norme{x_k
}) $.
414 \item Stagnation de la valeur courante : $ |J(x_
{k+
1}) - J(x_k)| <
\varepsilon(
1 + |J (x_k)|) $.
415 \item Nombre d’itérations dépassant un seuil fixé à l’avance : $ k < IterMax $.
417 et généralement une combinaison de ces critères :
422 Test d’optimalité satisfait \\
423 OU (Stagnation de la valeur courante ET Stagnation de la solution) \\
424 OU Nombre d’itérations maximum autorisé dépassé
427 \subsection{La recherche linéaire
}
429 Supposons pour l’instant résolu le problème du choix de la direction de descente et intéressons nous uniquement au calcul du pas : c’est la phase de recherche linéaire.
431 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 :
432 $$ J(x_0 + sd) < J(x_0). $$
433 Le choix de ce pas répond généralement à deux objectifs souvent contradictoires : trouver
434 le meilleur pas possible et effectuer le moins de calculs possibles. Ces deux objectifs ont
435 donné naissance à deux grandes familles : les algorithmes à pas fixe et ceux à pas optimal.
439 RECHERCHE LINÉAIRE : PAS FIXE. $ s_k = s_
{k-
1} $
445 RECHERCHE LINÉAIRE : PAS OPTIMAL. $ s_k $ solution du problème $
\displaystyle\min_{s
\in \mathbb{R
}_
{+
}^
{*
}} J(x_k + sd_k) $
449 Illustrées par les méthodes de descente de gradient, aucune de ces deux stratégies ne
450 s’est révélée réellement convaincante : si la première peut être “risquée” du point de vue de
451 la convergence, la seconde est souvent loin d’être triviale à mettre en oeuvre (sauf dans le
452 cas quadratique) et généralement inutilement coûteuse : en effet, à quoi bon calculer très
453 précisément un pas optimal dans une direction qui n’est peut-être pas la bonne ? (comme
454 c’est par exemple le cas pour la méthode de plus profonde descente). Les recherches
455 linéaires modernes reposent sur l’idée qu’un pas de descente acceptable est un pas qui fait
456 “suffisamment” décroître la fonction objectif. Reste alors à définir les pas qui sont
457 acceptables et ceux qui ne le sont pas.
459 On appelle $
\varphi : s
\in \mathbb{R
} \longmapsto J(x + sd)$ la fonction mérite associée à $ J $ en $ x $.
462 Dans le cas où $ J $ est différentiable sur $
\mathcal{C
} $, on dit que un algorithme de descente converge ssi
463 $$
\lim\limits_{k
\rightarrow +
\infty} \norme{\nabla J(x_k)
} =
0 $$
466 \subsubsection{Principe de démonstration de convergence
}
468 Une technique classique en optimisation pour obtenir des résultats de convergence glo-
469 bale consiste à montrer que l’algorithme de descente considéré vérifie une inégalité du
471 $$ J(x_k) - J(x_
{k+
1})
\geq c
\norme{\nabla J(x_k)
}^
2, $$
472 où $ c $ est un constante réelle.
474 En sommant ces inégalités pour $ k $ variant de $
0 $ à $ N -
1 $, on obtient :
475 $$
\forall N
\in \mathbb{N
} \ J(x_0) - J(x_N)
\geq c
\sum_{i=
0}^
{N-
1}\norme{\nabla J(x_i)
}^
2 $$
476 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 :
477 $$
\lim\limits_{k
\rightarrow +
\infty} \norme{\nabla J(x_k)
} =
0 $$
478 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.
480 \section{Méthode Newtonienne
}
482 L’algorithme de Newton en optimisation est une application directe de l’algorithme de
483 Newton pour la résolution d’équations du type : $ F(x) =
0 $. En optimisation sans contrainte,
484 l’algorithme de Newton cherche les solutions de l’équation :
485 $$
\nabla J(x) =
0, $$
486 autrement dit, les points critiques de la fonction $ J $ à minimiser.
488 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 :
489 $$ x_
{k+
1} = x_k - H
[J
](x_k)^
{-
1} \nabla J(x_k), $$
490 où $ d_k = -H
[J
](x_k)^
{-
1} \nabla J(x_k) $ est appelée direction de Newton.
492 \section{Méthode PQS (ou SQP)
}
494 \bibliographystyle{plain
}
495 \bibliography{stdlib_sbphilo
}
497 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%