Finally finish the introduction part.

Signed-off-by: Jérôme Benoit <jerome.benoit@piment-noir.org>

diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex
index 8bbbec296a5528fd104d4176aef97c0ac1d9466d..7370bba682f867a1e46db31c3f23345f94054e01 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,11 +188,36 @@ 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 de la solution dans $ \mathcal{C} $.

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

-La recherche d'une valeur 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 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
 \begin{Def}
  Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $.
  \newline


@@ -233,7 +258,27 @@ La recherche d'une valeur optimum au problème $ \mathcal{P} $ est l'activité p
 \begin{Rmq}
  $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $
 \end{Rmq}
 \begin{Rmq}
  $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $
 \end{Rmq}

-Dans le cas où $ J $ est continûment différentiable et ses dérivées sont continues (c'est à dire 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 $.
+
+\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

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