%%%%%Packages
+
\usepackage{latexsym}
+\usepackage{amsmath}
+\usepackage{mathtools}
\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\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
\newtheorem{Cor}[Th]{Corollaire}
\newtheorem{Rmq}{Remarque}
+\newcommand{\norme}[1]{\left\Vert #1\right\Vert}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{tabular}{c}
\hline
- ~ \\
- \LARGE\textbf {Programmation Séquentielle Quadratique} \\
- \LARGE\textbf {en} \\
+ ~ \\
+ \LARGE\textbf {Programmation Séquentielle Quadratique} \\
+ \LARGE\textbf {en} \\
\LARGE\textbf {Optimisation non linéraire sous contraintes} \\
- ~ \\
+ ~ \\
\hline
\end{tabular}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%Table des mati\`eres
\tableofcontents
\subsection{Définition de la problèmatique}
-Soient $(n, p, q) \in \mathbb{N}^3$, $x \in \mathbb{R}^n$, deux fonctions $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$, une fonction $J: \mathbb{R}^n \longrightarrow \mathbb{R}$;
-\newline
-On définit le problème central $ \mathcal{P} $ que ce propose de résoudre la recherche opérationnelle :
-\newline
-\begin{center}
-$
- \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{center}
-
+Définissons le problème central $ \mathcal{P} $ que ce 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 $) ainsi que de construction d'une solution.
\section{Qu'est-ce que l'optimisation?}
-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}.
+La recherche d'une valeur optimum au problème $ \mathcal{P} $ est l'activité principale de l'optimisation.
+\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}
+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 $.
+\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 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}.
%{\it La relativité}, Que sais-je?, 4ème édition, puf, 2000, \cite{Mavr};
%ainsi que Jean Hladik, {\it La relativité selon Einstein}, L'esprit des sciences, Ellipses, 2000, \cite{Hlad}.
-
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\chapter{Sujets d'étude en travaux dirigés}
-
-\section{Cahier des charges}
-
-Il s'agit de travailler en binôme ou bien seul sur des sujets complémentaires et d'approfondissement du cours. Le travail en question effectué durant les TDs consistera
-à effectuer un dossier sur un thème. Le dossier devra être tapé en Latex ou Tex puisque il peut y avoir des formules de mathématiques ou de physiques. Il pourra aussi comporter une partie "implémentation effective" d'algorithmes (en annexe).
-
-\vspace{.5em}
-
-Sur la fond, toutes les sources de connaissance utilisées devront être citées. En particulier, la méthodologie universitaire sera privilégiée
-(citations en note de bas de page et dans le corps du document, liste des références en fin de document dans la bibliographie, etc...).
-Wikipédia pourra être utilisé mais cela devra être mentionné en tant que référence (note de bas de page ou citation dans le corps du document).
-L'accent sera essentiellement mis sur la démarche scientifique utilisée à égal niveau avec le contenu acquis des connaissances.
-
-\vspace{.5em}
-
-Plusieurs sources devront être croisées afin de prétendre au maximum de vraisemblance
-et d'objectivité scientifique. Le document ne devra pas excéder 10 pages.
-On privilégiera les qualités de synthèse, d'organisation ainsi que du contenu du document.
-
-\section{Proposition de sujets}
-
-\subsection{Analyse numérique}
-
-\vspace{.5em}
-
-1) Méthode des moindres Carrés (cas général, cas pondéré, cas des équations non linéaires).
-
-\vspace{.5em}
-
-2) Méthode de Newton-Raphson (cas d'une variable, cas de deux variables) - Application: extrema d'une fonction à deux variables.
-
-\vspace{.5em}
-
-3) Autres méthodes: méthode de Jacobi, de Gauss-Seidel, etc....
-
-\vspace{.5em}
-
-\subsection{Optimisation}
-
-\vspace{.5em}
-
-\subsubsection{Optimisation sans contrainte}
-
-{\bf A- Algorithmes déterministes}
-
-\vspace{.5em}
-
-1) Régression linéaire sans contrainte (pré-requis: Méthode des moindres carrés).
-
-\vspace{.5em}
-
-2) Méthodes de descente: la méthode du gradient (à pas constant ou à pas variable ou à pas optimal).
-
-\vspace{.5em}
-
-3) Méthode de Newton (ou méthode dite de la tangente) et application à la recherche d'extrema.
-
-\vspace{.5em}
-
-4) Méthodes de descente: méthode du gradient conjugué (cas linéaire et cas général)
-
-\vspace{.5em}
-
-5) Méthode de relaxation
-
-\vspace{.5em}
-
-{\bf B- Algorithmes probabilistes ou dit stochastiques}
-
-\vspace{.5em}
-
-1) Dynamique de métropolis (prérequis: chaines de Markov)
-
-\vspace{.5em}
-
-2) Recuit simulé sur un ensemble fini et application au problème du voyageur de commerce (prérequis: dynamique de métropolis)
-
-\vspace{.5em}
+\chapter{Méthodes de programmation quadratique séquentielle}
+
+% \section{Cahier des charges}
+%
+% Il s'agit de travailler en binôme ou bien seul sur des sujets complémentaires et d'approfondissement du cours. Le travail en question effectué durant les TDs consistera
+% à effectuer un dossier sur un thème. Le dossier devra être tapé en Latex ou Tex puisque il peut y avoir des formules de mathématiques ou de physiques. Il pourra aussi comporter une partie "implémentation effective" d'algorithmes (en annexe).
+%
+% \vspace{.5em}
+%
+% Sur la fond, toutes les sources de connaissance utilisées devront être citées. En particulier, la méthodologie universitaire sera privilégiée
+% (citations en note de bas de page et dans le corps du document, liste des références en fin de document dans la bibliographie, etc...).
+% Wikipédia pourra être utilisé mais cela devra être mentionné en tant que référence (note de bas de page ou citation dans le corps du document).
+% L'accent sera essentiellement mis sur la démarche scientifique utilisée à égal niveau avec le contenu acquis des connaissances.
+%
+% \vspace{.5em}
+%
+% Plusieurs sources devront être croisées afin de prétendre au maximum de vraisemblance
+% et d'objectivité scientifique. Le document ne devra pas excéder 10 pages.
+% On privilégiera les qualités de synthèse, d'organisation ainsi que du contenu du document.
+%
+% \section{Proposition de sujets}
+%
+% \subsection{Analyse numérique}
+%
+% \vspace{.5em}
+%
+% 1) Méthode des moindres Carrés (cas général, cas pondéré, cas des équations non linéaires).
+%
+% \vspace{.5em}
+%
+% 2) Méthode de Newton-Raphson (cas d'une variable, cas de deux variables) - Application: extrema d'une fonction à deux variables.
+%
+% \vspace{.5em}
+%
+% 3) Autres méthodes: méthode de Jacobi, de Gauss-Seidel, etc....
+%
+% \vspace{.5em}
+
+\section{Optimisation}
+
+% \vspace{.5em}
+
+% \subsubsection{Optimisation sans contrainte}
+%
+% {\bf A- Algorithmes déterministes}
+%
+% \vspace{.5em}
+%
+% 1) Régression linéaire sans contrainte (pré-requis: Méthode des moindres carrés).
+%
+% \vspace{.5em}
+%
+% 2) Méthodes de descente: la méthode du gradient (à pas constant ou à pas variable ou à pas optimal).
+%
+% \vspace{.5em}
+%
+% 3) Méthode de Newton (ou méthode dite de la tangente) et application à la recherche d'extrema.
+%
+% \vspace{.5em}
+%
+% 4) Méthodes de descente: méthode du gradient conjugué (cas linéaire et cas général)
+%
+% \vspace{.5em}
+%
+% 5) Méthode de relaxation
+%
+% \vspace{.5em}
+%
+% {\bf B- Algorithmes probabilistes ou dit stochastiques}
+%
+% \vspace{.5em}
+%
+% 1) Dynamique de métropolis (prérequis: chaines de Markov)
+%
+% \vspace{.5em}
+%
+% 2) Recuit simulé sur un ensemble fini et application au problème du voyageur de commerce (prérequis: dynamique de métropolis)
+%
+% \vspace{.5em}
\subsubsection{Optimisation ou minimisation avec contraintes}
-\vspace{.5em}
-
-1) Régression linéaire avec contraintes (prérequis: méthode des moindres carrés, conditions ou équations dites de Karush-kuhn-Tucker (KKT)) .
-
-\vspace{.5em}
-
-2) Cas de la programmation linéaire (prérequis: Lagrangien et multiplicateurs de Lagrange, conditions de KKT).
-
-\vspace{.5em}
-
-3) Algorithmes: méthode du gradient projeté, méthode de Lagrange-Newton pour des contraintes en égalité,
-méthode de Newton projetée pour des contraintes de bornes, méthodes de pénalisation,
-méthodes de programmation quadratique successive (SQP Sequential Quadratic Programming),
-méthode de dualité (méthode d'Uzawa, prérequis: théorie de la dualité convexe) etc...
-
-\vspace{.5em}
-
-\subsection{Recherche opérationnelle}
-
-\vspace{.5em}
-
-\subsubsection{La programmation linéaire (cas particulier de l'optimisation avec contraintes)}
-
-1) Méthode d'énumération.
-
-\vspace{.5em}
-
-2) Méthode du simplexe.
-
-\vspace{.5em}
-
-3) Application à des problèmes de R.O:
-
-\vspace{.5em}
-
-\hspace{.3em} 3.1) Fêtes de Pâques: A l'approche des fêtes de Pâques, un artisan chocolatier décide de confectionner des oeufs en chocolats. En allant inspecter ses réserves, il constate qu'il lui reste 18 kg de cacao, 8 kg de noisettes et 14 litres de lait. Ce chocolatier a deux spécialités: l'oeuf {\it extra} et l'oeuf {\it sublime}. Un oeuf {\it extra} nécessite 1kg de cacao, 1 kg de noisettes et 2 litres de lait tandis qu'un oeuf {\it sublime} nécessite 3 kg de cacao, 1 kg de noisettes et 1 litre de lait. Il fera un bénéfice de 20 euros en vendant un oeuf {\it extra}, et de 30 euros en vendant un oeuf {\it sublime}.
-
-\vspace{.5em}
-
-\hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire.
-
-\vspace{.5em}
-
-\hspace{.6em} b) Combien d'oeufs extra et sublime doit-il fabriquer pour faire le plus grand bénéfice?
-
-\vspace{.5em}
-
-\hspace{.3em} 3.2) Organisation du travail: La fabrication d'une pièce $P_1$ a un prix de revient de 150 euros et celle d'une pièce $P_2$ coûte 100 euros. Chaque pièce est traitée successivement dans trois ateliers. Le nombre d'heures-machines par pièce est indiqué dans le tableau suivant :
-
-\vspace{.5em}
-
-\begin{center}
- $
- \begin{array}{|c|c|c|c|}
- \hline
- Atelier & A & B & C \\
- \hline
- Pièce 1 & 3 h & 5 h & 2 h \\
- \hline
- Pièce 2 & 1 h & 3 h & 3 h \\
- \hline
- \end{array}
- $
-\end{center}
-
-\vspace{.5em}
-
-Pour éviter le chômage technique, l'atelier A doit obligatoirement fournir 1200 heures machines, l'atelier B doit obligatoirement fournir 3000 heures machines et l'atelier C doit obligatoirement fournir 1800 heures machines.
-
-\hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire.
-
-\vspace{.5em}
-
-\hspace{.6em} b) Combien faut-il fabriquer de pièces $P_1$ et $P_2$ pour minimiser le coût de revient de l'ensemble de la production et pour assurer le fonctionnement des trois ateliers excluant tout chômage technique?
-
-\vspace{.5em}
+% \vspace{.5em}
+%
+% 1) Régression linéaire avec contraintes (prérequis: méthode des moindres carrés, conditions ou équations dites de Karush-kuhn-Tucker (KKT)) .
+%
+% \vspace{.5em}
+%
+% 2) Cas de la programmation linéaire (prérequis: Lagrangien et multiplicateurs de Lagrange, conditions de KKT).
+%
+% \vspace{.5em}
+%
+% 3) Algorithmes: méthode du gradient projeté, méthode de Lagrange-Newton pour des contraintes en égalité,
+% méthode de Newton projetée pour des contraintes de bornes, méthodes de pénalisation,
+% méthodes de programmation quadratique successive (SQP Sequential Quadratic Programming),
+% méthode de dualité (méthode d'Uzawa, prérequis: théorie de la dualité convexe) etc...
+%
+% \vspace{.5em}
+%
+% \subsection{Recherche opérationnelle}
+%
+% \vspace{.5em}
+%
+% \subsubsection{La programmation linéaire (cas particulier de l'optimisation avec contraintes)}
+%
+% 1) Méthode d'énumération.
+%
+% \vspace{.5em}
+%
+% 2) Méthode du simplexe.
+%
+% \vspace{.5em}
+%
+% 3) Application à des problèmes de R.O:
+%
+% \vspace{.5em}
+%
+% \hspace{.3em} 3.1) Fêtes de Pâques: A l'approche des fêtes de Pâques, un artisan chocolatier décide de confectionner des oeufs en chocolats. En allant inspecter ses réserves, il constate qu'il lui reste 18 kg de cacao, 8 kg de noisettes et 14 litres de lait. Ce chocolatier a deux spécialités: l'oeuf {\it extra} et l'oeuf {\it sublime}. Un oeuf {\it extra} nécessite 1kg de cacao, 1 kg de noisettes et 2 litres de lait tandis qu'un oeuf {\it sublime} nécessite 3 kg de cacao, 1 kg de noisettes et 1 litre de lait. Il fera un bénéfice de 20 euros en vendant un oeuf {\it extra}, et de 30 euros en vendant un oeuf {\it sublime}.
+%
+% \vspace{.5em}
+%
+% \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire.
+%
+% \vspace{.5em}
+%
+% \hspace{.6em} b) Combien d'oeufs extra et sublime doit-il fabriquer pour faire le plus grand bénéfice?
+%
+% \vspace{.5em}
+%
+% \hspace{.3em} 3.2) Organisation du travail: La fabrication d'une pièce $P_1$ a un prix de revient de 150 euros et celle d'une pièce $P_2$ coûte 100 euros. Chaque pièce est traitée successivement dans trois ateliers. Le nombre d'heures-machines par pièce est indiqué dans le tableau suivant :
+%
+% \vspace{.5em}
+%
+% \begin{center}
+% $
+% \begin{array}{|c|c|c|c|}
+% \hline
+% Atelier & A & B & C \\
+% \hline
+% Pièce 1 & 3 h & 5 h & 2 h \\
+% \hline
+% Pièce 2 & 1 h & 3 h & 3 h \\
+% \hline
+% \end{array}
+% $
+% \end{center}
+%
+% \vspace{.5em}
+%
+% Pour éviter le chômage technique, l'atelier A doit obligatoirement fournir 1200 heures machines, l'atelier B doit obligatoirement fournir 3000 heures machines et l'atelier C doit obligatoirement fournir 1800 heures machines.
+%
+% \hspace{.6em} a) \'Ecrire ce problème sous la forme d'un problème de programmation linéaire.
+%
+% \vspace{.5em}
+%
+% \hspace{.6em} b) Combien faut-il fabriquer de pièces $P_1$ et $P_2$ pour minimiser le coût de revient de l'ensemble de la production et pour assurer le fonctionnement des trois ateliers excluant tout chômage technique?
+%
+% \vspace{.5em}
\bibliographystyle{plain}
\bibliography{stdlib_sbphilo}
%\bibitem[2]{Aspect} {\bf Alain Aspect}, Présentation naïve des inégalités de Bell, 2004.\\
- \bibitem[3]{Basda} {\bf Jean-Louis Basdevant et Manuel Joffre}, Mécanique Quantique, Les éditions de l'Ecole Polytechnique, 2006.\\
+ % \bibitem[3]{Basda} {\bf Jean-Louis Basdevant et Manuel Joffre}, Mécanique Quantique, Les éditions de l'Ecole Polytechnique, 2006.\\
%\bibitem[4]{Diu} {\bf Bernard Diu}, Le congrès de Solvay de 1927: petite chronique d'un grand évènement, Bibnum.\\
repositories / Projet_Recherche_Operationnelle.git / blobdiff