Image via https://elements.envato.com under license to Naoki Shibuya
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?
omdat het zeer eenvoudig te gebruiken is, leren we het als een basis rekenkunde door het te oefenen totdat we het uit ons hoofd kunnen doen.
maar heb je je ooit afgevraagd waarom het werkt? Werkt het altijd? Zo niet, waarom niet?
als u de antwoorden op deze vragen wilt weten, bent u op de juiste plaats.
Ik zal het voor je demystificeren.
een voorbeeld beperkt optimalisatie probleem
indien u niet bekend bent met wat beperkt optimalisaties zijn, heb ik een artikel geschreven dat het uitlegt. Zo niet, lees dan verder.
stel dat we een berg hebben die er hieronder uitziet:
Image by author using Grapher on macOS
The height of a location (x, y) is given as follows (in kilometers):
Further suppose, the mountain has an eruption:
Image by author using Grapher on macOS
From the top, it looks like below:
Image by author using Grapher on macOS
The eruption area is given as follows:
Dit betekent dat de rand van de uitbarsting is gegeven als volgt:
Dus, de rand ziet er zo uit.
Image by author using Grapher on macOS
stel dat we de hoogste positie van de uitbarsting op deze berg willen weten.
Dit betekent dat de hoogste positie op de randlijn van de eruptie moet zijn die we als volgt kunnen uitdrukken:
elke locatie(x, y)dat voldoet aang(x, y)=0aan de rand van de uitbarsting.
daarom is het beperkte optimalisatieprobleem het vinden van het maximum f(x, y) bevredigend g(x, y) = 0.
Intuã tief weten we dat de maximale hoogte van de uitbarsting rond de plek ligt waar de blauwe pijl aangeeft.
Image by author using Grapher on macOS
we zijn op zoek naar de hoogste contourlijn die de rand van de uitbarsting raakt.
laten we de vergelijking van de contourlijn definiëren:
f(x, y) = H
H is een constante waarde die de hoogte van de contour aangeeft.
voor een gegeven waarde van H is er een verzameling van (x, y) waarden die voldoet aan f(x, y) = H.
de gradiënt van f(x, y) geeft de richting aan waar de hoogte toeneemt die loodrecht staat op de contourlijn.
Image by author using Grapher on macOS
The gradient is a vector of partial derivatives.
Similarly, the gradient of g(x, y) is perpendicular to the edge of the eruption area.
de hoogste contourlijn die de rand van de uitbarsting raakt moet de gradiënt vanf(x, y)parallel aan de gradiënt vang(x, y).
Image by author
als de gradiënt van de contourlijn niet parallel loopt met de gradiënt van de eruptierand, zal er een gebied zijn dat hoger ligt dan de contourlijn.
Image by author
So, we need to find such point(x, y)waar het verloop vanf(x, y)is parallel aan de gradiënt vang(x, y).
de Lagrange multiplier en de Lagrangian
laten we ons doel in een wiskundige formule zetten.
de gradiënt van f(x, y) en de gradiënt van g(x, y) moeten parallel zijn, maar ze kunnen een andere grootte en richting hebben.
grad f(x, y) = λ grad g(x, y)
Deze λ wordt Lagrange-vermenigvuldiger genoemd naar de naam van de wiskundige die de Lagrangiaanse mechanica introduceerde in 1788.
Joseph-Louis Lagrange (Wikipedia)
in dit stadium weten we de waarde vanwat iets kan zijn als 2.5, -1, of anders. Het betekent alleen dat de twee gradiënten parallel moeten zijn.
we kunnen de vergelijking als volgt herschikken:
grad { f(x, y) - λ g(x, y) } = 0
de nul betekent hier de vector met nullen: (0,0).
en we noemen de binnenkant van de accolades als de Lagrangian L.
L = f(x, y) - λ g(x, y)
dus zeggen we dat het volgende de vereiste voorwaarde is.
grad L = 0
de gradiënt van de Lagrangiaan geeft ons twee vergelijkingen.
maar we hebben drie onbekendenxy, enλ. Hoe kunnen we deze vergelijkingen oplossen?
eigenlijk hebben we nog een vergelijking die de g(x, y) = 0is.
dus we kunnen de drie vergelijkingen oplossen om de hoogste locatie (x, y) te vinden die voldoet aan de beperking.
het probleem wordt nu een rekenkundige oefening.
het antwoord is f(x, y) = 2 where x = 1 and y = 1.
Image by author using Grapher on macOS
u kunt de waarden verifiëren met de vergelijkingen.
ook λ = -4/5 wat betekent dat deze gradiënten in de tegenovergestelde richtingen zijn zoals verwacht.
al met al is de Lagrange multiplier nuttig om constraintoptimalisatieproblemen op te lossen.
we vinden het punt (x, y) waar de gradiënt van de functie die we optimaliseren en de gradiënt van de constraint functie parallel is met behulp van de multiplier λ.
samengevat hebben we de onderstaande stappen gevolgd:
Identificeer de te optimaliseren functie (maximaliseren of minimaliseren): f(x, y)
Identificeer de functie voor de beperking: g(x, y) = 0
Definieer de Lagrangian L = f(x, y) - λ g(x, y)
Solve grad L = 0 voldoen aan de beperking
Het is zo mechanisch als hierboven en je weet nu waarom het werkt.
maar er zijn nog een paar dingen te vermelden.
wanneer het niet werkt
heb ik een paar veronderstellingen gemaakt terwijl ik de Lagrange multiplier uitleg.
allereerst nam ik aan dat alle functies gradiënten hebben (de eerste afgeleiden), wat betekent dat de functies f(x, y) en g(x, y) continu en glad zijn.
ten tweede neem ik ook aan dat f(x, y) de tweede derivaten heeft, zodat we kunnen controleren of de oplossing (x, y) eigenlijk het maximum is of niet.
deze twee veronderstellingen zijn waar in dit voorbeeld, maar in echte problemen moet je dat controleren om de Lagrange multiplier te kunnen gebruiken om je constraint optimalisatie probleem op te lossen.
ten derde heb ik de vraag vereenvoudigd zodat we slechts één maximum hoeven te behandelen.
met andere woorden, de vorm van Berg is zo gedefinieerd dat er maar één oplossing is voor het beperkte optimalisatieprobleem.
in echte problemen kan de berg ingewikkelder vormen hebben met meerdere pieken en dalen.
https://unsplash.com/@simonfitall
in dat geval moeten we het globale optimalisatieprobleem aanpakken (d.w.z. meerdere lokale maxima).
in plaats daarvan behandelt het voorbeeld in dit artikel slechts één lokaal maximum, dat ook het globale maximum is.
Ik hoop dat uw begrip van de Lagrange multiplier nu optimaal is.
