X-Git-Url: https://git.piment-noir.org/?a=blobdiff_plain;f=rapport%2FProjetOptimRO.tex;h=7370bba682f867a1e46db31c3f23345f94054e01;hb=f899c72b16952ac4f1d71594788d03f62a596b3a;hp=52420143c3578b15d9b2f033136fad16d46df0b3;hpb=de30386ec37f188c3b84ed5f26e5181124012735;p=Projet_Recherche_Operationnelle.git diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index 5242014..7370bba 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -5,6 +5,8 @@ \usepackage{latexsym} +\usepackage{amsmath} +\usepackage{mathtools} \usepackage{amssymb} \usepackage[utf8]{inputenc} \usepackage[francais]{babel} @@ -27,7 +29,7 @@ \fancyhead[HC]{\footnotesize\leftmark} % chapitre centre haut \renewcommand{\headrulewidth}{0.2pt} % filet en haut \addtolength{\headheight}{0.5pt} % espace pour le filet -\renewcommand{\footrulewidth}{0.2pt} %filet en bas +\renewcommand{\footrulewidth}{0.2pt} % filet en bas %%%%%Th\'eor\`eme et d\'efinitions @@ -39,6 +41,7 @@ \newtheorem{Cor}[Th]{Corollaire} \newtheorem{Rmq}{Remarque} +\newcommand{\norme}[1]{\left\Vert #1\right\Vert} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -160,13 +163,13 @@ \subsection{Présentation rapide} -La recherche opérationnelle est une discipline dite "hybride" au confluent de plusieurs disciplines dont principalement l'analyse numérique, les probabilités, la statistique et l'algorithmie. +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). \newline -On la considère usuellement comme une sous discipline des mathématiques de la décision. +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. \subsection{Définition de la problèmatique} -Définissons le problème central $ \mathcal{P} $ que ce propose de résoudre la recherche opérationnelle. +Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la recherche opérationnelle : \begin{Def} 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}$. \newline @@ -185,10 +188,65 @@ Définissons le problème central $ \mathcal{P} $ que ce propose de résoudre la On définit $ \mathcal{C} $ l'ensemble des contraintes par : $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$ \end{Def} -Elle se doit de résoudre les problèmes d'existence d'une solution ($ \mathcal{C} \neq \emptyset $) ainsi que de construction d'une solution. +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 de la solution dans $ \mathcal{C} $. \section{Qu'est-ce que l'optimisation?} +\subsection{Définition} + +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. +\newline +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 une science. + +\subsection{Quelques définitions annexes} + +Définissons quelques notions supplémentaires de base nécessaires à la suite : +\begin{Def} +Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $. +\newline +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} $. +\end{Def} +\begin{Def} +Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $. +\newline +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} $. +\end{Def} + +\begin{Def} +Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $. +\newline +On dit que $ f $ est continue en $ x^\ast $ si +$$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+}^{*} \ \forall x \in \mathbb{R}^n \ \norme{x - x^\ast} \leq \alpha \Longrightarrow |f(x) - f(x^\ast)| \leq \varepsilon $$ +\end{Def} +\begin{Def} + Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $. + \newline + 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 + $$ t \longmapsto f(x^\ast_1,\ldots,x^\ast_{k-1},x^\ast_k + t,x^\ast_{k+1},\ldots,x^\ast_n) $$ + définie sur un voisinage de $ 0 $ dans $ \mathbb{R} $ et à valeurs dans $ \mathbb{R} $ est dérivable en $ 0 $. + \newline + Dans ce cas on note + $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$ + cette dérivée. +\end{Def} +\begin{Def} + Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ + et $ x^\ast, h \in \mathbb{R}^n $. + \newline + 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 + \[ + f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h}) + \] + 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} $ + telle que $ \lim\limits_{h \rightarrow 0} \varepsilon_{x^\ast}(h) = 0 $ et + \[ + f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h) + \] + On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $. +\end{Def} +\begin{Rmq} + On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$. +\end{Rmq} \begin{Def} Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable. \newline @@ -197,13 +255,32 @@ Elle se doit de résoudre les problèmes d'existence d'une solution ($ \mathcal{ \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast)) \] \end{Def} -La recherche d'un optimum au problème $ \mathcal{P} $ est l'activité principale de l'optimisation. +\begin{Rmq} + $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $ +\end{Rmq} + +\subsection{Conditions d'existence d'un extremum} + +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 : $ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \norme{\nabla J(x^\ast)} < \varepsilon $. +\newline +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 ou globaux 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. + +\subsubsection{Conditions de Kuhn-Tucker et Lagrange} + +\begin{Th} +Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $. +\newline +Une condition nécessaire pour que $ x^\ast \in \mathcal{C}$ soit un minimum local est : +$$ \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 $$ +et $ \{ \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. +\newline +\newline +On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange. +\end{Th} +Il est à noter que une condition d'égalité peut se répresenter par deux conditions d'inégalité : $ \forall i \in \{ 1,\ldots,q \} \ h_i = 0 \Longleftrightarrow \exists g_i \ g_i \leq 0 \land g_i \geq 0 $. \newline -Dans le cas où $ J $ est continûment différentiable et ses dérivées sont continues, -une condition suffisante pour que $ x^\ast \in \mathbb{R}^n $ soit un de ses extremums -est que $ \nabla f(x^\ast) = 0 $. \newline -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. +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. % Dans cette section nous prenons appui sur l'ouvrage {\it Optimisation et contrôle des systèmes linéaires} \cite{Berg} de Maïtine Bergounioux \footnote{Maïtine Bergounioux, {\it Optimisation et contrôle des systèmes linéaires}, Dunod, 2001.}. % Nous utiliserons aussi l'ouvrage de Francis Filbet\footnote{Francis Filbet, {\it Analyse numérique - Algorithme et étude mathématique}, Dunod, 2009.}, {\it Analyse numérique - Algorithme et étude mathématique} \cite{Filb}.