Add a some bibtex references.

[Projet_Recherche_Operationnelle.git] / rapport / ProjetOptimRO.tex

\documentclass[12pt,oneside,a4paper]{book}


%%%%%Packages


\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{color}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage[T1]{fontenc}
\usepackage{multirow}
\usepackage{fancyhdr}
\usepackage{tocbibind}
\usepackage{lmodern}


%%%%%Marges & en-t\^etes

\geometry{hmargin=2.3cm, vmargin=3cm}
\fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis
\fancyhead[FC]{\bfseries\thepage} % N∞page centre bas
\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


%%%%%Th\'eor\`eme et d\'efinitions

\newtheorem{Def}{D\'efinition}
\newtheorem{Not}[Def]{Notation}
\newtheorem{Th}{Th\'eor\`eme}
\newtheorem{Prop}[Th]{Proposition}
\newtheorem{Cor}[Th]{Corollaire}
\newtheorem{Rmq}{Remarque}

\newcommand{\norme}[1]{\left\Vert #1\right\Vert}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%Page de garde

\begin{center}

 %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\
 \includegraphics[scale=0.5]{polytech.png}\\

 \vspace*{0.5cm}

 \footnotesize{
  \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\
  \large \bf  5ème année\\
 }

 \vspace*{0.5cm}

 %\large{Master 2 Professionnel\\
 %Math\'ematiques et Informatique des Nouvelles Technologies\\}

 \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\}

 \vspace*{0.7cm}

 \begin{tabular}{c}
  \hline
  ~                                                           \\
  \LARGE\textbf {Programmation Séquentielle Quadratique}      \\
  \LARGE\textbf {en}                                          \\
  \LARGE\textbf {Optimisation non linéraire sous contraintes} \\
  ~                                                           \\
  \hline
 \end{tabular}

 \vspace*{0.7cm}

 \includegraphics[scale=0.4]{CE.PNG}\\

 \vspace*{0.5cm}

 \large par\\

 %\large  \bsc{}\\
 %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\

 \vspace*{0.2cm}
 \large  {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\

 %\vspace*{0.1cm}

 % \large sous la direction de \\

 %\vspace*{0.1cm}

 %Eric Audureau et Thierry Masson

 %\vspace*{1cm}

 \vspace*{1cm}

 %\normalsize{Licence de Mathématiques 3ème année}
 \normalsize{Année 2018-2019}

\end{center}

\thispagestyle{empty}

\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\pagestyle{plain}
\frontmatter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%Table des mati\`eres

\tableofcontents

\begin{figure}[!b]
 \begin{center}
  %\includegraphics{logo_fac2}
  \includegraphics[scale=0.04]{amu}
 \end{center}
\end{figure}

\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\mainmatter
\pagestyle{fancy}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Introduction générale}

\vspace{.5em}

\section{Qu'est-ce que la recherche opérationnelle?}

\subsection{Présentation rapide}

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. 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 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
 La problèmatique $ \mathcal{P} $ se définit par :
 $$
  \mathcal{P} \left \{
  \begin{array}{r c l}
   \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
   g(x) \leq 0                                 \\
   h(x) = 0
  \end{array}
  \right .
 $$
\end{Def}
\begin{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 d'une 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, 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 \implies |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
 Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
 \[
  \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
 \]
\end{Def}
\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 un 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. L'étude de la convexité de $ J $ permet d'explorer l'unicité de la solution \cite{LJK}.

\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 : $ 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}.
\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 \cite{FEA,WAL}.

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Méthodes de programmation quadratique séquentielle}

\section{Optimisation}

\subsubsection{Optimisation ou minimisation avec contraintes}

\bibliographystyle{plain}
\bibliography{stdlib_sbphilo}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}