Commit | Line | Data |
---|---|---|
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} | |
23 | ||
24 | ||
25 | %%%%%Marges & en-t\^etes | |
26 | ||
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 | |
66a4e4ad | 33 | \renewcommand{\footrulewidth}{0.2pt} % filet en bas |
e37aec65 JB |
34 | |
35 | ||
36 | %%%%%Th\'eor\`eme et d\'efinitions | |
37 | ||
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} | |
44 | ||
66a4e4ad | 45 | \newcommand{\norme}[1]{\left\Vert #1\right\Vert} |
e37aec65 JB |
46 | |
47 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
48 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
49 | ||
50 | \begin{document} | |
51 | ||
52 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
53 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
54 | ||
55 | %%%%%Page de garde | |
56 | ||
57 | \begin{center} | |
58 | ||
b0927d0a | 59 | %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\ |
cec1e8f8 | 60 | \includegraphics[scale=0.5]{polytech.png}\\ |
b0927d0a JB |
61 | |
62 | \vspace*{0.5cm} | |
63 | ||
64 | \footnotesize{ | |
65 | \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\ | |
66 | \large \bf 5ème année\\ | |
67 | } | |
68 | ||
69 | \vspace*{0.5cm} | |
70 | ||
71 | %\large{Master 2 Professionnel\\ | |
72 | %Math\'ematiques et Informatique des Nouvelles Technologies\\} | |
73 | ||
74 | \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\} | |
75 | ||
76 | \vspace*{0.7cm} | |
77 | ||
78 | \begin{tabular}{c} | |
79 | \hline | |
9f054a9c JB |
80 | ~ \\ |
81 | \LARGE\textbf {Programmation Séquentielle Quadratique ou PQS} \\ | |
82 | \LARGE\textbf {en} \\ | |
83 | \LARGE\textbf {Optimisation non linéraire sous contraintes} \\ | |
84 | ~ \\ | |
b0927d0a JB |
85 | \hline |
86 | \end{tabular} | |
87 | ||
88 | \vspace*{0.7cm} | |
89 | ||
90 | \includegraphics[scale=0.4]{CE.PNG}\\ | |
91 | ||
92 | \vspace*{0.5cm} | |
93 | ||
94 | \large par\\ | |
95 | ||
96 | %\large \bsc{}\\ | |
97 | %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\ | |
98 | ||
99 | \vspace*{0.2cm} | |
91df3de1 | 100 | \large {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\ |
b0927d0a JB |
101 | |
102 | %\vspace*{0.1cm} | |
103 | ||
104 | % \large sous la direction de \\ | |
105 | ||
106 | %\vspace*{0.1cm} | |
107 | ||
108 | %Eric Audureau et Thierry Masson | |
109 | ||
110 | %\vspace*{1cm} | |
111 | ||
112 | \vspace*{1cm} | |
113 | ||
114 | %\normalsize{Licence de Mathématiques 3ème année} | |
115 | \normalsize{Année 2018-2019} | |
e37aec65 JB |
116 | |
117 | \end{center} | |
118 | ||
119 | \thispagestyle{empty} | |
120 | ||
121 | \newpage | |
122 | ||
123 | ||
124 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
125 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
126 | ||
127 | ||
128 | \pagestyle{plain} | |
129 | \frontmatter | |
130 | ||
131 | ||
132 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
133 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
134 | ||
135 | ||
e37aec65 JB |
136 | %%%%%Table des mati\`eres |
137 | ||
138 | \tableofcontents | |
139 | ||
140 | \begin{figure}[!b] | |
b0927d0a JB |
141 | \begin{center} |
142 | %\includegraphics{logo_fac2} | |
143 | \includegraphics[scale=0.04]{amu} | |
144 | \end{center} | |
e37aec65 JB |
145 | \end{figure} |
146 | ||
147 | \newpage | |
148 | ||
149 | ||
150 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
151 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
152 | ||
153 | ||
154 | \mainmatter | |
155 | \pagestyle{fancy} | |
156 | ||
157 | ||
158 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
159 | \chapter{Introduction générale} | |
160 | ||
8000c039 JB |
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. |
162 | \newline | |
163 | Elle est loin d'être exhaustive mais devrait suffire dans le cadre de ce projet. | |
164 | ||
e37aec65 JB |
165 | \vspace{.5em} |
166 | ||
167 | \section{Qu'est-ce que la recherche opérationnelle?} | |
168 | ||
64f7c064 JB |
169 | \subsection{Présentation rapide} |
170 | ||
f899c72b | 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). |
e7e85554 | 172 | \newline |
f899c72b | 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. |
91df3de1 | 174 | |
64f7c064 JB |
175 | \subsection{Définition de la problèmatique} |
176 | ||
f899c72b | 177 | Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la recherche opérationnelle : |
6ec0df37 | 178 | \begin{Def} |
5e4341d1 JB |
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}$. |
180 | \newline | |
181 | La problèmatique $ \mathcal{P} $ se définit par : | |
182 | $$ | |
aa023e1c | 183 | \mathcal{P} \left \{ |
8000c039 | 184 | \begin{array}{r} |
aa023e1c JB |
185 | \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\ |
186 | g(x) \leq 0 \\ | |
187 | h(x) = 0 | |
188 | \end{array} | |
189 | \right . | |
5e4341d1 | 190 | $$ |
6ec0df37 | 191 | \end{Def} |
6ec0df37 | 192 | \begin{Def} |
5e4341d1 JB |
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 \} $$ | |
6ec0df37 | 195 | \end{Def} |
3b344e8c | 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} $. |
64f7c064 | 197 | |
e37aec65 JB |
198 | \section{Qu'est-ce que l'optimisation?} |
199 | ||
f899c72b JB |
200 | \subsection{Définition} |
201 | ||
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. | |
203 | \newline | |
8a00a107 | 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. |
f899c72b JB |
205 | |
206 | \subsection{Quelques définitions annexes} | |
207 | ||
208 | Définissons quelques notions supplémentaires de base nécessaires à la suite : | |
209 | \begin{Def} | |
9f054a9c JB |
210 | Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $. |
211 | \newline | |
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} $. | |
f899c72b | 213 | \end{Def} |
9f054a9c JB |
214 | \begin{Rmq} |
215 | $ A \subset \mathbb{R}^n $ est un ouvert $ \iff A = \mathring{A} $. | |
216 | \end{Rmq} | |
f899c72b | 217 | \begin{Def} |
9f054a9c JB |
218 | Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $. |
219 | \newline | |
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} $. | |
f899c72b | 221 | \end{Def} |
9f054a9c JB |
222 | \begin{Rmq} |
223 | $ A \subset \mathbb{R}^n $ est un fermé $ \iff A = \overline{A} $. | |
224 | \end{Rmq} | |
f899c72b | 225 | \begin{Def} |
9f054a9c JB |
226 | Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $. |
227 | \newline | |
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 $$ | |
f899c72b | 230 | \end{Def} |
d17ef079 JB |
231 | \begin{Def} |
232 | Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $. | |
233 | \newline | |
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 $. | |
237 | \newline | |
238 | Dans ce cas on note | |
239 | $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$ | |
240 | cette dérivée. | |
241 | \end{Def} | |
66a4e4ad JB |
242 | \begin{Def} |
243 | Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ | |
244 | et $ x^\ast, h \in \mathbb{R}^n $. | |
d17ef079 | 245 | \newline |
66a4e4ad JB |
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 |
247 | \[ | |
248 | f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h}) | |
249 | \] | |
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 | |
252 | \[ | |
253 | f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h) | |
254 | \] | |
d17ef079 | 255 | On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $. |
66a4e4ad | 256 | \end{Def} |
d17ef079 JB |
257 | \begin{Rmq} |
258 | On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$. | |
259 | \end{Rmq} | |
5e4341d1 JB |
260 | \begin{Def} |
261 | Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable. | |
262 | \newline | |
263 | Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par : | |
264 | \[ | |
de30386e | 265 | \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast)) |
5e4341d1 JB |
266 | \] |
267 | \end{Def} | |
d17ef079 JB |
268 | \begin{Rmq} |
269 | $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $ | |
270 | \end{Rmq} | |
9f054a9c JB |
271 | \begin{Def} |
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 : | |
274 | $$ H[f](x^\ast) = | |
275 | \begin{pmatrix} | |
276 | \frac{\partial^2 f}{\partial x_1^2}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n}(x^\ast) \\ | |
277 | \vdots & & \vdots \\ | |
278 | \frac{\partial^2 f}{\partial x_n\partial x_1}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_n^2}(x^\ast) | |
279 | \end{pmatrix} $$ | |
280 | \end{Def} | |
281 | \begin{Prop} | |
282 | \begin{enumerate} | |
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 $. | |
287 | \end{enumerate} | |
288 | \end{Prop} | |
f899c72b JB |
289 | |
290 | \subsection{Conditions d'existence d'un extremum} | |
291 | ||
3b344e8c JB |
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] | |
9f054a9c JB |
295 | Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue. |
296 | \newline | |
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} $. | |
299 | \newline | |
300 | De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $. | |
3b344e8c | 301 | \end{Th} |
8000c039 | 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}. |
b6cd6632 | 303 | |
3b344e8c JB |
304 | \subsection{Conditions de caractérisation d'un extremum} |
305 | ||
9f054a9c | 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}. |
f899c72b | 307 | \newline |
9f054a9c | 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}. |
f899c72b | 309 | |
8000c039 | 310 | \subsubsection{Conditions de Karuch-Kuhn-Tucker}\label{KKT} |
f899c72b JB |
311 | |
312 | \begin{Th} | |
9f054a9c JB |
313 | Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $. |
314 | \newline | |
315 | Les conditions nécessaires pour que $ x^\ast \in \mathcal{C}$ soit un minimum local de $ J $ sont : | |
316 | \newline | |
317 | \newline | |
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.} | |
319 | \newline | |
320 | \newline | |
321 | et | |
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. | |
f899c72b | 324 | \end{Th} |
8000c039 | 325 | \begin{proof} |
9f054a9c | 326 | Elle repose sur le lemme de Farkas \cite{FEA,RON}. |
8000c039 JB |
327 | \end{proof} |
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. | |
329 | ||
330 | ||
331 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
332 | ||
333 | \chapter{Méthode de programmation quadratique séquentielle} | |
334 | ||
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. | |
336 | ||
337 | \vspace{.5em} | |
338 | ||
339 | \section{Methode de descente}\label{descente} | |
340 | ||
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 : | |
9f054a9c | 342 | $$ x_{k+1} = x_k + s_kd_k $$ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $ et avec |
8000c039 JB |
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}. | |
345 | ||
346 | \subsection{Définition d'une direction de descente} | |
347 | ||
9f054a9c | 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 : |
8000c039 JB |
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- | |
351 | tions. | |
352 | \begin{Prop} | |
9f054a9c JB |
353 | Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $. |
354 | \newline | |
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 $$ | |
357 | De plus | |
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) $$ | |
8000c039 JB |
359 | \end{Prop} |
360 | \begin{proof} | |
9f054a9c | 361 | Elle s'effectue en utilisant le développement de Taylor-Young de l’application $ t \longmapsto f(x_0 + td) $ à l’ordre 1. |
8000c039 JB |
362 | \end{proof} |
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 : | |
365 | ||
366 | \hrulefill | |
367 | \newline | |
368 | ALGORITHME DE DESCENTE MODÈLE. | |
369 | \newline | |
370 | \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire. | |
371 | \newline | |
372 | \textit{Sortie}: une approximation de la solution du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $. | |
373 | \begin{enumerate} | |
374 | \item $ k := 0 $ | |
375 | \item Tant que "test d’arrêt" non satisfait, | |
9f054a9c JB |
376 | \begin{enumerate} |
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 $. | |
380 | \end{enumerate} | |
381 | \item Retourner $ x_k $. | |
8000c039 JB |
382 | \end{enumerate} |
383 | ||
384 | \hrulefill | |
385 | ||
386 | \subsection{Choix de la direction de descente} | |
387 | ||
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 | |
390 | descente : | |
391 | \begin{itemize} | |
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}. | |
394 | \end{itemize} | |
9f054a9c | 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. |
8000c039 JB |
396 | |
397 | \subsection{Critère d’arrêt} | |
398 | ||
9f054a9c | 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 $. |
f899c72b | 400 | \newline |
8000c039 JB |
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 $. | |
404 | ||
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. | |
409 | ||
410 | En pratique, le test d’optimalité n’est pas toujours satisfait et on devra faire appel à | |
9f054a9c | 411 | d’autres critères fondés sur l’expérience du numérique : |
8000c039 JB |
412 | \begin{itemize} |
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 $. | |
416 | \end{itemize} | |
417 | et généralement une combinaison de ces critères : | |
de30386e | 418 | \newline |
8000c039 JB |
419 | \newline |
420 | Critère d’arrêt = | |
421 | \begin{tabular}{l} | |
9f054a9c | 422 | Test d’optimalité satisfait \\ |
8000c039 JB |
423 | OU (Stagnation de la valeur courante ET Stagnation de la solution) \\ |
424 | OU Nombre d’itérations maximum autorisé dépassé | |
425 | \end{tabular} | |
6ec0df37 | 426 | |
8000c039 | 427 | \subsection{La recherche linéaire} |
e37aec65 | 428 | |
8000c039 JB |
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. |
430 | \newline | |
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. | |
436 | ||
437 | \hrulefill | |
438 | \newline | |
439 | RECHERCHE LINÉAIRE : PAS FIXE. $ s_k = s_{k-1} $ | |
440 | ||
441 | \hrulefill | |
442 | ||
443 | \hrulefill | |
444 | \newline | |
445 | RECHERCHE LINÉAIRE : PAS OPTIMAL. $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $ | |
e37aec65 | 446 | |
8000c039 JB |
447 | \hrulefill |
448 | \newline | |
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. | |
458 | \begin{Def} | |
459 | On appelle $ \varphi : s \in \mathbb{R} \longmapsto J(x + sd)$ la fonction mérite associée à $ J $ en $ x $. | |
460 | \end{Def} | |
461 | \begin{Def} | |
9f054a9c | 462 | Dans le cas où $ J $ est différentiable sur $ \mathcal{C} $, on dit que un algorithme de descente converge ssi |
8000c039 JB |
463 | $$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$ |
464 | \end{Def} | |
465 | ||
466 | \subsubsection{Principe de démonstration de convergence} | |
de30386e | 467 | |
8000c039 JB |
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 | |
470 | type : | |
471 | $$ J(x_k) - J(x_{k+1}) \geq c\norme{\nabla J(x_k)}^2, $$ | |
472 | où $ c $ est un constante réelle. | |
473 | \newline | |
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 $$ | |
9f054a9c | 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 : |
8000c039 JB |
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. | |
479 | ||
480 | \section{Méthode Newtonienne} | |
481 | ||
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. | |
487 | \newline | |
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. | |
de30386e | 491 | |
8000c039 | 492 | \section{Méthode PQS (ou SQP)} |
e37aec65 | 493 | |
e37aec65 JB |
494 | \bibliographystyle{plain} |
495 | \bibliography{stdlib_sbphilo} | |
496 | ||
497 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | |
498 | ||
499 | \end{document} |