Add solution existence conditions.

[Projet_Recherche_Operationnelle.git] / rapport / ProjetOptimRO.tex

diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex
index 7370bba682f867a1e46db31c3f23345f94054e01..7a583392366da994ecffccc23f01a7060463553f 100644 (file)
--- a/rapport/ProjetOptimRO.tex
+++ b/rapport/ProjetOptimRO.tex
@@ -188,7 +188,7 @@ Définissons le problème central $ \mathcal{P} $ que se 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 $ 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} $.
+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?}
 


@@ -196,7 +196,7 @@ Elle se doit de résoudre les problèmes d'existence d'une solution ($ \mathcal{
 
 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
 
 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.
+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}
 
 
 \subsection{Quelques définitions annexes}
 


@@ -261,9 +261,22 @@ $$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+
 
 \subsection{Conditions d'existence d'un extremum}
 
 
 \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
 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.
+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}
 
 
 \subsubsection{Conditions de Kuhn-Tucker et Lagrange}
 


@@ -271,13 +284,16 @@ On peut en déduire que une condition nécessaire et suffisante pour que $ x^\as
 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 :
 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
 \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}
 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 $.
+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
 \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.