rapport/ProjetOptimRO.tex

   1 \documentclass[12pt,oneside,a4paper]{book}
   2
   3
   4 %%%%%Packages
   5
   6
   7 \usepackage{latexsym}
   8 \usepackage{amsmath}
   9 \usepackage{amsthm}
  10 \usepackage{mathtools}
  11 \usepackage{amssymb}
  12 \usepackage[utf8]{inputenc}
  13 \usepackage[francais]{babel}
  14 \usepackage{color}
  15 \usepackage{geometry}
  16 \usepackage{graphicx}
  17 \usepackage{amsfonts}
  18 \usepackage[T1]{fontenc}
  19 \usepackage{multirow}
  20 \usepackage{fancyhdr}
  21 \usepackage{tocbibind}
  22 \usepackage{lmodern}
  23 \usepackage{enumitem}
  24
  25
  26 %%%%%Marges & en-t\^etes
  27
  28 \geometry{hmargin=2.3cm, vmargin=3cm}
  29 \fancyhf{} % supprime les en-t\^etes et pieds pr\'ed\'efinis
  30 \fancyhead[FC]{\bfseries\thepage} % N∞page centre bas
  31 \fancyhead[HC]{\footnotesize\leftmark} % chapitre centre haut
  32 \renewcommand{\headrulewidth}{0.2pt} % filet en haut
  33 \addtolength{\headheight}{0.5pt} % espace pour le filet
  34 \renewcommand{\footrulewidth}{0.2pt} % filet en bas
  35
  36
  37 %%%%%Th\'eor\`eme et d\'efinitions
  38
  39 \newtheorem{Def}{D\'efinition}
  40 \newtheorem{Not}[Def]{Notation}
  41 \newtheorem{Th}{Th\'eor\`eme}
  42 \newtheorem{Prop}[Th]{Proposition}
  43 \newtheorem{Cor}[Th]{Corollaire}
  44 \newtheorem{Rmq}{Remarque}
  45
  46 \newcommand{\norme}[1]{\left\Vert #1 \right\Vert}
  47
  48 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  49 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  50
  51 \begin{document}
  52
  53 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  55
  56 %%%%%Page de garde
  57
  58 \begin{center}
  59
  60  %\includegraphics[scale=0.5]{logo_sciences_rvb.png}\\
  61  \includegraphics[scale=0.5]{polytech.png}\\
  62
  63  \vspace*{0.5cm}
  64
  65  \footnotesize{
  66   \large \bf D\'epartement d'Informatique, Réseaux et Multimédia\\
  67   \large \bf  5ème année\\
  68  }
  69
  70  \vspace*{0.5cm}
  71
  72  %\large{Master 2 Professionnel\\
  73  %Math\'ematiques et Informatique des Nouvelles Technologies\\}
  74
  75  \large{Projet \\ en \\ Optimisation et Recherche Opérationnelle \\}
  76
  77  \vspace*{0.7cm}
  78
  79  \begin{tabular}{c}
  80   \hline
  81   ~                                                             \\
  82   \LARGE\textbf {Programmation Quadratique Séquentielle ou PQS} \\
  83   \LARGE\textbf {en}                                            \\
  84   \LARGE\textbf {Optimisation non linéraire sous contraintes}   \\
  85   ~                                                             \\
  86   \hline
  87  \end{tabular}
  88
  89  \vspace*{0.7cm}
  90
  91  \includegraphics[scale=0.4]{CE.PNG}\\
  92
  93  \vspace*{0.5cm}
  94
  95  \large par\\
  96
  97  %\large  \bsc{}\\
  98  %\normalsize{M\'emoire encadr\'e par :} \large St\'ephane \bsc{Ballet}\\
  99
 100  \vspace*{0.2cm}
 101  \large  {\bf Jérôme \bsc{Benoit} et Sylvain \bsc{Papa}}\\
 102
 103  %\vspace*{0.1cm}
 104
 105  % \large sous la direction de \\
 106
 107  %\vspace*{0.1cm}
 108
 109  %Eric Audureau et Thierry Masson
 110
 111  %\vspace*{1cm}
 112
 113  \vspace*{1cm}
 114
 115  %\normalsize{Licence de Mathématiques 3ème année}
 116  \normalsize{Année 2018-2019}
 117
 118 \end{center}
 119
 120 \thispagestyle{empty}
 121
 122 \newpage
 123
 124
 125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 126 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 127
 128
 129 \pagestyle{plain}
 130 \frontmatter
 131
 132
 133 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 135
 136
 137 %%%%%Table des mati\`eres
 138
 139 \tableofcontents
 140
 141 \begin{figure}[!b]
 142  \begin{center}
 143   %\includegraphics{logo_fac2}
 144   \includegraphics[scale=0.04]{amu}
 145  \end{center}
 146 \end{figure}
 147
 148 \newpage
 149
 150
 151 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 152 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 153
 154
 155 \mainmatter
 156 \pagestyle{fancy}
 157
 158
 159 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 160 \chapter{Introduction générale}
 161
 162 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.
 163 \newline
 164 Elle est loin d'être exhaustive mais devrait suffire dans le cadre de ce projet.
 165
 166 \vspace{.5em}
 167
 168 \section{Qu'est-ce que la recherche opérationnelle?}
 169
 170 \subsection{Présentation rapide}
 171
 172 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).
 173 \newline
 174 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.
 175
 176 \subsection{Définition de la problèmatique}
 177
 178 Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la recherche opérationnelle :
 179 \begin{Def}
 180  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}$.
 181  \newline
 182  La problèmatique $ \mathcal{P} $ se définit par :
 183  $$
 184   \mathcal{P} \left \{
 185   \begin{array}{l}
 186    \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
 187    g(x) \leq 0                                 \\
 188    h(x) = 0
 189   \end{array}
 190   \right .
 191  $$
 192 \end{Def}
 193 \begin{Def}
 194  On définit $ \mathcal{C} $ l'ensemble des contraintes par :
 195  $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$
 196 \end{Def}
 197 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} $.
 198
 199 \section{Qu'est-ce que l'optimisation?}
 200
 201 \subsection{Définition}
 202
 203 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.
 204 \newline
 205 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.
 206
 207 \subsection{Quelques définitions annexes}
 208
 209 Définissons quelques notions supplémentaires de base nécessaires à la suite :
 210 \begin{Def}
 211  On définit le Lagrangien associé à $ \mathcal{P} $ par :
 212  $$ \begin{array}{r c l}
 213    L : \mathbb{R}^n \times \mathbb{R}^q \times \mathbb{R}_+^p & \longrightarrow & \mathbb{R}                                                                                                      \\
 214    (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)           \\
 215                                                               &                 & L(x,\lambda,\mu) = J(x) + \langle \lambda,h(x) \rangle_{\mathbb{R}^q} + \langle \mu,g(x) \rangle_{\mathbb{R}^p}
 216   \end{array} $$
 217  où l’on note $ \lambda $  et $ \mu $ les vecteurs de coordonnées respectives $ (\lambda_1,\ldots,\lambda_q) $ et $ (\mu_1,\ldots,\mu_p) $.
 218 \end{Def}
 219 \begin{Def}
 220  Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
 221  \newline
 222  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} $.
 223 \end{Def}
 224 \begin{Rmq}
 225  $ A \subset \mathbb{R}^n $ est un ouvert $ \iff A = \mathring{A} $.
 226 \end{Rmq}
 227 \begin{Def}
 228  Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
 229  \newline
 230  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} $.
 231 \end{Def}
 232 \begin{Rmq}
 233  $ A \subset \mathbb{R}^n $ est un fermé $ \iff A = \overline{A} $.
 234 \end{Rmq}
 235 \begin{Def}
 236  Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $.
 237  \newline
 238  On dit que $ f $ est continue en $ x^\ast $ si
 239  $$ \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 $$
 240 \end{Def}
 241 \begin{Def}
 242  Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $.
 243  \newline
 244  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
 245  $$ t \longmapsto f(x^\ast_1,\ldots,x^\ast_{k-1},x^\ast_k + t,x^\ast_{k+1},\ldots,x^\ast_n) $$
 246  définie sur un voisinage de $ 0 $ dans $ \mathbb{R} $ et à valeurs dans $ \mathbb{R} $ est dérivable en $ 0 $.
 247  \newline
 248  Dans ce cas on note
 249  $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$
 250  cette dérivée.
 251 \end{Def}
 252 \begin{Def}
 253  Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $
 254  et $ x^\ast, h \in \mathbb{R}^n $.
 255  \newline
 256  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
 257  \[
 258   f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h})
 259  \]
 260  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} $
 261  telle que $ \lim\limits_{h \rightarrow 0} \varepsilon_{x^\ast}(h) = 0 $ et
 262  \[
 263   f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h)
 264  \]
 265  On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $.
 266 \end{Def}
 267 \begin{Rmq}
 268  On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$.
 269 \end{Rmq}
 270 \begin{Def}
 271  Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
 272  \newline
 273  Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
 274  \[
 275   \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
 276  \]
 277 \end{Def}
 278 \begin{Rmq}
 279  $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle $
 280 \end{Rmq}
 281 \begin{Def}
 282  Soit $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ un fonction de classe $ \mathcal{C}^2 $.
 283  On définit la matrice hessienne de $ f $ en $ x^\ast $ par :
 284  $$ H[f](x^\ast) =
 285   \begin{pmatrix}
 286    \frac{\partial^2 f}{\partial x_1^2}(x^\ast)           & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n}(x^\ast) \\
 287    \vdots                                                &        & \vdots                                                \\
 288    \frac{\partial^2 f}{\partial x_n\partial x_1}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_n^2}(x^\ast)
 289   \end{pmatrix} $$
 290 \end{Def}
 291 \begin{Prop}
 292  \begin{enumerate}
 293   \item $ H[f](x^\ast) $ est une matrice symétrique (Théorème de symétrie de Schwarz).
 294   \item On a le développement de Taylor-Young à l'ordre 2 en $ x^\ast $ suivant :
 295         $$ 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) $$
 296         ou
 297         $$ 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) $$
 298         avec $ \frac{|\varepsilon(v)|}{\norme{v}} \rightarrow 0 $ quand $ \norme{v} \rightarrow 0 $.
 299  \end{enumerate}
 300 \end{Prop}
 301 \begin{proof}
 302  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.
 303 \end{proof}
 304
 305 \subsection{Conditions d'existence d'un extremum}
 306
 307 On peut démontrer que $ \mathcal{C }$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues.
 308 On peut en déduire que si $ J $ est continue, $ \mathcal{C }$ est un ensemble fermé et borné de $ \mathbb{R}^n $.
 309 \begin{Th}[Théorème de Weierstrass]
 310  Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue.
 311  \newline
 312  Alors : $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$
 313  Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $.
 314  \newline
 315  De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $.
 316 \end{Th}
 317 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}.
 318
 319 \subsection{Conditions de caractérisation d'un extremum}
 320
 321 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}.
 322 \newline
 323 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}.
 324
 325 \subsubsection{Conditions de Karuch-Kuhn-Tucker}\label{KKT}
 326
 327 \begin{Th}
 328  Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
 329  \newline
 330  Les conditions nécessaires pour que $ x^\ast \in \mathcal{C}$ soit un minimum local de $ J $ sont :
 331  \newline
 332  \newline
 333  \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.}
 334  \newline
 335  \newline
 336  et
 337  $$ \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 $$
 338  On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
 339 \end{Th}
 340 \begin{proof}
 341  Elle repose sur le lemme de Farkas \cite{FEA,RON}.
 342 \end{proof}
 343 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.
 344
 345
 346 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 347
 348 \chapter{Méthode de programmation quadratique séquentielle}
 349
 350 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.
 351
 352 \vspace{.5em}
 353
 354 \section{Methode de descente}\label{descente}
 355
 356 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.
 357
 358 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 :
 359 $$ x_{k+1} = x_k + s_kd_k $$ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $ et avec
 360 $$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
 361 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}.
 362
 363 \subsection{Définition d'une direction de descente}
 364
 365 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 :
 366 $$ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) $$
 367 Il est donc important d’analyser le comportement de la fonction $ J $ dans certaines direc-
 368 tions.
 369 \begin{Prop}
 370  Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $.
 371  \newline
 372  d est un vecteur de descente de $ J $ en $ x_0 \in \mathbb{R}^n $ ssi :
 373  $$ \nabla J(x_0)^\top d < 0 $$
 374  De plus
 375  $$ \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) $$
 376 \end{Prop}
 377 \begin{proof}
 378  Elle s'effectue en utilisant le développement de Taylor-Young de l’application $ t \longmapsto f(x_0 + td) $ à l’ordre 1.
 379 \end{proof}
 380 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 :
 381
 382 \hrulefill
 383 \newline
 384 ALGORITHME DE DESCENTE MODÈLE.
 385 \newline
 386 \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
 387 \newline
 388 \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
 389 \begin{enumerate}
 390  \item $ k := 0 $.
 391  \item Tant que "test d’arrêt" non satisfait,
 392        \begin{enumerate}
 393         \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
 394         \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). $$
 395         \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
 396        \end{enumerate}
 397  \item Retourner $ x_k $.
 398 \end{enumerate}
 399
 400 \hrulefill
 401
 402 \subsection{Choix de la direction de descente}
 403
 404 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 :
 405 \begin{itemize}
 406  \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}.
 407  \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}.
 408 \end{itemize}
 409 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.
 410
 411 \subsection{Critère d’arrêt}
 412
 413 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 $.
 414 \newline
 415 En pratique, un test d’arrêt devra être choisi pour garantir que l’algorithme s’arrête
 416 toujours après un nombre fini d’itérations et que le dernier point calculé soit suffisamment
 417 proche de $ x^\ast $.
 418
 419 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
 420 sans contrainte, on testera si
 421 $$ \norme{\nabla J(x_k)} < \varepsilon, $$
 422 auquel cas l’algorithme s’arrête et fournit l’itéré courant $ x_k $ comme solution.
 423
 424 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 :
 425 \begin{itemize}
 426  \item Stagnation de la solution : $ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $.
 427  \item Stagnation de la valeur courante : $ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $.
 428  \item Nombre d’itérations dépassant un seuil fixé à l’avance : $ k < IterMax $.
 429 \end{itemize}
 430 et généralement une combinaison de ces critères :
 431 \newline
 432 \newline
 433 Critère d’arrêt =
 434 \begin{tabular}{l}
 435  Test d’optimalité satisfait                                        \\
 436  OU (Stagnation de la valeur courante ET Stagnation de la solution) \\
 437  OU Nombre d’itérations maximum autorisé dépassé
 438 \end{tabular}
 439
 440 \subsection{La recherche linéaire}
 441
 442 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.
 443 \newline
 444 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 :
 445 $$ J(x_0 + sd) < J(x_0). $$
 446 Le choix de ce pas répond généralement à deux objectifs souvent contradictoires : trouver
 447 le meilleur pas possible et effectuer le moins de calculs possibles. Ces deux objectifs ont
 448 donné naissance à deux grandes familles : les algorithmes à pas fixe et ceux à pas optimal.
 449
 450 \hrulefill
 451 \newline
 452 RECHERCHE LINÉAIRE : PAS FIXE. $ s_k = s_{k-1} $
 453
 454 \hrulefill
 455
 456 \hrulefill
 457 \newline
 458 RECHERCHE LINÉAIRE : PAS OPTIMAL. $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
 459
 460 \hrulefill
 461 \newline
 462 Illustrées par les méthodes de descente de gradient, aucune de ces deux stratégies ne
 463 s’est révélée réellement convaincante : si la première peut être “risquée” du point de vue de
 464 la convergence, la seconde est souvent loin d’être triviale à mettre en oeuvre (sauf dans le
 465 cas quadratique) et généralement inutilement coûteuse : en effet, à quoi bon calculer très
 466 précisément un pas optimal dans une direction qui n’est peut-être pas la bonne ? (comme
 467 c’est par exemple le cas pour la méthode de plus profonde descente). Les recherches
 468 linéaires modernes reposent sur l’idée qu’un pas de descente acceptable est un pas qui fait
 469 “suffisamment” décroître la fonction objectif. Reste alors à définir les pas qui sont
 470 acceptables et ceux qui ne le sont pas.
 471 \begin{Def}
 472  On appelle $ \varphi : s \in \mathbb{R} \longmapsto J(x + sd)$ la fonction mérite associée à $ J $ en $ x $.
 473 \end{Def}
 474 \begin{Def}
 475  Dans le cas où $ J $ est différentiable sur $ \mathcal{C} $, on dit que un algorithme de descente converge ssi
 476  $$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$
 477 \end{Def}
 478
 479 \subsubsection{Principe de démonstration de convergence}
 480
 481 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 :
 482 $$ J(x_k) - J(x_{k+1}) \geq c\norme{\nabla J(x_k)}^2, $$
 483 où $ c $ est une constante réelle.
 484 \newline
 485 En sommant ces inégalités pour $ k $ variant de $ 0 $ à $ N - 1 $, on obtient :
 486 $$ \forall N \in \mathbb{N} \ J(x_0) - J(x_N) \geq c \sum_{i=0}^{N-1}\norme{\nabla J(x_i)}^2 $$
 487 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 :
 488 $$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$
 489 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 $ et le choix d'une direction ainsi que leurs convergences sort du cadre de ce projet.
 490
 491 \section{Méthode Newtonienne}
 492
 493 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 :
 494 $$ \nabla J(x) = 0, $$
 495 autrement dit, les points critiques de la fonction $ J $ à minimiser.
 496 \newline
 497 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 :
 498 $$ x_{k+1} = x_k - H[J](x_k)^{-1} \nabla J(x_k), $$
 499 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 :
 500 $$ \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 $$
 501 Autrement dit, $ d_k $ est le point de minimum global de l’approximation de second ordre de $ J $ au voisinage du point courant $ x_k $.
 502 A 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 $.
 503 \newline
 504 Les propriétés remarquables de cet algorithme sont :
 505
 506 \begin{tabular}{|p{20em}|p{20em}|}
 507  \hline
 508  Avantages                                                                                           & Inconvénients                                                                                                                                                     \\
 509  \hline
 510  sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). &                                                                                                                                                                   \\
 511  \hline
 512                                                                                                      & 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. \\
 513  \hline
 514                                                                                                      & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $.                                                                          \\
 515  \hline
 516                                                                                                      & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la    hessienne est singulière.                                                  \\
 517  \hline
 518                                                                                                      & pas de distinction entre minima, maxima et points stationnaires.                                                                                                  \\
 519  \hline
 520 \end{tabular}
 521 \newline
 522 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
 523 l’algorithme de Newton en remplaçant les itérations par :
 524 $$ x_{k+1} = x_k - s_k H_k^{-1} \nabla J(x_k), $$
 525 où
 526 \begin{itemize}
 527  \item la matrice $ H_k $ est une approximation de la hessienne $ H[J](x_k) $.
 528  \item $ s_k > 0 $ est le pas calculé par une recherche linéaire bien choisie.
 529 \end{itemize}
 530 Plusieurs questions se posent alors :
 531 \begin{itemize}
 532  \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 ?
 533  \item Comment conserver les bonnes propriétés de l’algorithme de Newton ?
 534 \end{itemize}
 535 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.
 536
 537 \section{Méthode PQS (ou SQP)}
 538
 539 Nous supposons les fonctions $ J,g,h $ à valeurs réelles et de classe $ \mathcal{C}^1 $.
 540 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 d’un multiplicateur en travaillant sur un problème d’optimisation déduit du problème initial par \textit{dualité}.
 541
 542 \subsection{Algorithmes newtoniens}
 543
 544 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}} $ de multiplicateurs convergeant vers un multiplicateur optimal $ \overline{\lambda} $ associé à $ \overline{x} $.
 545
 546 \subsection{Algorithme PQS}
 547
 548 \subsubsection{Contraintes d’égalité}
 549
 550 Considérons un problème d’optimisation différentiable $ \mathcal{P} $ avec contraintes d’égalité :
 551 $$
 552  \mathcal{P} \left \{
 553  \begin{array}{l}
 554   \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
 555   h(x) = 0
 556  \end{array}
 557  \right .
 558 $$
 559 où $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables.
 560 \newline
 561 Les conditions d’optimalité de Lagrange (ou \textit{KKT}) s’écrivent :
 562 $$ \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) = 0 \iff \nabla L(x,\lambda) = 0 $$
 563 donc $ \mathcal{P} $ devient :
 564 $$ \begin{pmatrix}
 565  \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) \\
 566  h(x)
 567  \end {pmatrix} = 0 $$
 568 Pour résoudre ce système d’équations, utilisons la méthode de Newton dont une itération s’écrit ici :
 569 $$ H[L](x_k,\lambda_k)\begin{pmatrix}
 570   x_{k+1} - x_k \\
 571   \lambda_{k+1} - \lambda_k
 572  \end{pmatrix} = -\nabla L(x_k,\lambda_k) $$
 573 soit :
 574 $$ \begin{pmatrix}
 575   H_x[L](x_k,\lambda_k) & D_h(x_k)^\top \\
 576   D_h(x_k)              & 0
 577  \end{pmatrix} \begin{pmatrix}
 578   x_{k+1} - x_k \\
 579   \lambda_{k+1} - \lambda_k
 580  \end{pmatrix} = -\begin{pmatrix}
 581   \nabla_x L(x_k,\lambda_k) \\
 582   h(x_k)
 583  \end{pmatrix}  $$
 584 où $ D_h(x) $ désigne la matrice jacobienne de l’application $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ définie par :
 585 $$ D_h(x)^\top = \begin{bmatrix} \nabla h_1(x)\ldots\nabla h_q(x) \end{bmatrix} $$
 586 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 :
 587 $$ \begin{pmatrix}
 588   H_k      & D_h(x_k)^\top \\
 589   D_h(x_k) & 0
 590  \end{pmatrix} \begin{pmatrix}
 591   d \\
 592   \mu - \lambda_k
 593  \end{pmatrix} = -\begin{pmatrix}
 594   \nabla_x L(x_k,\lambda_k) \\
 595   h(x_k)
 596  \end{pmatrix} $$
 597 et est bien définie à condition que la matrice $ H_x[L](x_k,\lambda_k) $ soit inversible. Ce sera le cas si :
 598 \begin{enumerate}[label=(\roman*)]
 599  \item Les colonnes $ \nabla h_1(x_k),\ldots,\nabla h_q(x_k) $ de $ D_h(x_k)^\top $ sont linéairement indépendants : c’est l’hypothèse de qualification des contraintes.
 600  \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é.
 601 \end{enumerate}
 602 Revenons à l’itération. Elle s’écrit encore :
 603 $$
 604  \left \{
 605  \begin{array}{r c l}
 606   H_kd + \sum\limits_{i=1}^q(\mu_i - \lambda_{k_i})\nabla h_i(x_k) & = & -\nabla_x L(x_k,\lambda_k)        \\
 607   \nabla h_i(x_k)^\top d + h_i(x_k)                                & = & 0, \ \forall i \in \{1,\ldots,q\}
 608  \end{array}
 609  \right .
 610 $$
 611 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ù :
 612 $$
 613  \left \{
 614  \begin{array}{r c l}
 615   H_kd + \sum\limits_{i=1}^q\mu_i\nabla h_i(x_k) & = & -\nabla J(x_k)                    \\
 616   \nabla h_i(x_k)^\top d + h_i(x_k)              & = & 0, \ \forall i \in \{1,\ldots,q\}
 617  \end{array}
 618  \right .
 619 $$
 620 On reconnait dans le système ci-dessus les conditions d’optimalité de Lagrange du
 621 problème quadratique suivant :
 622 $$
 623  \mathcal{PQ}_k \left \{
 624  \begin{array}{l}
 625   \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 626   h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 627  \end{array}
 628  \right .
 629 $$
 630 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.
 631 \newline
 632 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 :
 633
 634 \hrulefill
 635 \newline
 636 ALGORITHME SQP AVEC CONSTRAINTES D'ÉGALITÉ.
 637 \newline
 638 \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.
 639 \newline
 640 \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
 641 \begin{enumerate}
 642  \item $ k := 0 $.
 643  \item Tant que $ \norme{\nabla L(x_k,\lambda_k)} > \varepsilon $,
 644        \begin{enumerate}
 645         \item Résoudre le sous-problème quadratique :
 646               $$
 647                \mathcal{PQ}_k \left \{
 648                \begin{array}{l}
 649                 \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 650                 h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 651                \end{array}
 652                \right .
 653               $$
 654               et obtenir la solution primale $ d_k $ et le multiplicateur $ \lambda^{\prime} $ associé à la contrainte d’égalité.
 655         \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ k := k + 1 $.
 656        \end{enumerate}
 657  \item Retourner $ x_k $.
 658 \end{enumerate}
 659
 660 \hrulefill
 661
 662 \subsubsection{Contraintes d’inégalité}
 663
 664 Intéressons nous maintenant aux problèmes avec contraintes d’égalité et d’inégalité :
 665 $$
 666  \mathcal{P} \left \{
 667  \begin{array}{l}
 668   \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
 669   g(x) \leq 0                                 \\
 670   h(x) = 0
 671  \end{array}
 672  \right .
 673 $$
 674 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.
 675 \newline
 676 Selon le même principe qu’avec contraintes d’égalité seules, on linéarise les contraintes et on utilise une approximation quadratique du Lagrangien :
 677 $$ 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 $$
 678
 679 \hrulefill
 680 \newline
 681 ALGORITHME SQP AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ.
 682 \newline
 683 \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.
 684 \newline
 685 \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $.
 686 \begin{enumerate}
 687  \item $ k := 0 $.
 688  \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $,
 689        \begin{enumerate}
 690         \item Résoudre le sous-problème quadratique :
 691               $$
 692                \mathcal{PQ}_k \left \{
 693                \begin{array}{l}
 694                 \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
 695                 g_j(x_k) + \nabla g_j(x_k)^\top d = 0, \ \forall j \in \{1,\ldots,p\}                 \\
 696                 h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
 697                \end{array}
 698                \right .
 699               $$
 700               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.
 701         \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $.
 702        \end{enumerate}
 703  \item Retourner $ x_k $.
 704 \end{enumerate}
 705
 706 \hrulefill
 707 \newline
 708 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.
 709 \newline
 710 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.
 711
 712 \bibliographystyle{plain}
 713 \bibliography{stdlib_sbphilo}
 714
 715 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 716
 717 \end{document}