La méthode des multiplicateurs de Lagrange est une méthode simple et élégante pour trouver les minima locaux ou les maxima locaux d’une fonction soumise à des contraintes d’égalité ou d’inégalité. Les multiplicateurs de Lagrange sont aussi appelés multiplicateurs indéterminés. Dans ce tutoriel, nous parlerons de cette méthode lorsque des contraintes d’égalité sont données.

Dans ce tutoriel, vous découvrirez la méthode des multiplicateurs de Lagrange et comment trouver le minimum ou le maximum local d’une fonction lorsque des contraintes d’égalité sont présentes.

Après avoir terminé ce tutoriel, vous saurez :

• Comment trouver des points de maximum ou de minimum locaux d’une fonction avec des contraintes d’égalité
• Méthode des multiplicateurs de Lagrange avec contraintes d’égalité

Commençons.

Présentation du didacticiel

Ce tutoriel est divisé en 2 parties ; elles sont:

1. Méthode des multiplicateurs de Lagrange avec contraintes d’égalité
2. Deux exemples résolus

Conditions préalables

Pour ce tutoriel, nous supposons que vous savez déjà ce que sont :

Vous pouvez revoir ces concepts en cliquant sur les liens ci-dessus.

Quelle est la méthode des multiplicateurs de Lagrange avec contraintes d’égalité ?

Supposons que nous ayons le problème d’optimisation suivant :

Minimiser f(x)

Sujet à:

g_1(x) = 0

g_2(x) = 0

…

g_n(x) = 0

La méthode des multiplicateurs de Lagrange construit d’abord une fonction appelée fonction de Lagrange telle que donnée par l’expression suivante.

L(x, ??) = f(x) + 𝜆_1 g_1(x) + 𝜆_2 g_2(x) + … + 𝜆_n g_n(x)

Ici ?? représente un vecteur de multiplicateurs de Lagrange, c’est-à-dire

?? = [ 𝜆_1, 𝜆_2, …, 𝜆_n]^T

Pour trouver les points de minimum local de f(x) soumis aux contraintes d’égalité, on trouve les points stationnaires de la fonction de Lagrange L(x, ??), c’est-à-dire que nous résolvons les équations suivantes :

xL = 0

∂L/∂𝜆_i = 0 (pour i = 1..n)

Par conséquent, nous obtenons un total de m+n équations à résoudre, où

m = nombre de variables dans le domaine de f

n = nombre de contraintes d’égalité.

En bref, les points de minimum local seraient la solution des équations suivantes :

∂L/∂x_j = 0 (pour j = 1..m)

g_i(x) = 0 (pour i = 1..n)

Exemples résolus

Cette section contient deux exemples résolus. Si vous résolvez les deux, vous aurez une assez bonne idée de la façon d’appliquer la méthode des multiplicateurs de Lagrange aux fonctions de plus de deux variables et d’un plus grand nombre de contraintes d’égalité.

Exemple 1 : Une contrainte d’égalité

Résolvons le problème de minimisation suivant :

Minimiser : f(x) = x^2 + y^2

Sous réserve de : x + 2y – 1 = 0

La première étape consiste à construire la fonction de Lagrange :

L(x, y, ) = x^2 + y^2 + 𝜆(x + 2y – 1)

Nous avons les trois équations suivantes à résoudre :

L/∂x = 0

2x + = 0 (1)

L/∂y = 0

2y + 2𝜆 = 0 (2)

L/∂𝜆 = 0

x + 2y -1 = 0 (3)

En utilisant (1) et (2), on obtient :

= -2x = -y

Le branchement de (3) nous donne :

x = 1/5

y = 2/5

Par conséquent, le point minimum local se situe à (1/5, 2/5) comme le montre la figure de droite. La figure de gauche montre le graphique de la fonction.

Exemple 2 : Deux contraintes d’égalité

Supposons que nous voulions trouver le minimum de la fonction suivante soumise aux contraintes données :

minimiser g(x, y) = x^2 + 4y^2

Sujet à:

x + y = 0

x^2 + y^2 – 1 = 0

La solution de ce problème peut être trouvée en construisant d’abord la fonction de Lagrange :

L(x, y, 𝜆_1, _2) = x^2 + 4y^2 + 𝜆_1(x + y) + 𝜆_2(x^2 + y^2 – 1)

Nous avons 4 équations à résoudre :

L/∂x = 0

2x + _1 + 2x 𝜆_2 = 0 (1)

L/∂y = 0

8y + 𝜆_1 + 2y 𝜆_2 = 0 (2)

L/∂𝜆_1 = 0

x + y = 0 (3)

L/∂𝜆_2 = 0

x^2 + y^2 – 1 = 0 (4)

La résolution du système d’équations ci-dessus nous donne deux solutions pour (x,y), c’est-à-dire que nous obtenons les deux points :

(1/sqrt(2), -1/sqrt(2))

(-1/sqrt(2), 1/sqrt(2))

La fonction ainsi que ses contraintes et son minimum local sont indiqués ci-dessous.

Relation avec les problèmes de maximisation

Si vous avez une fonction à maximiser, vous pouvez la résoudre de la même manière, en gardant à l’esprit que la maximisation et la minimisation sont des problèmes équivalents, c’est-à-dire,

maximiser f(x) équivaut à minimiser -f(x)

Importance de la méthode des multiplicateurs de Lagrange dans l’apprentissage automatique

De nombreux algorithmes d’apprentissage automatique bien connus utilisent la méthode des multiplicateurs de Lagrange. Par exemple, les fondements théoriques de l’analyse en composantes principales (ACP) sont construits à l’aide de la méthode des multiplicateurs de Lagrange avec contraintes d’égalité. De même, le problème d’optimisation dans les machines à vecteurs de support SVM est également résolu en utilisant cette méthode. Cependant, dans SVMS, des contraintes d’inégalité sont également impliquées.

Rallonges

Cette section répertorie quelques idées pour étendre le didacticiel que vous souhaiterez peut-être explorer.

• Optimisation avec contraintes d’inégalité
• Conditions KKT
• Soutenir les machines vectorielles

Si vous explorez l’une de ces extensions, j’aimerais le savoir. Postez vos découvertes dans les commentaires ci-dessous.

Lectures complémentaires

Cette section fournit plus de ressources sur le sujet si vous cherchez à approfondir.

Tutoriels

Ressources

Livres

• Thomas’ Calculus, 14e édition, 2017. (basé sur les travaux originaux de George B. Thomas, révisés par Joel Hass, Christopher Heil, Maurice Weir)
• Calcul, 3e édition, 2017. (Gilbert Strang)
• Calculus, 8e édition, 2015. (James Stewart)

Sommaire

Dans ce tutoriel, vous avez découvert quelle est la méthode des multiplicateurs de Lagrange. Concrètement, vous avez appris :

• Multiplicateurs de Lagrange et fonction de Lagrange
• Comment résoudre un problème d’optimisation lorsque des contraintes d’égalité sont données

Avez-vous des questions?

Posez vos questions dans les commentaires ci-dessous et je ferai de mon mieux pour y répondre.