La méthode des multiplicateurs de Lagrange

Jérémie Decock (www.jdhp.org)

Attention:

Veuillez noter que ce document est en cours de rédaction. Dans son état actuel, il n'est pas destiné à être lu par d'autres personnes que ses auteurs.

À quoi ça sert ?

À trouver les extremums (minimums, maximums) d'une fonction $f$ d'une ou plusieurs variables $x_1, \dots, x_n$, sous réserve que l'ensemble solution respecte un contrainte d'égalité: $g(x_1, \dots, x_n) = 0$. Autrement dit la méthode des multiplicateurs de Lagrange va permettre de résoudre certains problèmes d'optimisation sous contraintes.

Exemple: maximiser $f(x_1,x_2)$ soumise aux contraintes $g(x_1,x_2)=0$.

Cas d'une fonction à une variable

Dans ce cas, on écrit simplement $x := x_1$.

On pose la fonction:

$$ \mathcal{L}(x, \lambda) = f(x) + \lambda g(x) $$

$\lambda$ est ce qu'on appelle un multiplicateur de Lagrange ; sa valeur n'est pas connue à priori.

Pour maximiser $\mathcal{L}$, on annule ses dérivées partielles (condition nécessaire du premier ordre). Le problème initial revient à résoudre le système d'équations à deux inconnues suivant:

