Add solution existence conditions.

[Projet_Recherche_Operationnelle.git] / rapport / ProjetOptimRO.tex

diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex
index 9157eb6039bc7de61d0d5e84dc15c3289b56ae33..7a583392366da994ecffccc23f01a7060463553f 100644 (file)
--- a/rapport/ProjetOptimRO.tex
+++ b/rapport/ProjetOptimRO.tex
@@ -163,13 +163,13 @@
 
 \subsection{Présentation rapide}
 
 
 \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
 \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}
 
 
 \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
 \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


@@ -188,14 +188,51 @@ 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}
  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 d'une solution dans $ \mathcal{C} $.

 
 \section{Qu'est-ce que l'optimisation?}
 
 
 \section{Qu'est-ce que l'optimisation?}
 

-La recherche d'un optimum au problème $ \mathcal{P} $ est l'activité principale de 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, elle, 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 $.
 \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})
  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})


@@ -205,7 +242,11 @@ La recherche d'un optimum au problème $ \mathcal{P} $ est l'activité principal
  \[
   f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h)
  \]
  \[
   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}
 \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
 \begin{Def}
  Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
  \newline


@@ -214,8 +255,46 @@ La recherche d'un optimum au problème $ \mathcal{P} $ est l'activité principal
   \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
  \]
 \end{Def}
   \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
  \]
 \end{Def}

-Dans le cas où $ J $ est continûment différentiable et ses dérivées sont continues (ou de classe $ \mathcal{C}^1 $),
-une condition suffisante et nécessaire pour que $ x^\ast \in \mathbb{R}^n $ soit un de ses extremums local ou global est que $ \nabla f(x^\ast) = 0 $.
+\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}
+
+On peut démontrer que $ \mathcal{C }$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues.
+On peut en déduire que si $ J $ est continue, $ \mathcal{C }$ est un ensemble fermé et borné de $ \mathbb{R}^n $.
+\begin{Th}[Théorème de Weierstrass]
+Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue.
+\newline
+Alors $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$
+Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $.
+\newline
+De la même façon, il existe maximum global de $ J $ sur $ \mathcal{C} $.
+\end{Th}
+On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues.
+\subsection{Conditions de caractérisation 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 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 :
+\newline
+\newline
+\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.}
+\newline
+\newline
+et
+$$ \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 $$
+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 x \in \mathbb{R}^n \ \forall i \in \{ 1,\ldots,q \} \ h_i(x) = 0 \Longleftrightarrow h_i(x) \leq 0 \land h_i(x) \geq 0 $.
+\newline

 \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.
 
 \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.