Small fixlets.
[Projet_Recherche_Operationnelle.git] / rapport / ProjetOptimRO.tex
CommitLineData
e37aec65
JB
1\documentclass[12pt,oneside,a4paper]{book}
2
3
4%%%%%Packages
5
de30386e 6
e37aec65 7\usepackage{latexsym}
66a4e4ad 8\usepackage{amsmath}
8000c039 9\usepackage{amsthm}
66a4e4ad 10\usepackage{mathtools}
e37aec65
JB
11\usepackage{amssymb}
12\usepackage[utf8]{inputenc}
13\usepackage[francais]{babel}
14\usepackage{color}
15\usepackage{geometry}
16\usepackage{graphicx}
17\usepackage{amsfonts}
18\usepackage[T1]{fontenc}
19\usepackage{multirow}
20\usepackage{fancyhdr}
21\usepackage{tocbibind}
22\usepackage{lmodern}
7fd51f8b 23\usepackage{enumitem}
4b8b7ee7 24\usepackage{algorithm2e}
b8e1f3f6 25\usepackage{algorithmic}
e37aec65
JB
26
27
28%%%%%Marges & en-t\^etes
29
30\geometry{hmargin=2.3cm, vmargin=3cm}
31\fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis
32\fancyhead[FC]{\bfseries\thepage} % N∞page centre bas
33\fancyhead[HC]{\footnotesize\leftmark} % chapitre centre haut
34\renewcommand{\headrulewidth}{0.2pt} % filet en haut
35\addtolength{\headheight}{0.5pt} % espace pour le filet
66a4e4ad 36\renewcommand{\footrulewidth}{0.2pt} % filet en bas
e37aec65
JB
37
38
39%%%%%Th\'eor\`eme et d\'efinitions
40
41\newtheorem{Def}{D\'efinition}
42\newtheorem{Not}[Def]{Notation}
43\newtheorem{Th}{Th\'eor\`eme}
44\newtheorem{Prop}[Th]{Proposition}
45\newtheorem{Cor}[Th]{Corollaire}
46\newtheorem{Rmq}{Remarque}
47
682e0379 48\newcommand{\norme}[1]{\left\Vert #1 \right\Vert}
e37aec65
JB
49
50%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
51%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
52
53\begin{document}
54
55%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
56%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
57
58%%%%%Page de garde
59
60\begin{center}
61
b0927d0a 62 %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\
cec1e8f8 63 \includegraphics[scale=0.5]{polytech.png}\\
b0927d0a
JB
64
65 \vspace*{0.5cm}
66
67 \footnotesize{
68 \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\
69 \large \bf 5ème année\\
70 }
71
72 \vspace*{0.5cm}
73
74 %\large{Master 2 Professionnel\\
75 %Math\'ematiques et Informatique des Nouvelles Technologies\\}
76
77 \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\}
78
79 \vspace*{0.7cm}
80
81 \begin{tabular}{c}
82 \hline
9f054a9c 83 ~ \\
7fd51f8b 84 \LARGE\textbf {Programmation Quadratique Séquentielle ou PQS} \\
9f054a9c
JB
85 \LARGE\textbf {en} \\
86 \LARGE\textbf {Optimisation non linéraire sous contraintes} \\
87 ~ \\
b0927d0a
JB
88 \hline
89 \end{tabular}
90
91 \vspace*{0.7cm}
92
93 \includegraphics[scale=0.4]{CE.PNG}\\
94
95 \vspace*{0.5cm}
96
97 \large par\\
98
99 %\large \bsc{}\\
100 %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\
101
102 \vspace*{0.2cm}
91df3de1 103 \large {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\
b0927d0a
JB
104
105 %\vspace*{0.1cm}
106
107 % \large sous la direction de \\
108
109 %\vspace*{0.1cm}
110
111 %Eric Audureau et Thierry Masson
112
113 %\vspace*{1cm}
114
115 \vspace*{1cm}
116
117 %\normalsize{Licence de Mathématiques 3ème année}
118 \normalsize{Année 2018-2019}
e37aec65
JB
119
120\end{center}
121
122\thispagestyle{empty}
123
124\newpage
125
126
127%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
128%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
129
130
131\pagestyle{plain}
132\frontmatter
133
134
135%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
136%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
137
138
e37aec65
JB
139%%%%%Table des mati\`eres
140
141\tableofcontents
142
143\begin{figure}[!b]
b0927d0a
JB
144 \begin{center}
145 %\includegraphics{logo_fac2}
146 \includegraphics[scale=0.04]{amu}
147 \end{center}
e37aec65
JB
148\end{figure}
149
150\newpage
151
152
153%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
154%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
155
156
157\mainmatter
158\pagestyle{fancy}
159
160
161%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
162\chapter{Introduction générale}
163
8000c039
JB
164L'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.
165\newline
166Elle est loin d'être exhaustive mais devrait suffire dans le cadre de ce projet.
167
e37aec65
JB
168\vspace{.5em}
169
170\section{Qu'est-ce que la recherche opérationnelle?}
171
64f7c064
JB
172\subsection{Présentation rapide}
173
f899c72b 174La 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).
e7e85554 175\newline
f899c72b 176On 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.
91df3de1 177
64f7c064
JB
178\subsection{Définition de la problèmatique}
179
f899c72b 180Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la recherche opérationnelle :
6ec0df37 181\begin{Def}
5e4341d1
JB
182 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}$.
183 \newline
184 La problèmatique $ \mathcal{P} $ se définit par :
185 $$
aa023e1c 186 \mathcal{P} \left \{
7fd51f8b 187 \begin{array}{l}
aa023e1c
JB
188 \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
189 g(x) \leq 0 \\
190 h(x) = 0
191 \end{array}
192 \right .
5e4341d1 193 $$
6ec0df37 194\end{Def}
6ec0df37 195\begin{Def}
5e4341d1
JB
196 On définit $ \mathcal{C} $ l'ensemble des contraintes par :
197 $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$
6ec0df37 198\end{Def}
3b344e8c 199Elle 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} $.
64f7c064 200
e37aec65
JB
201\section{Qu'est-ce que l'optimisation?}
202
f899c72b
JB
203\subsection{Définition}
204
205La 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.
206\newline
8a00a107 207Si 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.
f899c72b
JB
208
209\subsection{Quelques définitions annexes}
210
211Définissons quelques notions supplémentaires de base nécessaires à la suite :
682e0379
JB
212\begin{Def}
213 On définit le Lagrangien associé à $ \mathcal{P} $ par :
214 $$ \begin{array}{r c l}
215 L : \mathbb{R}^n \times \mathbb{R}^q \times \mathbb{R}_+^p & \longrightarrow & \mathbb{R} \\
7fd51f8b 216 (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) \\
682e0379
JB
217 & & L(x,\lambda,\mu) = J(x) + \langle \lambda,h(x) \rangle_{\mathbb{R}^q} + \langle \mu,g(x) \rangle_{\mathbb{R}^p}
218 \end{array} $$
219 où l’on note $ \lambda $ et $ \mu $ les vecteurs de coordonnées respectives $ (\lambda_1,\ldots,\lambda_q) $ et $ (\mu_1,\ldots,\mu_p) $.
220\end{Def}
f899c72b 221\begin{Def}
9f054a9c
JB
222 Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
223 \newline
224 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} $.
f899c72b 225\end{Def}
9f054a9c
JB
226\begin{Rmq}
227 $ A \subset \mathbb{R}^n $ est un ouvert $ \iff A = \mathring{A} $.
228\end{Rmq}
f899c72b 229\begin{Def}
9f054a9c
JB
230 Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
231 \newline
232 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} $.
f899c72b 233\end{Def}
9f054a9c
JB
234\begin{Rmq}
235 $ A \subset \mathbb{R}^n $ est un fermé $ \iff A = \overline{A} $.
236\end{Rmq}
f899c72b 237\begin{Def}
7590f4bb
JB
238 Soient $ f : \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ S \subset \mathbb{R}^n $. On définit $ \mathrm{argmin} $ de $ f $ sur $ S $ par :
239 $$ \underset{x \in S}{\mathrm{argmin}} f(x) = \{ x \in \mathbb{R}^n \ | \ x \in S \land \forall y \in S \ f(y) \geq f(x) \} $$
240\end{Def}
241\begin{Def}
242 Soient une fonction $ f : \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $.
9f054a9c
JB
243 \newline
244 On dit que $ f $ est continue en $ x^\ast $ si
245 $$ \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 $$
f899c72b 246\end{Def}
d17ef079
JB
247\begin{Def}
248 Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $.
249 \newline
250 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
251 $$ t \longmapsto f(x^\ast_1,\ldots,x^\ast_{k-1},x^\ast_k + t,x^\ast_{k+1},\ldots,x^\ast_n) $$
252 définie sur un voisinage de $ 0 $ dans $ \mathbb{R} $ et à valeurs dans $ \mathbb{R} $ est dérivable en $ 0 $.
253 \newline
254 Dans ce cas on note
255 $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$
256 cette dérivée.
257\end{Def}
66a4e4ad 258\begin{Def}
7590f4bb 259 Soient une fonction $ f : \mathbb{R}^n \longrightarrow \mathbb{R} $
66a4e4ad 260 et $ x^\ast, h \in \mathbb{R}^n $.
d17ef079 261 \newline
66a4e4ad
JB
262 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
263 \[
264 f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h})
265 \]
266 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} $
267 telle que $ \lim\limits_{h \rightarrow 0} \varepsilon_{x^\ast}(h) = 0 $ et
268 \[
269 f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h)
270 \]
d17ef079 271 On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $.
66a4e4ad 272\end{Def}
d17ef079
JB
273\begin{Rmq}
274 On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$.
275\end{Rmq}
5e4341d1
JB
276\begin{Def}
277 Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
278 \newline
279 Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
280 \[
de30386e 281 \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
5e4341d1
JB
282 \]
283\end{Def}
d17ef079 284\begin{Rmq}
a5f09ac4 285 $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle = \nabla f(x^\ast)^\top h $
d17ef079 286\end{Rmq}
9f054a9c 287\begin{Def}
84af1fe2 288 Soit $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ une fonction de classe $ \mathcal{C}^2 $.
9f054a9c
JB
289 On définit la matrice hessienne de $ f $ en $ x^\ast $ par :
290 $$ H[f](x^\ast) =
291 \begin{pmatrix}
292 \frac{\partial^2 f}{\partial x_1^2}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n}(x^\ast) \\
293 \vdots & & \vdots \\
294 \frac{\partial^2 f}{\partial x_n\partial x_1}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_n^2}(x^\ast)
295 \end{pmatrix} $$
296\end{Def}
297\begin{Prop}
298 \begin{enumerate}
299 \item $ H[f](x^\ast) $ est une matrice symétrique (Théorème de symétrie de Schwarz).
682e0379 300 \item On a le développement de Taylor-Young à l'ordre 2 en $ x^\ast $ suivant :
9f054a9c 301 $$ 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) $$
682e0379
JB
302 ou
303 $$ 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) $$
9f054a9c
JB
304 avec $ \frac{|\varepsilon(v)|}{\norme{v}} \rightarrow 0 $ quand $ \norme{v} \rightarrow 0 $.
305 \end{enumerate}
306\end{Prop}
682e0379
JB
307\begin{proof}
308 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.
309\end{proof}
f899c72b
JB
310
311\subsection{Conditions d'existence d'un extremum}
312
7590f4bb
JB
313On peut démontrer que $ \mathcal{C}$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues.
314On peut en déduire $ \mathcal{C} $ est un ensemble fermé et borné de $ \mathbb{R}^n $.
3b344e8c 315\begin{Th}[Théorème de Weierstrass]
9f054a9c
JB
316 Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue.
317 \newline
318 Alors : $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$
319 Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $.
320 \newline
321 De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $.
3b344e8c 322\end{Th}
7590f4bb 323Si $ J $ est continue, 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}.
b6cd6632 324
3b344e8c
JB
325\subsection{Conditions de caractérisation d'un extremum}
326
9f054a9c 327Dans 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}.
f899c72b 328\newline
9f054a9c 329On 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}.
f899c72b 330
7590f4bb 331\subsubsection{Conditions nécessaires de Karuch-Kuhn-Tucker ou \textit{KKT}}\label{KKT}
f899c72b
JB
332
333\begin{Th}
9f054a9c
JB
334 Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
335 \newline
336 Les conditions nécessaires pour que $ x^\ast \in \mathcal{C}$ soit un minimum local de $ J $ sont :
09448b62
JB
337 \begin{center}
338 $ \{ \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.
339 \end{center}
9f054a9c 340 et
09448b62
JB
341 \begin{center}
342 $ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} $ tels que :
343 \end{center}
344 \begin{center}
345 $ \nabla J(x^\ast) + \sum\limits_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum\limits_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $
346 \end{center}
347 \begin{center}
348 $ \iff \nabla L(x^\ast,\lambda,\mu) = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $ où $ \lambda = (\lambda_1,\ldots,\lambda_q) $ et $ \mu = (\mu_1,\ldots,\mu_p) $.
349 \end{center}
9f054a9c 350 On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
7590f4bb
JB
351 \newline
352 On nomme également les conditions \textit{KTT} conditions nécessaires d'optimalité du premier ordre.
f899c72b 353\end{Th}
8000c039 354\begin{proof}
9f054a9c 355 Elle repose sur le lemme de Farkas \cite{FEA,RON}.
8000c039 356\end{proof}
6079168f 357Il 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.
7590f4bb
JB
358\begin{Def}
359 On appelle un point admissible $ x^\ast \in \mathcal{C} $ un point critique de $ \mathcal{P} $ si il statisfait les conditions \textit{KKT}.
360\end{Def}
8000c039 361
7590f4bb
JB
362\subsubsection{Conditions suffisantes du deuxième ordre}
363
364\begin{Th}
365 Les conditions suffisantes en plus de celles \textit{KKT} pour que $ x^\ast \in \mathcal{C} $ soit un minimum local de $ J $ sont :
366 \begin{enumerate}[label=(\roman*)]
367 \item relâchement complémentaire dual\footnote{La définition de cette notion ne sera pas donnée car elle n'est pas nécessaire pour l'étude de la méthode PQS.} strict en $ x^\ast $.
368 \item $ \forall v \in \mathbb{R}^n \land v \neq 0 \ \langle H_x[L](x^\ast,\lambda,\mu)v,v \rangle > 0 $.
369 \end{enumerate}
370\end{Th}
8000c039
JB
371
372%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
373
374\chapter{Méthode de programmation quadratique séquentielle}
375
376Dans 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.
377
378\vspace{.5em}
379
380\section{Methode de descente}\label{descente}
381
682e0379
JB
382Nous 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.
383
8000c039 384Partant 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 :
9f054a9c 385$$ x_{k+1} = x_k + s_kd_k $$ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $ et avec
8000c039
JB
386$$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
387Un 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}.
388
389\subsection{Définition d'une direction de descente}
390
9f054a9c 391Un 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 :
8000c039 392$$ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) $$
6079168f 393Il est donc important d’analyser le comportement de la fonction $ J $ dans certaines directions.
8000c039 394\begin{Prop}
9f054a9c
JB
395 Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $.
396 \newline
397 d est un vecteur de descente de $ J $ en $ x_0 \in \mathbb{R}^n $ ssi :
398 $$ \nabla J(x_0)^\top d < 0 $$
399 De plus
400 $$ \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) $$
8000c039
JB
401\end{Prop}
402\begin{proof}
9f054a9c 403 Elle s'effectue en utilisant le développement de Taylor-Young de l’application $ t \longmapsto f(x_0 + td) $ à l’ordre 1.
8000c039 404\end{proof}
6079168f 405Cette 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 :
8000c039
JB
406
407\hrulefill
408\newline
09448b62 409ALGORITHME DE DESCENTE GÉNÉRIQUE.
8000c039
JB
410\newline
411\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
412\newline
e17152e0 413\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
8000c039 414\begin{enumerate}
e17152e0 415 \item $ k := 0 $.
8000c039 416 \item Tant que "test d’arrêt" non satisfait,
9f054a9c
JB
417 \begin{enumerate}
418 \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
419 \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). $$
420 \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
421 \end{enumerate}
422 \item Retourner $ x_k $.
8000c039
JB
423\end{enumerate}
424
425\hrulefill
426
427\subsection{Choix de la direction de descente}
428
e17152e0 429Une 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 :
8000c039
JB
430\begin{itemize}
431 \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}.
432 \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}.
433\end{itemize}
9f054a9c 434Remarquons 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.
8000c039
JB
435
436\subsection{Critère d’arrêt}
437
09448b62 438Soit $ 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 générique, 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 $.
f899c72b 439\newline
6079168f 440En 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 $.
8000c039 441
6079168f 442Soit $ \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
8000c039
JB
443$$ \norme{\nabla J(x_k)} < \varepsilon, $$
444auquel cas l’algorithme s’arrête et fournit l’itéré courant $ x_k $ comme solution.
445
e17152e0 446En 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 :
8000c039
JB
447\begin{itemize}
448 \item Stagnation de la solution : $ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $.
449 \item Stagnation de la valeur courante : $ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $.
450 \item Nombre d’itérations dépassant un seuil fixé à l’avance : $ k < IterMax $.
451\end{itemize}
452et généralement une combinaison de ces critères :
de30386e 453\newline
8000c039
JB
454\newline
455Critère d’arrêt =
456\begin{tabular}{l}
9f054a9c 457 Test d’optimalité satisfait \\
8000c039
JB
458 OU (Stagnation de la valeur courante ET Stagnation de la solution) \\
459 OU Nombre d’itérations maximum autorisé dépassé
460\end{tabular}
6ec0df37 461
8000c039 462\subsection{La recherche linéaire}
e37aec65 463
8000c039
JB
464Supposons 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.
465\newline
466Soit $ 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 :
467$$ J(x_0 + sd) < J(x_0). $$
6079168f 468Le 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.
8000c039
JB
469
470\hrulefill
471\newline
472RECHERCHE LINÉAIRE : PAS FIXE. $ s_k = s_{k-1} $
473
474\hrulefill
475
476\hrulefill
477\newline
478RECHERCHE LINÉAIRE : PAS OPTIMAL. $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
e37aec65 479
8000c039
JB
480\hrulefill
481\newline
a5f09ac4 482Illustré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.
8000c039
JB
483\begin{Def}
484 On appelle $ \varphi : s \in \mathbb{R} \longmapsto J(x + sd)$ la fonction mérite associée à $ J $ en $ x $.
485\end{Def}
486\begin{Def}
9f054a9c 487 Dans le cas où $ J $ est différentiable sur $ \mathcal{C} $, on dit que un algorithme de descente converge ssi
7590f4bb 488 $$ \forall x_0 \in \mathbb{R}^n \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$
8000c039
JB
489\end{Def}
490
491\subsubsection{Principe de démonstration de convergence}
de30386e 492
e17152e0 493Une 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 :
8000c039 494$$ J(x_k) - J(x_{k+1}) \geq c\norme{\nabla J(x_k)}^2, $$
e17152e0 495où $ c $ est une constante réelle.
8000c039
JB
496\newline
497En sommant ces inégalités pour $ k $ variant de $ 0 $ à $ N - 1 $, on obtient :
498$$ \forall N \in \mathbb{N} \ J(x_0) - J(x_N) \geq c \sum_{i=0}^{N-1}\norme{\nabla J(x_i)}^2 $$
9f054a9c 499Si $ 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 :
8000c039 500$$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$
7590f4bb
JB
501\begin{Def}
502 On considère $ (x_n)_{n \in \mathbb{N}} $, la suite des itérés donnés par un algorithme convergent. On note $ x^\ast $ la limite de la suite $ (x_n)_{n \in \mathbb{N}} $ et on suppose que $ x_k \neq x^\ast $, pour tout $ k \in \mathbb{N} $. La convergence de l’algorithme est alors dite :
503 \begin{itemize}
504 \item linéaire si l'erreur décroît linéairement i.e. :
505 $$ \exists \tau \in ]0,1[ \ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}} = \tau $$
506 \item superlinéaire si :
507 $$ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}} = 0 $$
508 \item d'ordre $ p $ si :
509 $$ \exists \tau \geq 0 \ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}^p} = \tau $$
510 En particulier, si $ p = 2 $, la convergence est dite quadratique.
511 \end{itemize}
512\end{Def}
513L'étude plus détaillée de différents algorithmes de descente qui utilisent différentes méthodes de recherche linéaire pour optimiser $ \varphi $ ainsi que leurs convergences sort du cadre de ce projet.
8000c039
JB
514
515\section{Méthode Newtonienne}
516
e17152e0 517Les 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 :
8000c039
JB
518$$ \nabla J(x) = 0, $$
519autrement dit, les points critiques de la fonction $ J $ à minimiser.
520\newline
521En 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 :
522$$ x_{k+1} = x_k - H[J](x_k)^{-1} \nabla J(x_k), $$
682e0379
JB
523où $ 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 :
524$$ \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 $$
c207a96f 525Autrement dit, $ d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
a5f09ac4 526À 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 $.
7fd51f8b
JB
527\newline
528Les propriétés remarquables de cet algorithme sont :
682e0379
JB
529
530\begin{tabular}{|p{20em}|p{20em}|}
531 \hline
532 Avantages & Inconvénients \\
533 \hline
534 sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). & \\
535 \hline
536 & 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. \\
537 \hline
538 & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $. \\
539 \hline
09448b62 540 & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la hessienne est singulière. \\
682e0379
JB
541 \hline
542 & pas de distinction entre minima, maxima et points stationnaires. \\
543 \hline
544\end{tabular}
545\newline
6079168f 546La 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 :
682e0379
JB
547$$ x_{k+1} = x_k - s_k H_k^{-1} \nabla J(x_k), $$
548
549\begin{itemize}
550 \item la matrice $ H_k $ est une approximation de la hessienne $ H[J](x_k) $.
551 \item $ s_k > 0 $ est le pas calculé par une recherche linéaire bien choisie.
552\end{itemize}
553Plusieurs questions se posent alors :
554\begin{itemize}
555 \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 ?
556 \item Comment conserver les bonnes propriétés de l’algorithme de Newton ?
557\end{itemize}
7fd51f8b 558Nous 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.
de30386e 559
8000c039 560\section{Méthode PQS (ou SQP)}
e37aec65 561
7590f4bb 562Nous 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 des multiplicateurs en travaillant sur un problème d’optimisation déduit du problème initial par \textit{dualité}.
682e0379 563
329ebbc2
JB
564\subsection{Problème quadratique sous contraintes linéaires}
565
566Nous introduisons les différentes approches développées pour la résolution des problèmes de programmation quadratique avec contraintes d'égalités et d’inégalités linéaires.
567\newline
568Ce type de problème quadratique se pose sous la forme :
569$$
570 \mathcal{PQ} \left \{
571 \begin{array}{l}
572 \displaystyle\min_{x \in \mathbb{R}^n} c^\top x + \frac{1}{2} x^\top \mathcal{Q} x \\
573 A^\top x + b \leq 0 \\
574 A^{\prime^\top} x + b^\prime = 0
575 \end{array}
576 \right .
577$$
578où $$ \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 $$
579Or
580$$ 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 $$
581Donc le problème se ramène à :
582
583\subsubsection{Algorithme 1}
584
585\subsubsection{Algorithme 2}
586
a5f09ac4 587\subsection{Algorithmes Newtoniens}
682e0379 588
6079168f 589Les 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} $.
682e0379
JB
590
591\subsection{Algorithme PQS}
592
593\subsubsection{Contraintes d’égalité}
594
595Considérons un problème d’optimisation différentiable $ \mathcal{P} $ avec contraintes d’égalité :
596$$
597 \mathcal{P} \left \{
7fd51f8b 598 \begin{array}{l}
682e0379
JB
599 \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
600 h(x) = 0
601 \end{array}
602 \right .
603$$
604où $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables.
605\newline
606Les conditions d’optimalité de Lagrange (ou \textit{KKT}) s’écrivent :
7fd51f8b 607$$ \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) = 0 \iff \nabla L(x,\lambda) = 0 $$
682e0379
JB
608donc $ \mathcal{P} $ devient :
609$$ \begin{pmatrix}
7fd51f8b 610 \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) \\
682e0379
JB
611 h(x)
612 \end {pmatrix} = 0 $$
613Pour résoudre ce système d’équations, utilisons la méthode de Newton dont une itération s’écrit ici :
7fd51f8b
JB
614$$ H[L](x_k,\lambda_k)\begin{pmatrix}
615 x_{k+1} - x_k \\
616 \lambda_{k+1} - \lambda_k
617 \end{pmatrix} = -\nabla L(x_k,\lambda_k) $$
618soit :
619$$ \begin{pmatrix}
620 H_x[L](x_k,\lambda_k) & D_h(x_k)^\top \\
621 D_h(x_k) & 0
622 \end{pmatrix} \begin{pmatrix}
623 x_{k+1} - x_k \\
624 \lambda_{k+1} - \lambda_k
625 \end{pmatrix} = -\begin{pmatrix}
626 \nabla_x L(x_k,\lambda_k) \\
627 h(x_k)
628 \end{pmatrix} $$
629où $ D_h(x) $ désigne la matrice jacobienne de l’application $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ définie par :
7590f4bb 630$$ D_h(x)^\top = \begin{bmatrix} \nabla h_1(x)^\top\ldots\nabla h_q(x)^\top \end{bmatrix} $$
7fd51f8b
JB
631Posons : $ 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 :
632$$ \begin{pmatrix}
633 H_k & D_h(x_k)^\top \\
634 D_h(x_k) & 0
635 \end{pmatrix} \begin{pmatrix}
636 d \\
637 \mu - \lambda_k
638 \end{pmatrix} = -\begin{pmatrix}
639 \nabla_x L(x_k,\lambda_k) \\
640 h(x_k)
641 \end{pmatrix} $$
642et est bien définie à condition que la matrice $ H_x[L](x_k,\lambda_k) $ soit inversible. Ce sera le cas si :
643\begin{enumerate}[label=(\roman*)]
7590f4bb 644 \item Les colonnes $ \nabla h_1(x_k)^\top,\ldots,\nabla h_q(x_k)^\top $ de $ D_h(x_k)^\top $ sont linéairement indépendants : c’est la condition première de \textit{KTT} ou condition de qualification des contraintes.
7fd51f8b
JB
645 \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é.
646\end{enumerate}
647Revenons à l’itération. Elle s’écrit encore :
648$$
649 \left \{
650 \begin{array}{r c l}
651 H_kd + \sum\limits_{i=1}^q(\mu_i - \lambda_{k_i})\nabla h_i(x_k) & = & -\nabla_x L(x_k,\lambda_k) \\
652 \nabla h_i(x_k)^\top d + h_i(x_k) & = & 0, \ \forall i \in \{1,\ldots,q\}
653 \end{array}
654 \right .
655$$
e17152e0 656Or $ \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ù :
7fd51f8b
JB
657$$
658 \left \{
659 \begin{array}{r c l}
660 H_kd + \sum\limits_{i=1}^q\mu_i\nabla h_i(x_k) & = & -\nabla J(x_k) \\
661 \nabla h_i(x_k)^\top d + h_i(x_k) & = & 0, \ \forall i \in \{1,\ldots,q\}
662 \end{array}
663 \right .
664$$
6079168f 665On reconnait dans le système ci-dessus les conditions d’optimalité de Lagrange du problème quadratique suivant :
7fd51f8b
JB
666$$
667 \mathcal{PQ}_k \left \{
668 \begin{array}{l}
669 \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
670 h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
671 \end{array}
672 \right .
673$$
674Le 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.
675\newline
676Comme 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 :
677
e17152e0
JB
678\hrulefill
679\newline
6079168f 680ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ.
e17152e0
JB
681\newline
682\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.
683\newline
684\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
685\begin{enumerate}
686 \item $ k := 0 $.
687 \item Tant que $ \norme{\nabla L(x_k,\lambda_k)} > \varepsilon $,
688 \begin{enumerate}
689 \item Résoudre le sous-problème quadratique :
690 $$
691 \mathcal{PQ}_k \left \{
692 \begin{array}{l}
693 \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
694 h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
695 \end{array}
696 \right .
697 $$
698 et obtenir la solution primale $ d_k $ et le multiplicateur $ \lambda^{\prime} $ associé à la contrainte d’égalité.
699 \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ k := k + 1 $.
700 \end{enumerate}
701 \item Retourner $ x_k $.
702\end{enumerate}
703
704\hrulefill
705
7fd51f8b 706\subsubsection{Contraintes d’inégalité}
682e0379 707
e17152e0
JB
708Intéressons nous maintenant aux problèmes avec contraintes d’égalité et d’inégalité :
709$$
710 \mathcal{P} \left \{
711 \begin{array}{l}
712 \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
713 g(x) \leq 0 \\
714 h(x) = 0
715 \end{array}
716 \right .
717$$
718où $ 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.
719\newline
7590f4bb 720Selon le même principe qu’avec contraintes d’égalité seules, on linéarise les contraintes et on utilise une approximation quadratique du Lagrangien à l'aide de développements de Taylor-Young en $ x_k $ et $ (x_k,\lambda_k,\mu_k) $ respectivement :
e17152e0 721$$ 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 $$
7590f4bb
JB
722Soit à l'ordre 2 pour le Lagrangien :
723$$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$
724et à l'ordre 1 pour les contraintes :
725$$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
726$$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
727En 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 $ :
e17152e0
JB
728
729\hrulefill
730\newline
e173772d 731ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.
e17152e0
JB
732\newline
733\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.
734\newline
735\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
736\begin{enumerate}
737 \item $ k := 0 $.
738 \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $,
739 \begin{enumerate}
740 \item Résoudre le sous-problème quadratique :
741 $$
742 \mathcal{PQ}_k \left \{
743 \begin{array}{l}
744 \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
e173772d 745 g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\} \\
e17152e0
JB
746 h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
747 \end{array}
748 \right .
749 $$
750 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.
751 \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $.
752 \end{enumerate}
753 \item Retourner $ x_k $.
754\end{enumerate}
755
756\hrulefill
757\newline
758Afin 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.
759\newline
760Etant 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.
761
7590f4bb
JB
762\subsection{Stratégie d'approximation de la hessienne}
763
764\subsubsection{Équation de sécante et approximation}
765
766L'approximation $ H_k $ de la hessienne du Lagrangien peut être obtenu par la relation :
767$$ \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) \approx H[L](x_{k+1},\lambda_{k+1},\mu_{k+1})(x_{k+1} - x_k) $$
768On construit une approximation $ H_{k+1} $ de $ H[L](x_{k+1},\lambda_{k+1},\mu_{k+1}) $ comme solution de l’équation :
769$$ H_{k+1}(x_{k+1} - x_k) = \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) $$
770appelée équation de sécante ou équation de quasi-Newton.
771\newline
772De façon similaire, on peut construire une approximation $ B_{k+1} $ de $ H[L](x_{k+1},\lambda_{k+1},\mu_{k+1})^{-1} $ comme solution de l’équation :
773$$ B_{k+1}(\nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1})) = x_{k+1} - x_k $$
774Dans les deux cas, les équations de quasi-Newton forment un système sous-déterminé à $ n $ équations et $ n^2 $ inconnues. Il existe donc une infinité de matrices $ H_{k+1} $ pouvant convenir.
775\newline
776Une 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 :
777$$ H_{k+1} = H_k + U_k $$
1be1955b
JB
778% \subsubsection{Mises à jour DFP et BFGS}
779Les méthodes de mise à jour DFP et BFGS suivent par exemple cette stratégie.
7590f4bb
JB
780
781\subsection{Exemple d'utilisation de PQS}
782
783Considérons le problème $ \mathcal{P} $ suivant :
784$$
785 \mathcal{P} \left \{
786 \begin{array}{l}
787 \displaystyle\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2 \\
788 g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 \\
789 \end{array}
790 \right .
791$$
e173772d 792où $$ (r,r_1,r_2) \in \mathbb{R}_+^{*^3} \land r < r_1 \land r < r_2. $$
84af1fe2 793\textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $ la précision, $ (x_0,y_0,z_0) = $ point initial et $ (\lambda_{0_1},\lambda_{0_2}) = $ multiplicateur initial.
7590f4bb 794\newline
84af1fe2 795Le Lagrangien $ L $ de $ \mathcal{P} $ : $$ L((x,y,z),(\lambda_1,\lambda_2)) = x^2 + y^2 + z^2 -r^2 + \lambda_1(x^2 + y^2 - r_1^2) + \lambda_2(x^2 + z^2 -r_2^2). $$
7590f4bb 796\newline
84af1fe2 797Le gradient de $ J $ : $$ \nabla J(x,y,z) = (\frac{\partial J}{\partial x}(x,y,z),\frac{\partial J}{\partial y}(x,y,z),\frac{\partial J}{\partial z}(x,y,z)) = (2x,2y,2z). $$
7590f4bb 798\newline
b8e1f3f6 799Le gradient de $ g $ : $$ \nabla g(x,y,z) = (\nabla g_1(x,y,z),\nabla g_2(x,y,z)) $$
84af1fe2
JB
800$$ = ((\frac{\partial g_1}{\partial x}(x,y,z),\frac{\partial g_1}{\partial y}(x,y,z),\frac{\partial g_1}{\partial z}(x,y,z)),(\frac{\partial g_2}{\partial x}(x,y,z),\frac{\partial g_2}{\partial y}(x,y,z),\frac{\partial g_2}{\partial z}(x,y,z)) $$
801$$ = ((2x,2y,0),(2x,0,2z)). $$
7590f4bb 802\newline
84af1fe2
JB
803Le gradient du Lagrangien $ L $ :
804$$ \nabla L((x,y,z),(\lambda_1,\lambda_2)) = \nabla J(x,y,z) + \lambda_1 \nabla g_1(x,y,z) + \lambda_2 \nabla g_2(x,y,z)) $$
805\newline
806La matrice hessienne de $ J $ : $$ H[J](x,y,z) =
7590f4bb 807 \begin{pmatrix}
46973afb
JB
808 \frac{\partial^2 J}{\partial^2 x}(x,y,z) & \frac{\partial^2 J}{\partial x\partial y}(x,y,z) & \frac{\partial^2 J}{\partial x\partial z}(x,y,z) \\
809 \frac{\partial^2 J}{\partial y\partial x}(x,y,z) & \frac{\partial^2 J}{\partial^2 y}(x,y,z) & \frac{\partial^2 J}{\partial y\partial z}(x,y,z) \\
810 \frac{\partial^2 J}{\partial z\partial x}(x,y,z) & \frac{\partial^2 J}{\partial z\partial y}(x,y,z) & \frac{\partial^2 J}{\partial^2 z}(x,y,z) \\
7590f4bb
JB
811 \end{pmatrix} =
812 \begin{pmatrix}
84af1fe2
JB
813 2 & 0 & 0 \\
814 0 & 2 & 0 \\
815 0 & 0 & 2 \\
816 \end{pmatrix} = 2Id_{\mathbb{R}^3} $$
329ebbc2 817On en déduit que $ H[J](x,y,z) $ est inversible et que $ H[J](x,y,z)^{-1} = \frac{1}{2}Id_{\mathbb{R}^3} $.
7590f4bb 818
9862be00 819\newpage
b8e1f3f6 820
a11e6dde 821\subsection{Trace d'éxécution de l'algorithme PQS}
b8e1f3f6 822
a11e6dde
JB
823\begin{center}
824 \includegraphics[scale=0.2]{sphere2.jpg} \\
825 \footnotesize{
826 \small \it Fig : Exemple de la sphère \\
827 \vspace*{0.5cm}
828 }
9862be00 829\end{center}
e173772d 830
a11e6dde 831En utilisant le problème $ \mathcal{P} $ précédent :
e173772d 832
a11e6dde 833\textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $, $ (x_0,y_0,z_0) = (100, 100 ,0)$ et $(\lambda_{0_1},\lambda_{0_2}) = (1 , 1)$, les rayons : $r = 100$ et $r_1 = r_2 = 10$.
b8e1f3f6 834\newline
a11e6dde 835Calcul du Lagrangien $ L $ de $ \mathcal{P} $ en $(x_0,y_0,z_0)$ :
e173772d 836\newline
a11e6dde
JB
837$ L((100,100,0),(1,1)) = 100^2 + 100^2 + 0^2 -100^2 + 1 * (100^2 +100^2 - 10^2) + 1 * (100^2 + 100^2 -10^2). $
838$ L((100,100,0),(1,1)) = 1000 + 1000 - 1000 + (1000 + 1000 - 100) + (1000 + 1000 -100). $
839$ L((100,100,0),(1,1)) = 4800. $
e173772d 840
70b2e2fc 841\newpage
4b8b7ee7 842
a11e6dde
JB
843% \begin{algorithmfloat}[#Algo 1]
844\begin{algorithm}
845 \caption {Trace d'éxécution de l'algorithme PQS}
846 \begin{algorithmic}
847 \REQUIRE $g(x_0,y_0,z_0)\leq 0$, $(x_0,y_0,z_0) = (10, 10 ,10)$
848 \ENSURE $\displaystyle\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2$ and \newline $g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 $
849 \STATE \textbf{Data :}
850 \STATE $k \leftarrow 0, (x_k, y_k, z_k) \leftarrow (100, 100, 0), r \leftarrow 100$
851 \STATE $r_1 = r_2 \leftarrow 10, \varepsilon \leftarrow 0.01$
1be1955b 852 \STATE $\lambda_1 = \lambda_2 \leftarrow 1$
a11e6dde
JB
853 \STATE $ H[J](x,y,z)^{-1} \leftarrow
854 \begin{pmatrix}
855 0.5 & 0 & 0 \\
856 0 & 0.5 & 0 \\
857 0 & 0 & 0.5 \\
858 \end{pmatrix} $
859 \newline
860 \STATE {//Calcul des deux composantes du gradient de $ g $: }
861 \STATE $ \nabla g_1(x_k,y_k,z_k) = ((2x_k,2y_k,0)$ \hfill $ //résultat : (20, 20, 0)$
862 \STATE $ \nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k))$ \hfill $ //résultat : (20, 0, 20)$
863 \STATE $ \nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
864 \newline
865
866 \WHILE{$ (\norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $ or k $ \leq 10)$}
867
868 \STATE {//Première itération :}
869 \STATE{//Calcul du gradient de $ J $ :}
870 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (100,100,0) $
871 \newline
872 \STATE {//Calcul du gradient de $ L $ : }
873 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (220, 220, 40)$
874 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
875 % \STATE $ \nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = (x_L , y_L, z_L) $
876 \newline
877 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
878 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(50,50,0))$
879 \newline
880 \STATE {//Calcul des nouvelles valeurs des coordonnées}
881 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (50,50,0)$
882 \newline
883 \STATE {//Incrémentation de $ k $}
884 \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 1$
885 \newline
886
887 \STATE {//Deuxième itération :}
888 \STATE{//Calcul du gradient de $ J $ :}
889 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (100,100,0) $
890 \newline
891 \STATE {//Calcul du gradient de $ L $ : }
892 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (120, 120, 0)$
893 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
894 \newline
895 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
896 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(25,25,0))$
897 \STATE {//Calcul des nouvelles valeurs des coordonnées}
898 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (25,25,0)$
899 \newline
900 \STATE {//Incrémentation de $ k $ }
901 \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 2$
902 \newline
903
904 \STATE {//Troisième itération :}
905 \STATE{//Calcul du gradient de $ J $ :}
906 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (50,50,0) $
907 \newline
908 \STATE {//Calcul du gradient de $ L $ : }
909 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (70, 70, 0)$
910 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
911 \newline
912 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
913 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(12.5,12.5,0))$
914 \STATE {//Calcul des nouvelles valeurs des coordonnées}
915 \newline
916 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (12.5,12.5,0)$
917 \STATE {//Incrémentation de $ k $}
918 \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 3$
919 \newline
920
921 \STATE {//Quatrième itération :}
922 \STATE{//Calcul du gradient de $ J $ :}
923 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (25,25,0) $
924 \newline
925 \STATE {//Calcul du gradient de $ L $ : }
926 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (45, 45, 0)$
927 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
928 \newline
929 \STATE {//Calcule de la direction de la pente $ d_k $ (méthode de Newton) :}
930 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(6.25,6.25,0))$
931 \newline
932 \STATE {//Calcul des nouvelles valeurs des coordonnées}
933 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (6.25,6.25,0)$
934 \STATE {//Incrémentation de $ k $}
935 \newline
936 \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 4$
937 \STATE $ $
938 \newline
939
940 \STATE {//Cinquième itération :}
941 \STATE{//Calcul du gradient de $ J $ :}
942 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (12.5,12.5,0) $
943 \newline
944 \STATE {//Calcul du gradient de $ L $ : }
945 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (32.5, 32.5, 0)$
946 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
947 \newline
948 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
949 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(3.125,3.125,0))$
950 \newline
951 \STATE {//Calcul des nouvelles valeurs des coordonnées}
952 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (3.125,3.125,0)$
953 \newline
954 \STATE {//Incrémentation de $ k $}
955 \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 5$
956 \newline
957
958 \STATE {//Sixième itération :}
959 \STATE{//Calcul du gradient de $ J $ :}
960 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (6.25,6.25,0) $
961 \newline
962 \STATE {//Calcul du gradient de $ L $ : }
963 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (26.25, 26.25, 0)$
964 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
965 \newline
966 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
967 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(1.5625,1.5625,0))$
968 \STATE {//Calcul des nouvelles valeurs des coordonnées}
969 \newline
970 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (1.5625,1.5625,0)$
971 \STATE {//Incrémentation de $ k $}
972 \newline
973 \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 6$
974 \newline
975
976 \STATE {//Septième itération :}
977 \STATE{//Calcul du gradient de $ J $ :}
978 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (3.125, 3.125, 0) $
979 \newline
980 \STATE {//Calcul du gradient de $ L $ : }
981 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (23.125, 23.125, 0)$
982 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
983 \newline
984 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
985 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.78125,0.78125,0))$
986 \STATE {//Calcul des nouvelles valeurs des coordonnées}
987 \newline
988 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0.78125,0.78125,0)$
989 \STATE {//Incrémentation de $ k $}
990 \newline
991 \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 7$
992 \newline
993
994 \STATE {//Huitième itération :}
995 \STATE{//Calcul du gradient de $ J $ :}
996 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (1.5625, 1.5625, 0) $
997 \newline
998 \STATE {//Calcul du gradient de $ L $ : }
999 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (21.5625, 21.5625, 0)$
1000 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
1001 \newline
1002 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
1003 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.390625,0.390625,0))$
1004 \newline
1005 \STATE {//Calcul des nouvelles valeurs des coordonnées}
1006 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.390625,0.390625,0)$
1007 \newline
1008 \STATE {//Incrémentation de $ k $}
1009 \STATE $ k \leftarrow k + 1$ \hfill $ //résulat : k = 8$
1010 \newline
1011
1012 \STATE {//Neuvième itération :}
1013 \STATE{//Calcul du gradient de $ J $ :}
1014 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (0.78125, 0.78125, 0) $
1015 \newline
1016 \STATE {//Calcul du gradient de $ L $ : }
1017 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (20.78125, 20.78125, 0)$
1018 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
1019 \newline
1020 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
1021 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.1953125,0.1953125,0))$
1022 \newline
1023 \STATE {//Calcul des nouvelles valeurs des coordonnées}
1024 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0.1953125,0.1953125,0)$
1025 \newline
1026 \STATE {//Incrémentation de $ k $}
1027 \STATE $ k \leftarrow k + 1 \hfill //résultat : k = 9$
1028 \newline
1029
1030 \STATE {//Dixième itération :}
1031 \STATE{//Calcul du gradient de $ J $ :}
1032 \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (0.390625, 0.390625, 0) $
1033 \newline
1034 \STATE {//Calcul du gradient de $ L $ : }
1035 \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $//résultat : (20.390625, 20.390625, 0)$
1036 \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
1037 \newline
1038 \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
1039 \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.097665625,0.097665625,0))$
1040 \newline
1041 \STATE {//Calcul des nouvelles valeurs des coordonnées}
1042 \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0.097665625,0.097665625,0)$
1043 \newline
1044 \STATE {//Incrémentation de $ k $}
1045 \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 10$
1046 \newline
1047 \STATE {//Fin de la boucle "while" car nous avons atteint $ k = 10 $, condition mettant fin à la //boucle}
1048 \newline
1049
1050 \ENDWHILE
1051
1052 \end{algorithmic}
1053 % \end{algorithmfloat}
1054\end{algorithm}
b8e1f3f6 1055
e37aec65
JB
1056\bibliographystyle{plain}
1057\bibliography{stdlib_sbphilo}
1058
1059%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1060
1061\end{document}