\usepackage{latexsym}
+\usepackage{amsmath}
+\usepackage{amsthm}
+\usepackage{mathtools}
\usepackage{amssymb}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{fancyhdr}
\usepackage{tocbibind}
\usepackage{lmodern}
+\usepackage{enumitem}
+\usepackage{algorithm2e}
+\usepackage{algorithmic}
%%%%%Marges & en-t\^etes
\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 {Optimisation non linéraire sous contraintes} \\
- ~ \\
+ ~ \\
+ \LARGE\textbf {Programmation Quadratique Séquentielle ou PQS} \\
+ \LARGE\textbf {en} \\
+ \LARGE\textbf {Optimisation non linéraire sous contraintes} \\
+ ~ \\
\hline
\end{tabular}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Introduction générale}
+L'objectif de ce chapitre est de faire un bref rappel des définitions, notions et résultats essentiels en recherche opérationnelle ainsi que en mathématiques nécessaires à l'étude de la méthode PQS.
+\newline
+Elle est loin d'être exhaustive mais devrait suffire dans le cadre de ce projet.
+
\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 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
-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}
-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
La problèmatique $ \mathcal{P} $ se définit par :
$$
\mathcal{P} \left \{
- \begin{array}{r c l}
+ \begin{array}{l}
\displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
g(x) \leq 0 \\
h(x) = 0
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?}
+\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}
+ On définit le Lagrangien associé à $ \mathcal{P} $ par :
+ $$ \begin{array}{r c l}
+ L : \mathbb{R}^n \times \mathbb{R}^q \times \mathbb{R}_+^p & \longrightarrow & \mathbb{R} \\
+ (x,\lambda,\mu) & \longmapsto & L(x,\lambda,\mu) = J(x) + \sum\limits_{i=1}^{q} \lambda_i h_i(x) + \sum\limits_{j=1}^{p} \mu_j g_j(x) \\
+ & & L(x,\lambda,\mu) = J(x) + \langle \lambda,h(x) \rangle_{\mathbb{R}^q} + \langle \mu,g(x) \rangle_{\mathbb{R}^p}
+ \end{array} $$
+ où l’on note $ \lambda $ et $ \mu $ les vecteurs de coordonnées respectives $ (\lambda_1,\ldots,\lambda_q) $ et $ (\mu_1,\ldots,\mu_p) $.
+\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{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{Rmq}
+ $ A \subset \mathbb{R}^n $ est un ouvert $ \iff A = \mathring{A} $.
+\end{Rmq}
+\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{Rmq}
+ $ A \subset \mathbb{R}^n $ est un fermé $ \iff A = \overline{A} $.
+\end{Rmq}
+\begin{Def}
+ Soient $ f : \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ S \subset \mathbb{R}^n $. On définit $ \mathrm{argmin} $ de $ f $ sur $ S $ par :
+ $$ \underset{x \in S}{\mathrm{argmin}} f(x) = \{ x \in \mathbb{R}^n \ | \ x \in S \land \forall y \in S \ f(y) \geq f(x) \} $$
+\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
\nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
\]
\end{Def}
-La recherche d'un optimum au problème $ \mathcal{P} $ est l'activité principale de l'optimisation.
-\newline
-Dans le cas où $ J $ est continûment différentiable et ses dérivées sont continues,
-une condition suffisante pour que $ x^\ast \in \mathbb{R}^n $ soit un de ses extremums
-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 = \nabla f(x^\ast)^\top h $
+\end{Rmq}
+\begin{Def}
+ Soit $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ une fonction de classe $ \mathcal{C}^2 $.
+ On définit la matrice hessienne de $ f $ en $ x^\ast $ par :
+ $$ H[f](x^\ast) =
+ \begin{pmatrix}
+ \frac{\partial^2 f}{\partial x_1^2}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n}(x^\ast) \\
+ \vdots & & \vdots \\
+ \frac{\partial^2 f}{\partial x_n\partial x_1}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_n^2}(x^\ast)
+ \end{pmatrix} $$
+\end{Def}
+\begin{Prop}
+ \begin{enumerate}
+ \item $ H[f](x^\ast) $ est une matrice symétrique (Théorème de symétrie de Schwarz).
+ \item On a le développement de Taylor-Young à l'ordre 2 en $ x^\ast $ suivant :
+ $$ f(x^\ast + v) = f(x^\ast) + \langle \nabla f(x^\ast),v \rangle + \frac{1}{2} v^\top H[f](x^\ast) v + \varepsilon(v) $$
+ ou
+ $$ f(x^\ast + v) = f(x^\ast) + \langle \nabla f(x^\ast),v \rangle + \frac{1}{2} \langle H[f](x^\ast)v,v \rangle + \varepsilon(v) $$
+ avec $ \frac{|\varepsilon(v)|}{\norme{v}} \rightarrow 0 $ quand $ \norme{v} \rightarrow 0 $.
+ \end{enumerate}
+\end{Prop}
+\begin{proof}
+ Elle repose entièrement sur deux autres théorèmes dont les preuves sont connues et de la réécriture de formulation de résultat.
+\end{proof}
+
+\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 $ \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}
+Si $ J $ est continue, on en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues \cite{LJK,RON}. L'étude de la convexité de $ J $ sur $ \mathcal{C} $ permet d'explorer l'unicité de la solution \cite{LJK,RON}.
+
+\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 des descentes par gradient [section \ref{descente}] 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
-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.
+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 local \cite{FEA,WAL}.
-% 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}.
+\subsubsection{Conditions nécessaires de Karuch-Kuhn-Tucker ou \textit{KKT}}\label{KKT}
-%{\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}.
+\begin{Th}
+ Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
+ \newline
+ Les conditions nécessaires pour que $ x^\ast \in \mathcal{C}$ soit un minimum local de $ J $ sont :
+ \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.
+ \newline
+ On nomme également les conditions \textit{KTT} conditions nécessaires d'optimalité du premier ordre.
+\end{Th}
+\begin{proof}
+ Elle repose sur le lemme de Farkas \cite{FEA,RON}.
+\end{proof}
+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 $ \cite{FEA}, ce qui peut permettre de réécrire le problème $ \mathcal{P} $ en éliminant les contraintes d'égalités et change la forme des conditions \textit{KKT} à vérifier mais rajoute $ 2q $ conditions d'inégalités et donc $ 2q $ multiplicateurs de Kuhn-Tucker.
+\begin{Def}
+ On appelle un point admissible $ x^\ast \in \mathcal{C} $ un point critique de $ \mathcal{P} $ si il statisfait les conditions \textit{KKT}.
+\end{Def}
+
+\subsubsection{Conditions suffisantes du deuxième ordre}
+\begin{Th}
+ Les conditions suffisantes en plus de celles \textit{KKT} pour que $ x^\ast \in \mathcal{C} $ soit un minimum local de $ J $ sont :
+ \begin{enumerate}[label=(\roman*)]
+ \item relâchement complémentaire dual\footnote{La définition de cette notion ne sera pas donnée car elle n'est pas nécessaire pour l'étude de la méthode PQS.} strict en $ x^\ast $.
+ \item $ \forall v \in \mathbb{R}^n \land v \neq 0 \ \langle H_x[L](x^\ast,\lambda,\mu)v,v \rangle > 0 $.
+ \end{enumerate}
+\end{Th}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\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}
+\chapter{Méthode de programmation quadratique séquentielle}
-\bibliographystyle{plain}
-\bibliography{stdlib_sbphilo}
+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 ou PQS.
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\vspace{.5em}
-\end{document}
+\section{Methode de descente}\label{descente}
+Nous supposons que le domaine des contraintes de $ \mathcal{P} $ est un ouvert de $ \mathbb{R}^n $ (c'est à dire que nous n'avons pas de contraintes) et $ J $ est une fonction définie sur $ \mathbb{R}^n $ à valeurs réelles supposée différentiable, voire même deux fois différentiable. Les conditions nécessaires d’optimalité du premier et du second ordre expriment le fait qu’il n’est pas possible de “descendre” à partir d’un point de minimum (local ou global). Cette observation va servir de point de départ à l’élaboration des méthodes dites de descente.
-\begin{thebibliography}{6}\input{MemoireM2Ballet6.synctex.gz(busy)}
+Partant d’un point $ x_0 \in \mathbb{R}^n $ arbitrairement choisi, un algorithme de descente va chercher à générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ définie par :
+$$ x_{k+1} = x_k + s_kd_k $$ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $ et avec
+$$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
+Un tel algorithme est ainsi déterminé par deux éléments à chaque étape $ k $ : le choix de la direction $ d_k $ appelée direction de descente, et le choix de la taille du pas $ s_k $ à faire dans la direction $ d_k $. Cette étape est appelée \textit{recherche linéaire}.
- %\bibitem[1]{BL} Jean-Pierre \bsc{Bourguignon} et David \bsc{Langlois}, Cours de M1, Module Relativité Générale,
- %Ecole Polytechnique, ParisTech, 2011.\\
+\subsection{Définition d'une direction de descente}
- %\bibitem[2]{G} Gilles \bsc{Cohen-Tannoudji}, Einstein et la refondation relativiste de la physique, 2005.\\
+Un vecteur $ d \in \mathbb{R}^n $ est une direction de descente pour $ J $ à partir d’un point $ x_0 \in \mathbb{R}^n $ si $ t \longmapsto f(x_0 + td) $ est strictement décroissante en $ t = 0 $, c’est-à-dire :
+$$ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) $$
+Il est donc important d’analyser le comportement de la fonction $ J $ dans certaines directions.
+\begin{Prop}
+ Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $.
+ \newline
+ d est un vecteur de descente de $ J $ en $ x_0 \in \mathbb{R}^n $ ssi :
+ $$ \nabla J(x_0)^\top d < 0 $$
+ De plus
+ $$ \forall \beta < 1 \in \mathbb{R}_{+} \ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) + t\beta \nabla J(x_0)^\top d < J(x_0) $$
+\end{Prop}
+\begin{proof}
+ Elle s'effectue en utilisant le développement de Taylor-Young de l’application $ t \longmapsto f(x_0 + td) $ à l’ordre 1.
+\end{proof}
+Cette dernière inégalité garantit une décroissance minimum de la fonction $ J $ dans la direction $ d $ et peut se traduire par : la décroissance de la fonction $ J $, en effectuant un pas de longueur $ t $ dans la direction $ d $, est au moins égale à la longueur du pas multipliée par une fraction de la pente. Le schéma général d’un algorithme de descente est alors le suivant :
+
+\hrulefill
+\newline
+ALGORITHME DE DESCENTE MODÈLE.
+\newline
+\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
+\newline
+\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
+\begin{enumerate}
+ \item $ k := 0 $.
+ \item Tant que "test d’arrêt" non satisfait,
+ \begin{enumerate}
+ \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
+ \item \textit{Recherche linéaire} : Choisir un pas $ s_k > 0 $ à faire dans cette direction et tel que : $$ J(x_k + s_kd_k) < J(x_k). $$
+ \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
+ \end{enumerate}
+ \item Retourner $ x_k $.
+\end{enumerate}
+
+\hrulefill
+
+\subsection{Choix de la direction de descente}
+
+Une fois la théorie bien maîtrisée, calculer une direction de descente est relativement simple. Dans le cas différentiable, il existe deux grandes stratégies de choix de direction de descente :
+\begin{itemize}
+ \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}.
+ \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}.
+\end{itemize}
+Remarquons que si $ x_k $ est un point stationnaire ($ \iff \nabla J(x_k) = 0 $) non optimal alors toutes ces directions sont nulles et aucun de ces algorithmes ne pourra progresser. Ce problème peut être résolu en utilisant des approches de type région de confiance qui ne seront pas étudiées dans le cadre de ce projet.
+
+\subsection{Critère d’arrêt}
+
+Soit $ x^\ast $ un minimum local de l'objectif $ J $ à optimiser. Supposons que l’on choisisse comme test d’arrêt dans l’algorithme de descente modèle, le critère idéal : "$ x_k = x^\ast $". Dans un monde idéal (i.e. en supposant tous les calculs exacts et la capacité de calcul illimitée), soit l’algorithme s’arrête après un nombre fini d’itérations, soit il construit (théoriquement) une suite infinie $ x_0,x_1,\ldots,x_k,\ldots $ de points de $ \mathbb{R}^n $ qui converge vers $ x^\ast $.
+\newline
+En pratique, un test d’arrêt devra être choisi pour garantir que l’algorithme s’arrête toujours après un nombre fini d’itérations et que le dernier point calculé soit suffisamment proche de $ x^\ast $.
+
+Soit $ \varepsilon \in \mathbb{R}_{+}^{*} $ la précision demandée. Plusieurs critères sont à notre disposition : tout d’abord (et c’est le plus naturel), un critère d’optimalité basé sur les conditions nécessaires d’optimalité du premier ordre : en optimisation différentiable sans contrainte, on testera si
+$$ \norme{\nabla J(x_k)} < \varepsilon, $$
+auquel cas l’algorithme s’arrête et fournit l’itéré courant $ x_k $ comme solution.
+
+En pratique, le test d’optimalité n’est pas toujours satisfait et on devra faire appel à d’autres critères fondés sur l’expérience du numérique :
+\begin{itemize}
+ \item Stagnation de la solution : $ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $.
+ \item Stagnation de la valeur courante : $ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $.
+ \item Nombre d’itérations dépassant un seuil fixé à l’avance : $ k < IterMax $.
+\end{itemize}
+et généralement une combinaison de ces critères :
+\newline
+\newline
+Critère d’arrêt =
+\begin{tabular}{l}
+ Test d’optimalité satisfait \\
+ OU (Stagnation de la valeur courante ET Stagnation de la solution) \\
+ OU Nombre d’itérations maximum autorisé dépassé
+\end{tabular}
- %\bibitem[3]{D} Pierre \bsc{Duhem}, La théorie physique, son objet, sa structure, Vrin, 2007.\\
+\subsection{La recherche linéaire}
- %\bibitem[4]{E1} Albert \bsc{Einstein}, Die formale grundlage der allgemeinen Relativittstheorie. Kniglich Preussische
- %Akademie der Wissenschaften (Berlin),Sitzungsberichte: pp 1030-1085. \\
+Supposons pour l’instant résolu le problème du choix de la direction de descente et intéressons nous uniquement au calcul du pas : c’est la phase de recherche linéaire.
+\newline
+Soit $ x_0 \in \mathbb{R}^n $ un point non critique et $ d $ une direction de descente de $ J $ en $ x_0 $. Nous cherchons à calculer un pas $ s > 0 $ de sorte que :
+$$ J(x_0 + sd) < J(x_0). $$
+Le choix de ce pas répond généralement à deux objectifs souvent contradictoires : trouver le meilleur pas possible et effectuer le moins de calculs possibles. Ces deux objectifs ont donné naissance à deux grandes familles : les algorithmes à pas fixe et ceux à pas optimal.
- %\bibitem[5]{G} Christian \bsc{Godin}, Dictionnaire de philosophie, Fayard Edition du temps, 2004.\\
+\hrulefill
+\newline
+RECHERCHE LINÉAIRE : PAS FIXE. $ s_k = s_{k-1} $
- %\bibitem[6]{H} Jean \bsc{Hladik}, La Relativité selon Einstein, L'Esprit des Sciences, Ellipses.\\
+\hrulefill
- %\bibitem[7]{IS} \bsc{Iftime} and \bsc{Stachel}, The hole argument for covariant theories, arKiv:gr-qc/0512021v2, 8 avril 2006.\\
+\hrulefill
+\newline
+RECHERCHE LINÉAIRE : PAS OPTIMAL. $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
- %\bibitem[8]{K} \bsc{Kant}, Critique de la raison pure, Traduction, présentation, notes par Alain Renaut, GF-Flammarion, 2006.\\
+\hrulefill
+\newline
+Illustrées par les méthodes de descente de gradient, aucune de ces deux stratégies ne s’est révélée réellement convaincante : si la première peut être “risquée” du point de vue de la convergence, la seconde est souvent loin d’être triviale à mettre en oeuvre (sauf dans le cas quadratique) et généralement inutilement coûteuse : en effet, à quoi bon calculer très précisément un pas optimal dans une direction qui n’est peut-être pas la bonne ? (comme c’est par exemple le cas pour la méthode de plus profonde descente). Les recherches linéaires modernes reposent sur l’idée qu’un pas de descente acceptable est un pas qui fait “suffisamment” décroître la fonction objectif. Reste alors à définir les pas qui sont acceptables et ceux qui ne le sont pas.
+\begin{Def}
+ On appelle $ \varphi : s \in \mathbb{R} \longmapsto J(x + sd)$ la fonction mérite associée à $ J $ en $ x $.
+\end{Def}
+\begin{Def}
+ Dans le cas où $ J $ est différentiable sur $ \mathcal{C} $, on dit que un algorithme de descente converge ssi
+ $$ \forall x_0 \in \mathbb{R}^n \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$
+\end{Def}
- %\bibitem[9]{K2} \bsc{Kant}, Prolégomènes à toute métaphysique future, Traduction de Louis Guilermit, Vrin, 1986.\\
+\subsubsection{Principe de démonstration de convergence}
- %\bibitem[10]{KU} Thomas \bsc{Kuhn}, La structure des révolutions scientifiques, Flammarion Champs Sciences, 2008.
+Une technique classique en optimisation pour obtenir des résultats de convergence globale consiste à montrer que l’algorithme de descente considéré vérifie une inégalité du type :
+$$ J(x_k) - J(x_{k+1}) \geq c\norme{\nabla J(x_k)}^2, $$
+où $ c $ est une constante réelle.
+\newline
+En sommant ces inégalités pour $ k $ variant de $ 0 $ à $ N - 1 $, on obtient :
+$$ \forall N \in \mathbb{N} \ J(x_0) - J(x_N) \geq c \sum_{i=0}^{N-1}\norme{\nabla J(x_i)}^2 $$
+Si $ J $ est bornée inférieurement, alors nécessairement $ J(x_0 ) - J(x_N) $ est majorée et donc la somme partielle est majorée, et donc la série $ (\sum\limits_{i=0}^{N-1}\norme{\nabla J(x_i)}^2)_{N \in \mathbb{N}} $ converge, ce qui implique :
+$$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$
+\begin{Def}
+ On considère $ (x_n)_{n \in \mathbb{N}} $, la suite des itérés donnés par un algorithme convergent. On note $ x^\ast $ la limite de la suite $ (x_n)_{n \in \mathbb{N}} $ et on suppose que $ x_k \neq x^\ast $, pour tout $ k \in \mathbb{N} $. La convergence de l’algorithme est alors dite :
+ \begin{itemize}
+ \item linéaire si l'erreur décroît linéairement i.e. :
+ $$ \exists \tau \in ]0,1[ \ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}} = \tau $$
+ \item superlinéaire si :
+ $$ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}} = 0 $$
+ \item d'ordre $ p $ si :
+ $$ \exists \tau \geq 0 \ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}^p} = \tau $$
+ En particulier, si $ p = 2 $, la convergence est dite quadratique.
+ \end{itemize}
+\end{Def}
+L'étude plus détaillée de différents algorithmes de descente qui utilisent différentes méthodes de recherche linéaire pour optimiser $ \varphi $ ainsi que leurs convergences sort du cadre de ce projet.
- %\bibitem[11]{L} Marc \bsc{Lachièze-Rey}, Initiation à la cosmologie, 3ème édition, Dunod, 2000.\\
+\section{Méthode Newtonienne}
- %\bibitem[12]{Mas} Thierry \bsc{Masson}, Cours de géométrie différentielle, groupe et algèbre de Lie, fibrés et connexions, 2010.\\
+Les hypothèses sur $ \mathcal{P} $ de la section précédente restent les mêmes dans cette section. L’algorithme de Newton en optimisation est une application directe de l’algorithme de Newton pour la résolution d’équations du type : $ F(x) = 0 $. En optimisation sans contrainte, l’algorithme de Newton cherche les solutions de l’équation :
+$$ \nabla J(x) = 0, $$
+autrement dit, les points critiques de la fonction $ J $ à minimiser.
+\newline
+En supposant $ J $ de classe $ \mathcal{C}^2 $ et la matrice hessienne $ H[J](x_k) $ inversible, une itération de l’algorithme de Newton s’écrit :
+$$ x_{k+1} = x_k - H[J](x_k)^{-1} \nabla J(x_k), $$
+où $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ est appelée direction de Newton. La direction $ d_k $ est également l’unique solution du problème :
+$$ \underset{d \in \mathbb{R}^n}{\mathrm{argmin}} \ J(x_k) + \langle \nabla J(x_k),d \rangle + \frac{1}{2}\langle H[J](x_k)d,d \rangle $$
+Autrement dit, $ d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
+À condition que la matrice $ H[J](x_k) $ soit définie positive à chaque itération, la méthode de Newton est bien une méthode de descente à pas fixe égal à $ 1 $.
+\newline
+Les propriétés remarquables de cet algorithme sont :
+
+\begin{tabular}{|p{20em}|p{20em}|}
+ \hline
+ Avantages & Inconvénients \\
+ \hline
+ sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). & \\
+ \hline
+ & les difficultés et le coût de calcul de la hessienne $ H[J](x_k) $ : l’expression analytique des dérivées secondes est rarement disponible dans les applications. \\
+ \hline
+ & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $. \\
+ \hline
+ & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la hessienne est singulière. \\
+ \hline
+ & pas de distinction entre minima, maxima et points stationnaires. \\
+ \hline
+\end{tabular}
+\newline
+La question que l’on se pose est donc : comment forcer la convergence globale de l’algorithme de Newton ? L’idée des méthodes de type Newton consiste à reprendre l’algorithme de Newton en remplaçant les itérations par :
+$$ x_{k+1} = x_k - s_k H_k^{-1} \nabla J(x_k), $$
+où
+\begin{itemize}
+ \item la matrice $ H_k $ est une approximation de la hessienne $ H[J](x_k) $.
+ \item $ s_k > 0 $ est le pas calculé par une recherche linéaire bien choisie.
+\end{itemize}
+Plusieurs questions se posent alors :
+\begin{itemize}
+ \item Comment déterminer une matrice $ H_k $ qui soit une “bonne” approximation de la hessienne à l’itération $ k $ sans utiliser les informations de second ordre et garantir que $ H_k^{-1} \nabla J(x_k) $ soit bien une direction de descente de $ J $ en $ x_k $, sachant que la direction de Newton, si elle existe, n’en est pas nécessairement une ?
+ \item Comment conserver les bonnes propriétés de l’algorithme de Newton ?
+\end{itemize}
+Nous ne répondrons pas à ces questions qui sont hors du cadre de ce projet. Cette section permet d'introduire certains prérequis pour l'étude de la méthode PQS et de rendre compte de sa filiation.
+
+\section{Méthode PQS (ou SQP)}
+
+Nous supposons les fonctions $ J,g,h $ à valeurs réelles et de classe $ \mathcal{C}^1 $. Trouver une solution d’un problème d’optimisation sous contraintes fonctionnelles consiste à déterminer un point optimal $ x^\ast $ et des multiplicateurs associés $ (\lambda^\ast,\mu^\ast) $. Deux grandes familles de méthodes peuvent être définies pour la résolution des problèmes d’optimisation sous contraintes : les méthodes primales et les méthodes duales. Les approches primales se concentrent sur la détermination du point $ x^\ast $, les multiplicateurs $ (\lambda,\mu) $ ne servant souvent qu’à vérifier l’optimalité de $ x^\ast $. Les méthodes duales quant à elles mettent l’accent sur la recherche des multiplicateurs en travaillant sur un problème d’optimisation déduit du problème initial par \textit{dualité}.
+
+\subsection{Problème quadratique sous contraintes linéaires}
+
+Nous introduisons les différentes approches développées pour la résolution des problèmes de programmation quadratique avec contraintes d'égalités et d’inégalités linéaires.
+\newline
+Ce type de problème quadratique se pose sous la forme :
+$$
+ \mathcal{PQ} \left \{
+ \begin{array}{l}
+ \displaystyle\min_{x \in \mathbb{R}^n} c^\top x + \frac{1}{2} x^\top \mathcal{Q} x \\
+ A^\top x + b \leq 0 \\
+ A^{\prime^\top} x + b^\prime = 0
+ \end{array}
+ \right .
+$$
+où $$ \mathcal{Q} \in \mathcal{M}_n(\mathbb{R}) \ symétrique, c \in \mathbb{R}^n, A \in \mathcal{M}_{n,p}(\mathbb{R}), b \in \mathbb{R}^p, A^\prime \in \mathcal{M}_{n,q}(\mathbb{R}), b^\prime \in \mathbb{R}^q $$
+Or
+$$ A^{\prime^\top} x + b^\prime = 0 \iff A^{\prime^\top} x + b^\prime \leq 0 \land -A^{\prime^\top} x - b^\prime \leq 0 $$
+Donc le problème se ramène à :
+
+\subsubsection{Algorithme 1}
+
+\subsubsection{Algorithme 2}
+
+\subsection{Algorithmes Newtoniens}
+
+Les algorithmes newtoniens sont basés sur la linéarisation d’équations caractérisant les solutions que l’on cherche, fournies par les conditions d’optimalité d’ordre $ 1 $. Ces algorithmes sont \textit{primaux-duaux} dans le sens où ils génèrent à la fois une suite primale $ (x_k )_{k \in \mathbb{N}} $ convergeant vers une solution $ \overline{x} $ du problème considéré, et une suite duale $ (\lambda_k)_{k \in \mathbb{N}} $ (resp. $ ((\lambda_k, \mu_k))_{k \in \mathbb{N}} $) de multiplicateurs convergeant vers un multiplicateur optimal $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu})) $ associé à $ \overline{x} $.
+
+\subsection{Algorithme PQS}
+
+\subsubsection{Contraintes d’égalité}
+
+Considérons un problème d’optimisation différentiable $ \mathcal{P} $ avec contraintes d’égalité :
+$$
+ \mathcal{P} \left \{
+ \begin{array}{l}
+ \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
+ h(x) = 0
+ \end{array}
+ \right .
+$$
+où $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables.
+\newline
+Les conditions d’optimalité de Lagrange (ou \textit{KKT}) s’écrivent :
+$$ \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) = 0 \iff \nabla L(x,\lambda) = 0 $$
+donc $ \mathcal{P} $ devient :
+$$ \begin{pmatrix}
+ \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) \\
+ h(x)
+ \end {pmatrix} = 0 $$
+Pour résoudre ce système d’équations, utilisons la méthode de Newton dont une itération s’écrit ici :
+$$ H[L](x_k,\lambda_k)\begin{pmatrix}
+ x_{k+1} - x_k \\
+ \lambda_{k+1} - \lambda_k
+ \end{pmatrix} = -\nabla L(x_k,\lambda_k) $$
+soit :
+$$ \begin{pmatrix}
+ H_x[L](x_k,\lambda_k) & D_h(x_k)^\top \\
+ D_h(x_k) & 0
+ \end{pmatrix} \begin{pmatrix}
+ x_{k+1} - x_k \\
+ \lambda_{k+1} - \lambda_k
+ \end{pmatrix} = -\begin{pmatrix}
+ \nabla_x L(x_k,\lambda_k) \\
+ h(x_k)
+ \end{pmatrix} $$
+où $ D_h(x) $ désigne la matrice jacobienne de l’application $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ définie par :
+$$ D_h(x)^\top = \begin{bmatrix} \nabla h_1(x)^\top\ldots\nabla h_q(x)^\top \end{bmatrix} $$
+Posons : $ H_k = H_x[L](x_k,\lambda_k), \ d = x_{k+1} - x_k $ et $ \mu = \lambda_{k+1} $. L'itération s'écrit donc :
+$$ \begin{pmatrix}
+ H_k & D_h(x_k)^\top \\
+ D_h(x_k) & 0
+ \end{pmatrix} \begin{pmatrix}
+ d \\
+ \mu - \lambda_k
+ \end{pmatrix} = -\begin{pmatrix}
+ \nabla_x L(x_k,\lambda_k) \\
+ h(x_k)
+ \end{pmatrix} $$
+et est bien définie à condition que la matrice $ H_x[L](x_k,\lambda_k) $ soit inversible. Ce sera le cas si :
+\begin{enumerate}[label=(\roman*)]
+ \item Les colonnes $ \nabla h_1(x_k)^\top,\ldots,\nabla h_q(x_k)^\top $ de $ D_h(x_k)^\top $ sont linéairement indépendants : c’est la condition première de \textit{KTT} ou condition de qualification des contraintes.
+ \item Quel que soit $ d \neq 0 $ tel que $ D_h(x_k)d = 0, \ d^\top H_k d > 0 $ : c’est la condition suffisante d’optimalité du second ordre dans le cas de contraintes d’égalité.
+\end{enumerate}
+Revenons à l’itération. Elle s’écrit encore :
+$$
+ \left \{
+ \begin{array}{r c l}
+ H_kd + \sum\limits_{i=1}^q(\mu_i - \lambda_{k_i})\nabla h_i(x_k) & = & -\nabla_x L(x_k,\lambda_k) \\
+ \nabla h_i(x_k)^\top d + h_i(x_k) & = & 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+$$
+Or $ \nabla_x L(x_k,\lambda_k) = \nabla J(x_k) + \sum\limits_{i=1}^{q} \lambda_{k_i} \nabla h_i(x_k) $, d'où :
+$$
+ \left \{
+ \begin{array}{r c l}
+ H_kd + \sum\limits_{i=1}^q\mu_i\nabla h_i(x_k) & = & -\nabla J(x_k) \\
+ \nabla h_i(x_k)^\top d + h_i(x_k) & = & 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+$$
+On reconnait dans le système ci-dessus les conditions d’optimalité de Lagrange du problème quadratique suivant :
+$$
+ \mathcal{PQ}_k \left \{
+ \begin{array}{l}
+ \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
+ h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+$$
+Le problème $ \mathcal{PQ}_k $ peut être vu comme la minimisation d’une approximation quadratique du Lagrangien de $ \mathcal{P} $ avec une approximation linéaire des contraintes.
+\newline
+Comme son nom l’indique, la méthode PQS consiste à remplacer le problème initial par une suite de problèmes quadratiques sous contraintes linéaires plus faciles à résoudre. L’algorithme est le suivant :
- %\bibitem[13]{Poi} Henri \bsc{Poincaré}, La Science et L'Hypothèse, Flammarion, Paris, 1968.\\
+\hrulefill
+\newline
+ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ.
+\newline
+\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $, $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ différentiables, $ x_0 \in \mathbb{R}^n $ point initial arbitraire, $ \lambda_0 \in \mathbb{R}^q $ multiplicateur initial, $ \varepsilon > 0 $ précision demandée.
+\newline
+\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
+\begin{enumerate}
+ \item $ k := 0 $.
+ \item Tant que $ \norme{\nabla L(x_k,\lambda_k)} > \varepsilon $,
+ \begin{enumerate}
+ \item Résoudre le sous-problème quadratique :
+ $$
+ \mathcal{PQ}_k \left \{
+ \begin{array}{l}
+ \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
+ h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+ $$
+ et obtenir la solution primale $ d_k $ et le multiplicateur $ \lambda^{\prime} $ associé à la contrainte d’égalité.
+ \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ k := k + 1 $.
+ \end{enumerate}
+ \item Retourner $ x_k $.
+\end{enumerate}
+
+\hrulefill
+
+\subsubsection{Contraintes d’inégalité}
+
+Intéressons nous maintenant aux problèmes avec contraintes d’égalité et d’inégalité :
+$$
+ \mathcal{P} \left \{
+ \begin{array}{l}
+ \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
+ g(x) \leq 0 \\
+ h(x) = 0
+ \end{array}
+ \right .
+$$
+où $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $, $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables.
+\newline
+Selon le même principe qu’avec contraintes d’égalité seules, on linéarise les contraintes et on utilise une approximation quadratique du Lagrangien à l'aide de développements de Taylor-Young en $ x_k $ et $ (x_k,\lambda_k,\mu_k) $ respectivement :
+$$ L(x,\lambda,\mu) = J(x) + \lambda^\top g(x) + \mu^\top h(x), \ \lambda \in \mathbb{R}_+^p \land \mu \in \mathbb{R}^q $$
+Soit à l'ordre 2 pour le Lagrangien :
+$$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$
+et à l'ordre 1 pour les contraintes :
+$$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
+$$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
+En posant $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $, on obtient le sous problème quadratique $ \mathcal{PQ}_k $ :
+
+\hrulefill
+\newline
+ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ.
+\newline
+\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $, $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$, $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ différentiables, $ x_0 \in \mathbb{R}^n $ point initial arbitraire, $ \lambda_0 \in \mathbb{R}_+^p $ et $ \mu_0 \in \mathbb{R}_+^q $ multiplicateurs initiaux, $ \varepsilon > 0 $ précision demandée.
+\newline
+\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
+\begin{enumerate}
+ \item $ k := 0 $.
+ \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $,
+ \begin{enumerate}
+ \item Résoudre le sous-problème quadratique :
+ $$
+ \mathcal{PQ}_k \left \{
+ \begin{array}{l}
+ \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
+ g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0 \\, \ \forall j \in \{1,\ldots,p\} \\
+ h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+ $$
+ et obtenir la solution primale $ d_k $ et les multiplicateurs $ \lambda^{\prime} $ et $ \mu^{\prime} $ associé aux contraintes d’inégalité et d’égalité respectivement.
+ \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $.
+ \end{enumerate}
+ \item Retourner $ x_k $.
+\end{enumerate}
+
+\hrulefill
+\newline
+Afin que le sous-programme quadratique $ \mathcal{PQ}_k $ admette une unique solution, la plupart des implémentations actuelles de PQS utilisent une approximation du hessien $ H_k $ du Lagrangien qui soit définie positive, en particulier celle fournie par les techniques quasi-newtonienne (BFGS) par exemple.
+\newline
+Etant une méthode newtonienne, l’algorithme PQS converge localement quadratiquement pourvu que les points initiaux $ (x_0,\lambda_0 ) $ (resp. $ (x_0,\lambda_0,\mu_0) $) soient dans un voisinage d’un point stationnaire $ \overline{x} $ et de ses multiplicateurs associés $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu}) $). Bien entendu, il est possible de globaliser l’algorithme en ajoutant une étape de recherche linéaire.
+
+\subsection{Stratégie d'approximation de la hessienne}
+
+\subsubsection{Équation de sécante et approximation}
+
+L'approximation $ H_k $ de la hessienne du Lagrangien peut être obtenu par la relation :
+$$ \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) \approx H[L](x_{k+1},\lambda_{k+1},\mu_{k+1})(x_{k+1} - x_k) $$
+On construit une approximation $ H_{k+1} $ de $ H[L](x_{k+1},\lambda_{k+1},\mu_{k+1}) $ comme solution de l’équation :
+$$ H_{k+1}(x_{k+1} - x_k) = \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) $$
+appelée équation de sécante ou équation de quasi-Newton.
+\newline
+De façon similaire, on peut construire une approximation $ B_{k+1} $ de $ H[L](x_{k+1},\lambda_{k+1},\mu_{k+1})^{-1} $ comme solution de l’équation :
+$$ B_{k+1}(\nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1})) = x_{k+1} - x_k $$
+Dans les deux cas, les équations de quasi-Newton forment un système sous-déterminé à $ n $ équations et $ n^2 $ inconnues. Il existe donc une infinité de matrices $ H_{k+1} $ pouvant convenir.
+\newline
+Une stratégie commune est de calculer $ (x_{k+1},\lambda_{k+1},\mu_{k+1}) $ pour une matrice $ H_k $ donnée et faire une mise à jour de $ H_k $ de rang 1 ou 2 :
+$$ H_{k+1} = H_k + U_k $$
+
+\subsubsection{Mises à jour DFP et BFGS}
+
+\subsection{Exemple d'utilisation de PQS}
+
+Considérons le problème $ \mathcal{P} $ suivant :
+$$
+ \mathcal{P} \left \{
+ \begin{array}{l}
+ \displaystyle\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2 \\
+ g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 \\
+ \end{array}
+ \right .
+$$
+où $$ (r,r_1,r_2) \in \mathbb{R}_+^3. $$
+\textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $ la précision, $ (x_0,y_0,z_0) = $ point initial et $ (\lambda_{0_1},\lambda_{0_2}) = $ multiplicateur initial.
+\newline
+Le Lagrangien $ L $ de $ \mathcal{P} $ : $$ L((x,y,z),(\lambda_1,\lambda_2)) = x^2 + y^2 + z^2 -r^2 + \lambda_1(x^2 + y^2 - r_1^2) + \lambda_2(x^2 + z^2 -r_2^2). $$
+\newline
+Le gradient de $ J $ : $$ \nabla J(x,y,z) = (\frac{\partial J}{\partial x}(x,y,z),\frac{\partial J}{\partial y}(x,y,z),\frac{\partial J}{\partial z}(x,y,z)) = (2x,2y,2z). $$
+\newline
+Le gradient de $ g $ : $$ \nabla g(x,y,z) = (\nabla g_1(x,y,z),\nabla g_2(x,y,z)) $$
+$$ = ((\frac{\partial g_1}{\partial x}(x,y,z),\frac{\partial g_1}{\partial y}(x,y,z),\frac{\partial g_1}{\partial z}(x,y,z)),(\frac{\partial g_2}{\partial x}(x,y,z),\frac{\partial g_2}{\partial y}(x,y,z),\frac{\partial g_2}{\partial z}(x,y,z)) $$
+$$ = ((2x,2y,0),(2x,0,2z)). $$
+\newline
+Le gradient du Lagrangien $ L $ :
+$$ \nabla L((x,y,z),(\lambda_1,\lambda_2)) = \nabla J(x,y,z) + \lambda_1 \nabla g_1(x,y,z) + \lambda_2 \nabla g_2(x,y,z)) $$
+\newline
+La matrice hessienne de $ J $ : $$ H[J](x,y,z) =
+ \begin{pmatrix}
+ \frac{\partial^2 J}{\partial^2 x}(x,y,z) & \frac{\partial^2 J}{\partial x\partial y}(x,y,z) & \frac{\partial^2 J}{\partial x\partial z}(x,y,z) \\
+ \frac{\partial^2 J}{\partial y\partial x}(x,y,z) & \frac{\partial^2 J}{\partial^2 y}(x,y,z) & \frac{\partial^2 J}{\partial y\partial z}(x,y,z) \\
+ \frac{\partial^2 J}{\partial z\partial x}(x,y,z) & \frac{\partial^2 J}{\partial z\partial y}(x,y,z) & \frac{\partial^2 J}{\partial^2 z}(x,y,z) \\
+ \end{pmatrix} =
+ \begin{pmatrix}
+ 2 & 0 & 0 \\
+ 0 & 2 & 0 \\
+ 0 & 0 & 2 \\
+ \end{pmatrix} = 2Id_{\mathbb{R}^3} $$
+On en déduit que $ H[J](x,y,z) $ est inversible et que $ H[J](x,y,z)^{-1} = \frac{1}{2}Id_{\mathbb{R}^3} $.
+
+\hrulefill
+
+\subsection{Trace d'éxécution de PQS}
+
+Utilisons le problème $ \mathcal{P} $ précédent :
+
+$$
+ \mathcal{P} \left \{
+ \begin{array}{l}
+ \displaystyle\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2 \\
+ g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 \\
+ \end{array}
+ \right .
+$$
+où $$ (r,r_1,r_2) \in \mathbb{R}_+^3. $$
+\textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $, $ (x_0,y_0,z_0) = (100, 100 ,0)$ et $(\lambda_{0_1},\lambda_{0_2}) = (1 , 1)$, les rayons : $r= 100$ et $r1 = r2 = 10$.
+\newline
+Le Lagrangien $ L $ de $ \mathcal{P} $ : $$ L((x,y,z),(\lambda_1,\lambda_2)) = x^2 + y^2 + z^2 -r^2 + \lambda_1(x^2 + y^2 - r_1^2) + \lambda_2(x^2 + z^2 -r_2^2). $$
+\newline
+Le Lagrangien $ L $ de $ \mathcal{P} $ avec les valeurs :
+ $ L((100,100,0),(1,1)) = 100^2 + 100^2 + 0^2 -100^2 + 1 * (100^2 +100^2 - 10^2) + \lambda_2(100^2 + 100^2 -10^2). $
+ $ L((100,100,0),(1,1)) = 1000 + 1000 - 1000 + (1000 + 1000 - 100) + (1000 + 1000 -100). $
+ $ L((100,100,0),(1,1)) = 4800. $
+
+\newpage
+\begin{algorithmfloat}[#Algo 1]
+ \caption {Trace d'éxécution du PQS du problème $ \mathcal{P} $}
+ \begin{algorithmic}
+ \REQUIRE $g(x_0,y_0,z_0)\leq 0$, $(x_0,y_0,z_0) = (10, 10 ,10)$
+ \ENSURE $\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2$ and \newline $g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 $
+ \STATE \textbf{Data :}
+ \STATE $k \leftarrow 0, (x_k, y_k, z_k) \leftarrow (100, 100, 0), r \leftarrow 100$
+ \STATE $r_1 = r2 \leftarrow 10, \varepsilon \leftarrow 0.01$
+ \STATE $\lambda_1 = \lambda_2 = 1$
+ \STATE $ H[J](x,y,z)^{-1}\leftarrow \begin{pmatrix}
+ 0.5 & 0 & 0 \\
+ 0 & 0.5 & 0 \\
+ 0 & 0 & 0.5 \\ \end{pmatrix} $
+\newline
+
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (100,100,0) $
+\newline
+ \STATE {//calcule des deux sous partie de du gradient de $ g $: }
+ \STATE $ \nabla g_1(x_a,y_a,z_a) = ((2x_a,2y_a,0)$ \hfill $ //résultat : (20, 20, 0)$
+ \STATE $ \nabla g_2(x_a,y_a,z_a) = (2x_a,0,2z_a))$ \hfill $ //résultat : (20, 0, 20)$
+ \STATE $ \nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
+\newline
+ \WHILE{$ (\norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $ or k $ \leq 10)$}
+
+ \STATE { //première itération :}
+
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (220, 220, 40)$
+ \STATE $ \nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = (x_L , y_L, z_L) $
+\newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(50,50,0))$
+ \newline
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (50,50,0)$
+ \newline
+ \STATE {//Incrémentation de k}
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 1$
+\newline
+
+ \STATE {//Deuxième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (100,100,0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (120, 120, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(25,25,0))$
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (25,25,0)$
+ \newline
+ \STATE {//Incrémentation de k}
+\STATE $ k \leftarrow k+1$\hfill $ //k = 2$
+\newline
+
+\STATE {//Troisième itération :}
+\STATE{//Calcule du gradient de $ J $ :}
+\STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (50,50,0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (70, 70, 0)$
+\STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+\STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+\STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(12.5,12.5,0))$
+\STATE {//Calcul nouvelles valeurs des coordonnées}
+\newline
+\STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (12.5,12.5,0)$
+\STATE {//Incrémentation de k}
+\STATE $ k \leftarrow k+1$\hfill $ //k = 3$
+\newline
+
+\STATE {//Quatrième itération :}
+\STATE{//Calcule du gradient de $ J $ :}
+\STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (25,25,0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (45, 45, 0)$
+\STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+\STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+\STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(6.25,6.25,0))$
+\newline
+\STATE {//Calcul nouvelles valeurs des coordonnées}
+\STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (6.25,6.25,0)$
+\STATE {//Incrémentation de k}
+\newline
+\STATE $ k \leftarrow k+1$\hfill $ //k = 4$
+\STATE $ $
+
+\STATE {//Cinquième itération :}
+\STATE{//Calcule du gradient de $ J $ :}
+\STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (12.5,12.5,0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (32.5, 32.5, 0)$
+\STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+\STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+\STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(3.125,3.125,0))$
+\newline
+\STATE {//Calcul nouvelles valeurs des coordonnées}
+\STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (3.125,3.125,0)$
+\newline
+\STATE {//Incrémentation de k}
+\STATE $ k \leftarrow k+1$\hfill $ //k = 5$
+\newline
+
+\STATE {//Sixième itération :}
+\STATE{//Calcule du gradient de $ J $ :}
+\STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (6.25,6.25,0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (26.25, 26.25, 0)$
+\STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+\STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+\STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(1.5625,1.5625,0))$
+\STATE {//Calcul nouvelles valeurs des coordonnées}
+\newline
+\STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (1.5625,1.5625,0)$
+\STATE {//Incrémentation de k}
+\newline
+\STATE $ k \leftarrow k+1$\hfill $ //k = 6$
+\newline
+
+\STATE {//Septième itération :}
+\STATE{//Calcule du gradient de $ J $ :}
+\STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (3.125, 3.125, 0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (23.125, 23.125, 0)$
+\STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+\STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+\STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.78125,0.78125,0))$
+\STATE {//Calcul nouvelles valeurs des coordonnées}
+\newline
+\STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.78125,0.78125,0)$
+\STATE {//Incrémentation de k}
+\newline
+\STATE $ k \leftarrow k+1$\hfill $ //k = 7$
+\newline
- %\bibitem[14]{Mav} Stamatia \bsc{Mavridès}, La Relativité, Que sais-je, 4ème édition, PUF, 2000.\\
+\STATE {//Huitième itération :}
+\STATE{//Calcule du gradient de $ J $ :}
+\STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (1.5625, 1.5625, 0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (21.5625, 21.5625, 0)$
+\STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+\STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+\STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.390625,0.390625,0))$
+\newline
+\STATE {//Calcul nouvelles valeurs des coordonnées}
+\STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.390625,0.390625,0)$
+\newline
+\STATE {//Incrémentation de k}
+\STATE $ k \leftarrow k+1$\hfill $ //k = 8$
+\newline
- %\bibitem[15]{R} Robert \bsc{Rynasiewicz}, The Lessons of the Hole Argument, The British Journal of the Philosophy of Science,
- %vol; 45 (2), 407-436, Oxford University Press, Oxford Journals, 1994. \\
+\STATE {//neuvième itération :}
+\STATE{//Calcule du gradient de $ J $ :}
+\STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (0.78125, 0.78125, 0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (20.78125, 20.78125, 0)$
+\STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+\STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+\STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.1953125,0.1953125,0))$
+\newline
+\STATE {//Calcul nouvelles valeurs des coordonnées}
+\STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.1953125,0.1953125,0)$
+\newline
+\STATE {//Incrémentation de k}
+\STATE $ k \leftarrow k+1 \hfill //k = 9$
+\newline
- %\bibitem[16]{S} Standford Encyclopedia of Philosophy.\\
+\STATE {//Dixième itération :}
+\STATE{//Calcule du gradient de $ J $ :}
+\STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (0.390625, 0.390625, 0) $
+\newline
+\STATE {//Calcule du gradient de $ L $ : }
+\STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (20.390625, 20.390625, 0)$
+\STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+\newline
+\STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+\STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.097665625,0.097665625,0))$
+\newline
+\STATE {//Calcul nouvelles valeurs des coordonnées}
+\STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.097665625,0.097665625,0)$
+\newline
+\STATE {//Incrémentation de k}
+\STATE $ k \leftarrow k+1$\hfill $ //k = 10$
+\newline
+\STATE {// Fin de la boucle "while" car nous avons atteint k =10, condition mettant fin à la //boucle}
+\newline
- %\bibitem[17]{W} Wikipedia.\\
+ \ENDWHILE
- %\bibitem[1]{Bachtold} {\bf Manuel Bächtold}, L'interprétation de la mécanique quantique, une approche pragmatique, Collection vision des sciences, Hermann, 2008 .\\
+\end{algorithmic}
+\end{algorithmfloat}
- %\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.\\
+\hrulefill
- %\bibitem[4]{Diu} {\bf Bernard Diu}, Le congrès de Solvay de 1927: petite chronique d'un grand évènement, Bibnum.\\
+\bibliographystyle{plain}
+\bibliography{stdlib_sbphilo}
- %\bibitem[1]{B} \bsc{Aristote}, Métaphysique, traduction J.Tricot, Vrin, 1974.\\
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\end{thebibliography}
+\end{document}
repositories / Projet_Recherche_Operationnelle.git / blobdiff