$$ \left\{ \begin{array}{rcl} {\large \frac{\partial\mathcal{L}(x,\lambda)}{\partial x}} & = & 0 \\ {\large \frac{\partial\mathcal{L}(x,\lambda)}{\partial \lambda}} & = & 0 \end{array} \right. $$

Exemple

On cherche à résoudre le problème d'optimisation suivant:

$$ \begin{align} \max & \quad f(x) = a x^2 + b x + c \\ \text{s.t.} & \quad g(x) = a' x^2 + b' x + c' = 0 \end{align} $$

avec par exemple

$a = -\frac12$, $b = 0$, $c = 20$, $a' = 1$, $b' = 2$ et $c' = -10$

soit

$$ \begin{align} \max & \quad f(x) = -\frac12 x^2 + 20 \\ \text{s.t.} & \quad g(x) = x^2 + 2 x - 10 = 0 \end{align} $$

avec:

  • $f(x) = -\frac12 x^2 + 20$ la fonction à maximiser
  • $g(x) = x^2 + 2 x - 10 = 0$ la contrainte à respecter

La fonction de Lagrange correspondant à ce problème est:

$$ \begin{align} \mathcal{L}(x,\lambda) & = f(x) + \lambda g(x) \\ & = -\frac12 x^2 + 20 + \lambda (x^2 + 2 x - 10) \\ & = -\frac12 x^2 + 20 + \lambda x^2 + 2 \lambda x - 10 \lambda \\ & = (-\frac12 + \lambda) x^2 + 2 \lambda x + 20 - 10 \lambda \end{align} $$

Les conditions du premier ordre (annulation des dérivées premières) sont données par:

$$ \begin{align} \left\{ \begin{array}{rcl} {\large \frac{\partial\mathcal{L}(x,\lambda)}{\partial x}} & = & 0 \\ {\large \frac{\partial\mathcal{L}(x,\lambda)}{\partial \lambda}} & = & 0 \end{array} \right. & \Leftrightarrow \left\{ \begin{array}{rcl} 2 (-\frac12 + \lambda) x + 2 \lambda & = & 0 \\ x^2 + 2 x - 10 & = & 0 \end{array} \right. \\ & \\ & \Leftrightarrow \left\{ \begin{array}{rcl} -x + 2 \lambda x + 2 \lambda & = & 0 \\ x & = & -\sqrt{11} - 1 \quad \text{ou} \quad x = \sqrt{11} - 1 \end{array} \right. \\ & \\ & \Leftrightarrow \left\{ \begin{array}{rcl} 2 \lambda x + 2 \lambda & = & x \\ x & = & -\sqrt{11} - 1 \quad \text{ou} \quad x = \sqrt{11} - 1 \end{array} \right. \\ & \\ & \Leftrightarrow \left\{ \begin{array}{rcl} \lambda & = & \frac{x}{2x + 2} \\ x & = & -\sqrt{11} - 1 \quad \text{ou} \quad x = \sqrt{11} - 1 \end{array} \right. \\ & \\ & \Leftrightarrow \left\{ \begin{array}{rcl} \lambda & = & \frac{-\sqrt{11} - 1}{2(-\sqrt{11} - 1) + 2} \\ x & = & -\sqrt{11} - 1 \end{array} \right. \quad \text{ou} \quad \left\{ \begin{array}{rcl} \lambda & = & \frac{\sqrt{11} - 1}{2(\sqrt{11} - 1) + 2} \\ x & = & \sqrt{11} - 1 \end{array} \right. \\ & \\ & \Leftrightarrow \left\{ \begin{array}{rcl} \lambda & = & \frac{\sqrt{11} + 1}{2 \sqrt{11}} \\ x & = & -\sqrt{11} - 1 \end{array} \right. \quad \text{ou} \quad \left\{ \begin{array}{rcl} \lambda & = & \frac{\sqrt{11} - 1}{2 \sqrt{11}} \\ x & = & \sqrt{11} - 1 \end{array} \right. \end{align} $$

Les points stationnaires de $\mathcal{L}$ sont quelquepart sur les droites vertes...

Cas d'une fonction à deux variables

On pose la fonction:

$$ \mathcal{L}(x_1,x_2,\lambda) = f(x_1,x_2) + \lambda g(x_1,x_2) $$

$\lambda$ est ce qu'on appelle un multiplicateur de Lagrange ; sa valeur n'est pas connue à priori.

Pour maximiser $\mathcal{L}$, on annule ses dérivées partielles (condition nécessaire du premier ordre). Le problème initial revient à résoudre le système d'équations à trois inconnues suivant:

$$ \left\{ \begin{array}{rcl} {\large \frac{\partial\mathcal{L}(x_1,x_2,\lambda)}{\partial x_1}} & = & 0 \\ {\large \frac{\partial\mathcal{L}(x_1,x_2,\lambda)}{\partial x_2}} & = & 0 \\ {\large \frac{\partial\mathcal{L}(x_1,x_2,\lambda)}{\partial \lambda}} & = & 0 \end{array} \right. $$

Exemple

On cherche le rectangle d'aire maximum et de périmètre constant $P$.

Plus formellement, on cherche à résoudre le problème d'optimisation suivant:

$$ \begin{align} \max & \quad f(x_1,x_2) = x_1 x_2 \\ \text{s.t.} & \quad g(x_1,x_2) = 2x_1 + 2x_2 - P = 0 \end{align} $$

avec:

  • $x_1$ et $x_2$ les dimensions du rectangle (respectivement la largeur et la hauteur)
  • $f(x_1,x_2) = x_1 x_2$ l'aire du rectangle (la fonction à maximiser)
  • $g(x_1,x_2) = 2x_1 + 2x_2 - P = 0$ la contrainte sur le périmètre du rectangle ($2x_1 + 2x_2 = P$)

La fonction de Lagrange correspondant à ce problème est:

$$ \mathcal{L}(x_1,x_2,\lambda) = x_1 x_2 + \lambda (2x_1 + 2x_2 - P) $$

Les conditions du premier ordre (annulation des dérivées premières) sont données par:

$$ \begin{align} \left\{ \begin{array}{rcl} {\large \frac{\partial\mathcal{L}(x_1,x_2,\lambda)}{\partial x_1}} & = & 0 \\ {\large \frac{\partial\mathcal{L}(x_1,x_2,\lambda)}{\partial x_2}} & = & 0 \\ {\large \frac{\partial\mathcal{L}(x_1,x_2,\lambda)}{\partial \lambda}} & = & 0 \end{array} \right. & \Leftrightarrow \left\{ \begin{array}{rcl} x_2 + 2 \lambda & = & 0 \\ x_1 + 2 \lambda & = & 0 \\ 2x_1 + 2x_2 - P & = & 0 \end{array} \right. \\ & \\ & \Leftrightarrow \left\{ \begin{array}{rcl} \color{red} \lambda & \color{red} = & {\color{red} {\large \frac{-x_2}{2}}} \\ \color{red} \lambda & \color{red} = & {\color{red} {\large \frac{-x_1}{2}}} \\ 2x_1 + 2x_2 - P & = & 0 \end{array} \right. \\ & \\ & \Leftrightarrow \left\{ \begin{array}{rcl} x_1 & = & x_2 \\ 2x_1 + 2x_2 - P & = & 0 \end{array} \right. \\ & \\ & \Leftrightarrow \left\{ \begin{array}{rcl} x_1 & = & x_2 \\ P & = & 2x_1 + 2x_1 = 4x_1 = 4x_2 \end{array} \right. \end{align} $$

On a donc ${\large \frac{-x_2}{2}} = {\large \frac{-x_1}{2}}$ c'est à dire $x_1 = x_2$. Ainsi, le carré ($x_1 = x_2$) est le rectangle d'aire maximum pour un périmètre donné $P$.

Remarque: il est préférable d'éliminer $\lambda$ dés le début des calculs car c'est une variable auxiliaire dont la valeur n'est pas utile.

Bibliographie

Quelques livres sur le sujet:

  • Optimisation et contrôle des systèmes linéaires (chapitre 3) de Maïtine Bergounioux aux editions Dunod
  • Toutes les mathématiques et les bases de l'informatique (p. 566-567) de Horst Stöcker aux editions Dunod