Multiplicateur de Lagrange

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant l'analyse.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Pour les articles homonymes, voir Théorème de Lagrange.

Le multiplicateur de Lagrange est une méthode permettant de trouver des points stationnaires (maximum, minimum...) d'une fonction dérivable d'une ou plusieurs variables.

Cette technique est utile entre autres pour résoudre les problèmes d'optimisation sous contrainte(s) (linéaire(s)). Supposons que le problème soit de trouver un extremum d'une fonction de N variables, tout en imposant K contraintes sur les valeurs de celle-ci. La méthode consiste à introduire une inconnue scalaire supplémentaire - appelée multiplicateur de Lagrange - par contrainte; il y a donc K multiplicateurs. On forme ensuite une combinaison linéaire de la fonction et des contraintes, où les coefficients des contraintes sont les multiplicateurs de Lagrange. Le problème passe ainsi d'un problème d'optimisation avec contrainte à un problème non contraint, qui peut être résolu par une méthode adaptée (gradient conjugué, par exemple).

Hugh Everett a généralisé la méthode aux fonctions non-dérivables, sous réserve de disposer d'un algorithme déterminant l'optimum (ou les optima) d'une fonction sans contrainte (dans la pratique, on doit se contenter d'heuristiques).

Sommaire

1 Écriture du problème
2 Exemples
- 2.1 Équation du mouvement
- 2.2 Calcul d'un volume
3 Notes

[modifier] Écriture du problème

Soit le problème d'optimisation : $\mathrm{Min}\ F(X)$ où $X = \{x_1, x_2, \ldots x_n\}$

soumis à des contraintes d'égalité $g_k(X) = 0 \qquad k = 1, 2, ... m$ ^[1]

On définit alors la fonction $\displaystyle H(X, \lambda)$ comme :

$H(X, \lambda) = F(X) + \sum_{k=1}^m \lambda_k g_k (X)$

On cherche maintenant l'extremum de $H (X,λ)$ :

$\frac{\partial H(X, \lambda)}{\partial x_i} = 0,$

ce qui est équivalent à :

$\frac{\partial F(X)}{\partial x_i} = - \sum_{k=1}^m \lambda_k \frac{\partial g_k(X)}{\partial x_i}.$

Autrement dit, la méthode des multiplicateurs de Lagrange stipule qu'on atteint la valeur optimale de $F (X)$ pour les valeurs $x i$ de $X$ qui satisfont le système :

$\left\{ \begin{matrix} \dfrac{\partial F(X)}{\partial x_1} + \displaystyle\sum_{k=1}^m \lambda_k \frac{\partial g_k(X)}{\partial x_1} &=& 0 \\ \vdots \\ \dfrac{\partial F(X)}{\partial x_n} + \displaystyle\sum_{k=1}^m \lambda_k \frac{\partial g_k(X)}{\partial x_n} &=& 0 \\ g_1(X) &=& 0\\ \vdots\\ g_m(X) &=& 0\\ \end{matrix} \right .$

Cette méthode peut être généralisée aux problèmes d'optimisation incluant des contraintes d'inégalités (ou non linéaires) en utilisant les conditions de Kuhn-Tucker. Mais également sur des fonctions discrètes à maximiser ou minimiser sous contraintes, moyennant un changement d'interprétation, en utilisant la méthode des multiplicateurs d'Everett (ou de Lagrange généralisés), plus volontiers appelée méthode des pénalités.

[modifier] Exemples

[modifier] Équation du mouvement

L'application de la méthode des multiplicateurs de Lagrange en mécanique classique fait apparaître le sens de ces multiplicateurs. Les équations du mouvement peuvent s'exprimer à l'aide du formalisme lagrangien, c'est-à-dire à partir de la fonction de Lagrange, et des équations d'Euler-Lagrange. On considère une masse ponctuelle, qui se déplace sur un cercle ayant pour rayon $R$ . Le lagrangien en coordonnées polaires est donné par :

$L = \frac{1}{2} m (\dot{r}^2+r^2\dot{\varphi}^2)$

avec la condition $g = r - R = 0$

On obtient la fonction :

$L^\prime=L+\lambda g$

De l'équation d'Euler-Lagrange^[2],

$\frac{d}{dt}\frac{\partial L^\prime}{\partial \dot{r}}-\frac{\partial L^\prime}{\partial r} = 0$ ,

on trouve alors :

$m \ddot{r} - m r \dot{\varphi}^2 - \lambda =0$

avec $\ddot{r}=0$ et $r = R$ .

$\lambda = -mR \dot{\varphi}^2$

Le terme $λ g$ correspondant à la force centripète exprimé en coordonnées polaires, lorsque le mouvement d'une masse ponctuelle est limitée à se déplacer sur un cercle.

[modifier] Calcul d'un volume

Supposons que l'on veuille déterminer le rayon R et la hauteur H d'un cylindre qui minimisent la surface S de celui-ci, tout en ayant un volume V imposé. Le problème peut se formaliser de la manière suivante :

On cherche à minimiser la fonction $S(R,H)=2\times \pi\times R\times (R+H)$
avec la condition $g(R,H)=\pi\times R^2\times H-V=0$

Ayant une seule contrainte, on ajoute un seul multiplicateur de Lagrange :

$L(R,H,\lambda)=S(R,H)+\lambda\times g(R,H)$

Le problème revient maintenant à minimiser le Lagrangien $L(R,H,\lambda)=2\times\pi\times R\times H+2\times\pi\times R^2+\lambda\times(\pi\times R^2\times H-V)$

On cherche donc à annuler le Gradient du Lagrangien, soit : $\nabla L=0$ , ce qui nous amène au système :

$\left\{ \begin{matrix} \frac{\partial L}{\partial R} &=& 2.\pi.H+4.\pi.R+2.\pi.\lambda.H.R &=& 0 &(1)&\\ \\ \frac{\partial L}{\partial H} &=& 2.\pi.R+\lambda.\pi.R^2 &=& 0 &(2)&\\ \\ \frac{\partial L}{\partial \lambda} &=& \pi.R^2.H-V &=& 0 &(3)&\\ \end{matrix} \right .$

L'équation (2) nous donne : $R=-\frac{2}{\lambda}$
L'équation (1) nous donne : $H=-\frac{4}{\lambda}$
L'équation (3) nous donne enfin : $\lambda=-2\times\left(\frac{2.\pi}{V}\right)^{1/3}$

Si le volume imposé est $V = 1 m 3$ , l'optimum de la fonction S est :

$\left\{ \begin{matrix} R\approx 0,542(m)\\ \\ H\approx 1,084(m)\\ \end{matrix} \right .$

Et la fonction vaut $S\approx 5,536m^2$ en ce point.

[modifier] Notes

↑ Si le nombre m de contraintes est supérieur au nombre n de variables, le problème est surcontraint et n'admet en général pas de solution.
↑ on s'intéresse ici qu'a la composante radiale, car la contrainte ne dépend que de cette coordonnée.