rapport/ProjetOptimRO.tex

   1 \documentclass[12pt,oneside,a4paper]{book}
   2
   3
   4 %%%%%Packages
   5
   6
   7 \usepackage{latexsym}
   8 \usepackage{amsmath}
   9 \usepackage{mathtools}
  10 \usepackage{amssymb}
  11 \usepackage[utf8]{inputenc}
  12 \usepackage[francais]{babel}
  13 \usepackage{color}
  14 \usepackage{geometry}
  15 \usepackage{graphicx}
  16 \usepackage{amsfonts}
  17 \usepackage[T1]{fontenc}
  18 \usepackage{multirow}
  19 \usepackage{fancyhdr}
  20 \usepackage{tocbibind}
  21 \usepackage{lmodern}
  22
  23
  24 %%%%%Marges & en-t\^etes
  25
  26 \geometry{hmargin=2.3cm, vmargin=3cm}
  27 \fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis
  28 \fancyhead[FC]{\bfseries\thepage} % N∞page centre bas
  29 \fancyhead[HC]{\footnotesize\leftmark} % chapitre centre haut
  30 \renewcommand{\headrulewidth}{0.2pt} % filet en haut
  31 \addtolength{\headheight}{0.5pt} % espace pour le filet
  32 \renewcommand{\footrulewidth}{0.2pt} % filet en bas
  33
  34
  35 %%%%%Th\'eor\`eme et d\'efinitions
  36
  37 \newtheorem{Def}{D\'efinition}
  38 \newtheorem{Not}[Def]{Notation}
  39 \newtheorem{Th}{Th\'eor\`eme}
  40 \newtheorem{Prop}[Th]{Proposition}
  41 \newtheorem{Cor}[Th]{Corollaire}
  42 \newtheorem{Rmq}{Remarque}
  43
  44 \newcommand{\norme}[1]{\left\Vert #1\right\Vert}
  45
  46 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  47 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  48
  49 \begin{document}
  50
  51 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  52 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  53
  54 %%%%%Page de garde
  55
  56 \begin{center}
  57
  58  %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\
  59  \includegraphics[scale=0.5]{polytech.png}\\
  60
  61  \vspace*{0.5cm}
  62
  63  \footnotesize{
  64   \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\
  65   \large \bf  5ème année\\
  66  }
  67
  68  \vspace*{0.5cm}
  69
  70  %\large{Master 2 Professionnel\\
  71  %Math\'ematiques et Informatique des Nouvelles Technologies\\}
  72
  73  \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\}
  74
  75  \vspace*{0.7cm}
  76
  77  \begin{tabular}{c}
  78   \hline
  79   ~                                                           \\
  80   \LARGE\textbf {Programmation Séquentielle Quadratique}      \\
  81   \LARGE\textbf {en}                                          \\
  82   \LARGE\textbf {Optimisation non linéraire sous contraintes} \\
  83   ~                                                           \\
  84   \hline
  85  \end{tabular}
  86
  87  \vspace*{0.7cm}
  88
  89  \includegraphics[scale=0.4]{CE.PNG}\\
  90
  91  \vspace*{0.5cm}
  92
  93  \large par\\
  94
  95  %\large  \bsc{}\\
  96  %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\
  97
  98  \vspace*{0.2cm}
  99  \large  {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\
 100
 101  %\vspace*{0.1cm}
 102
 103  % \large sous la direction de \\
 104
 105  %\vspace*{0.1cm}
 106
 107  %Eric Audureau et Thierry Masson
 108
 109  %\vspace*{1cm}
 110
 111  \vspace*{1cm}
 112
 113  %\normalsize{Licence de Mathématiques 3ème année}
 114  \normalsize{Année 2018-2019}
 115
 116 \end{center}
 117
 118 \thispagestyle{empty}
 119
 120 \newpage
 121
 122
 123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 124 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 125
 126
 127 \pagestyle{plain}
 128 \frontmatter
 129
 130
 131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 133
 134
 135 %%%%%Table des mati\`eres
 136
 137 \tableofcontents
 138
 139 \begin{figure}[!b]
 140  \begin{center}
 141   %\includegraphics{logo_fac2}
 142   \includegraphics[scale=0.04]{amu}
 143  \end{center}
 144 \end{figure}
 145
 146 \newpage
 147
 148
 149 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 150 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 151
 152
 153 \mainmatter
 154 \pagestyle{fancy}
 155
 156
 157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 158 \chapter{Introduction générale}
 159
 160 \vspace{.5em}
 161
 162 \section{Qu'est-ce que la recherche opérationnelle?}
 163
 164 \subsection{Présentation rapide}
 165
 166 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).
 167 \newline
 168 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.
 169
 170 \subsection{Définition de la problèmatique}
 171
 172 Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la recherche opérationnelle :
 173 \begin{Def}
 174  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}$.
 175  \newline
 176  La problèmatique $ \mathcal{P} $ se définit par :
 177  $$
 178   \mathcal{P} \left \{
 179   \begin{array}{r c l}
 180    \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
 181    g(x) \leq 0                                 \\
 182    h(x) = 0
 183   \end{array}
 184   \right .
 185  $$
 186 \end{Def}
 187 \begin{Def}
 188  On définit $ \mathcal{C} $ l'ensemble des contraintes par :
 189  $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$
 190 \end{Def}
 191 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} $.
 192
 193 \section{Qu'est-ce que l'optimisation?}
 194
 195 \subsection{Définition}
 196
 197 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.
 198 \newline
 199 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.
 200
 201 \subsection{Quelques définitions annexes}
 202
 203 Définissons quelques notions supplémentaires de base nécessaires à la suite :
 204 \begin{Def}
 205 Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
 206 \newline
 207 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} $.
 208 \end{Def}
 209 \begin{Def}
 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{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} $.
 213 \end{Def}
 214 \begin{Def}
 215 Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $.
 216 \newline
 217 On dit que $ f $ est continue en $ x^\ast $ si
 218 $$ \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 $$
 219 \end{Def}
 220 \begin{Def}
 221  Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $.
 222  \newline
 223  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
 224  $$ t \longmapsto f(x^\ast_1,\ldots,x^\ast_{k-1},x^\ast_k + t,x^\ast_{k+1},\ldots,x^\ast_n) $$
 225  définie sur un voisinage de $ 0 $ dans $ \mathbb{R} $ et à valeurs dans $ \mathbb{R} $ est dérivable en $ 0 $.
 226  \newline
 227  Dans ce cas on note
 228  $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$
 229  cette dérivée.
 230 \end{Def}
 231 \begin{Def}
 232  Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $
 233  et $ x^\ast, h \in \mathbb{R}^n $.
 234  \newline
 235  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
 236  \[
 237   f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h})
 238  \]
 239  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} $
 240  telle que $ \lim\limits_{h \rightarrow 0} \varepsilon_{x^\ast}(h) = 0 $ et
 241  \[
 242   f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h)
 243  \]
 244  On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $.
 245 \end{Def}
 246 \begin{Rmq}
 247  On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$.
 248 \end{Rmq}
 249 \begin{Def}
 250  Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
 251  \newline
 252  Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
 253  \[
 254   \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
 255  \]
 256 \end{Def}
 257 \begin{Rmq}
 258  $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $
 259 \end{Rmq}
 260
 261 \subsection{Conditions d'existence d'un extremum}
 262
 263 On peut démontrer que $ \mathcal{C }$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues.
 264 On peut en déduire que si $ J $ est continue, $ \mathcal{C }$ est un ensemble fermé et borné de $ \mathbb{R}^n $.
 265 \begin{Th}[Théorème de Weierstrass]
 266 Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue.
 267 \newline
 268 Alors : $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$
 269 Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $.
 270 \newline
 271 De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $.
 272 \end{Th}
 273 On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues. L'étude de la convexité de $ J $ permet d'explorer l'unicité de la solution \cite{LJK}.
 274
 275 \subsection{Conditions de caractérisation d'un extremum}
 276
 277 Dans le cas où $ J, g, h $ sont continûment différentiable et ses dérivées sont continues (c'est à dire de classe $ \mathcal{C}^1 $), la recherche du mimimum consiste à faire une descente par gradient 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}.
 278 \newline
 279 On peut en déduire que une condition nécessaire et suffisante pour que $ x^\ast \in \mathring{\mathcal{C}} $ soit un des extremums locaux de $ J $ est que $ \nabla J(x^\ast) = 0 $. Mais si $ x^\ast \in \overline{\mathcal{C}}\setminus\mathring{\mathcal{C}} $ (la frontière de $ \mathcal{C} $) alors $ \nabla J(x^\ast) $ n'est pas nécessairement nul. Il sera par conséquent nécessaire de trouver d'autres caratérisations d'un extremum \cite{FEA,WAL}.
 280
 281 \subsubsection{Conditions de Kuhn-Tucker et Lagrange}
 282
 283 \begin{Th}
 284 Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
 285 \newline
 286 Une condition nécessaire pour que $ x^\ast \in \mathcal{C}$ soit un minimum local est :
 287 \newline
 288 \newline
 289 \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.}
 290 \newline
 291 \newline
 292 et
 293 $$ \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 $$
 294 On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
 295 \end{Th}
 296 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 $.
 297 \newline
 298 \newline
 299 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.
 300
 301
 302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 303
 304 \chapter{Méthodes de programmation quadratique séquentielle}
 305
 306 \section{Optimisation}
 307
 308 \subsubsection{Optimisation ou minimisation avec contraintes}
 309
 310 \bibliographystyle{plain}
 311 \bibliography{stdlib_sbphilo}
 312
 313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 314
 315 \end{document}