Understanding why it works
Have you ever wondered why we use the Lagrange multiplier to solve constrained optimization problems?
Is it just a clever technique?
Comme il est très facile à utiliser, nous l’apprenons comme une arithmétique de base en la pratiquant jusqu’à ce que nous puissions le faire par cœur.
Mais vous êtes-vous déjà demandé pourquoi cela fonctionne? Ça marche toujours ? Sinon, pourquoi pas ?
Si vous voulez connaître les réponses à ces questions, vous êtes au bon endroit.
Je vais le démystifier pour vous.
Un exemple de problème d’optimisation contrainte
Au cas où vous ne connaissiez pas ce que sont les optimisations contraintes, j’ai écrit un article qui l’explique. Sinon, veuillez lire la suite.
Supposons que nous ayons une montagne qui ressemble à celle ci-dessous:
The height of a location (x, y) is given as follows (in kilometers):
Further suppose, the mountain has an eruption:
From the top, it looks like below:
The eruption area is given as follows:
Cela signifie que le bord de l’éruption est donné comme suit:
Donc, le bord ressemble à ceci.
Supposons que nous voulions connaître la position la plus élevée de l’éruption sur cette montagne.
Cela signifie que la position la plus élevée doit être sur la ligne de bord de l’éruption que nous pouvons exprimer comme suit:
Tout emplacement (x, y) qui satisfait g(x, y)=0 est au bord de l’éruption.
Par conséquent, le problème d’optimisation contrainte consiste à trouver le f(x, y) maximum satisfaisant g(x, y) = 0.
Intuition sur la façon de résoudre le problème d’optimisation contrainte
Intuitivement, nous savons que la hauteur maximale de l’éruption se situe autour de l’endroit indiqué par la flèche bleue.
Nous recherchons la ligne de contour la plus élevée qui touche le bord de l’éruption.
Définissons l’équation de la ligne de contour:
f(x, y) = H
H est une valeur constante indiquant la hauteur du contour.
Pour une valeur donnée de H, il existe un ensemble de valeurs (x, y) qui satisfont f(x, y) = H.
Le gradient de f(x, y) indique la direction où la hauteur augmente qui est perpendiculaire à la ligne de contour.
The gradient is a vector of partial derivatives.
Similarly, the gradient of g(x, y) is perpendicular to the edge of the eruption area.
La ligne de contour la plus élevée qui touche le bord de l’éruption doit avoir le gradient de f(x, y) en parallèle à la ligne de gradient de g(x, y).
Si le gradient de la ligne de contour n’est pas parallèle au gradient du bord de l’éruption, il y aura une zone d’éruption située plus haut que la ligne de contour.
Nous devons donc trouver un tel point (x, y) où le gradient de f(x, y) est parallèle au gradient de g(x, y).
Le multiplicateur de Lagrange et le Lagrangien
Mettons notre objectif dans une formule mathématique.
Le gradient de f(x, y) et le gradient de g(x, y) doivent être parallèles mais ils peuvent avoir une taille et une direction différentes.
grad f(x, y) = λ grad g(x, y)
Ce λ est appelé multiplicateur de Lagrange du nom du mathématicien qui a introduit la mécanique lagrangienne en 1788.
À ce stade, nous ne connaissons pas la valeur de λ qui pourrait être quelque chose comme 2.5, -1, ou bien. Cela signifie simplement que les deux gradients doivent être parallèles.
On peut réorganiser l’équation comme suit:
grad { f(x, y) - λ g(x, y) } = 0
Le zéro signifie ici le vecteur avec des zéros: (0,0).
Et nous appelons l’intérieur des accolades comme le Lagrangien L.
L = f(x, y) - λ g(x, y)
Donc, nous disons que ce qui suit est la condition requise.
grad L = 0
Le gradient du Lagrangien nous donne deux équations.
Mais nous avons trois inconnues xy, et λ. Comment pouvons-nous résoudre ces équations?
En fait, nous avons une équation de plus qui est la g(x, y) = 0.
Ainsi, nous pouvons résoudre les trois équations pour trouver l’emplacement le plus élevé (x, y) qui satisfait la contrainte.
Le problème devient maintenant un exercice arithmétique.
La réponse est f(x, y) = 2 where x = 1 and y = 1.
Vous pouvez vérifier les valeurs avec les équations.
De plus, λ = -4/5 ce qui signifie que ces gradients sont dans les directions opposées comme prévu.
Dans l’ensemble, le multiplicateur de Lagrange est utile pour résoudre les problèmes d’optimisation des contraintes.
Nous trouvons le point (x, y)où le gradient de la fonction que nous optimisons et le gradient de la fonction de contrainte sont en parallèle à l’aide du multiplicateur λ.
En résumé, nous avons suivi les étapes ci-dessous :
- Identifiez la fonction à optimiser (maximiser ou minimiser) :
f(x, y) - Identifiez la fonction pour la contrainte:
g(x, y) = 0 - Définissez le Lagrangien
L = f(x, y) - λ g(x, y) - Résolvez
grad L = 0satisfaisant la contrainte
C’est aussi mécanique que ce qui précède et vous savez maintenant pourquoi cela fonctionne.
Mais il y a encore quelques choses à mentionner.
Quand cela ne fonctionne pas
J’ai fait quelques hypothèses en expliquant le multiplicateur de Lagrange.
Tout d’abord, j’ai supposé que toutes les fonctions ont des gradients (les premières dérivées), ce qui signifie que les fonctions f(x, y) et g(x, y) sont continues et lisses.
Deuxièmement, je suppose également que f(x, y) a les dérivées secondes afin que nous puissions vérifier si la solution (x, y) est réellement le maximum ou non.
Ces deux hypothèses sont vraies dans cet exemple, mais dans les problèmes réels, vous devez vérifier cela pour pouvoir utiliser le multiplicateur de Lagrange pour résoudre votre problème d’optimisation des contraintes.
Troisièmement, j’ai simplifié la question afin que nous n’ayons à traiter qu’un seul maximum.
En d’autres termes, la forme de la montagne est définie de telle sorte qu’il n’y ait qu’une seule solution au problème d’optimisation contrainte.
Dans des problèmes réels, la montagne pourrait avoir des formes plus compliquées avec plusieurs sommets et vallées.
Dans ce cas, nous devons traiter le problème d’optimisation globale (c’est-à-dire plusieurs maxima locaux).
Au lieu de cela, l’exemple de cet article ne traite que d’un maximum local qui est également le maximum global.
J’espère que votre compréhension du multiplicateur de Lagrange est optimale maintenant.