Multiplicateur de Lagrange : Mathématique

D	L	M	M	J	V	S
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

« Mathématique du crime Guillermo Martinez, Eduardo Jimenez Roman (broché). Paru en 09/2004 Livre | Page d'accueil | Multiplicateurs de Lagrange »

14/02/2011

Multiplicateur 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).

É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$

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.

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} rac{partial F(X)}{partial x_1} - sum_{k=1}^m lambda_k rac{partial g_k(X)}{partial x_1} &=& 0 dots rac{partial F(X)}{partial x_n} - sum_{k=1}^m lambda_k rac{partial g_k(X)}{partial x_n} &=& 0 g_1(X) &=& 0 dots g_m(X) &=& 0 end{matrix} ight .$

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.

Exemple

Supposons que l'on veuille déterminer le rayon R et la hauteur H d'un cylindre qui minimise la surface S de celui-ci, tout en ayant un volume V imposé. Le problème s'écrit sous la forme :

Minimiser $S(R,H)=2 imes pi imes R imes (R+H)$

sous $g(R,H)=pi imes R^2 imes H-V=0$

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

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

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

On cherche donc à annuler le Gradient du Lagrangien, soit : $abla L=0$ ,

ce qui nous amène au système :

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