Lagrange Multiplier Demystified

Have you ever wondered why we use the Lagrange multiplier to solve constrained optimization problems?

Is it just a clever technique?

da det er meget let at bruge, lærer vi det som en grundlæggende aritmetik ved at øve det, indtil vi kan gøre det udenad.

men har du nogensinde spekuleret på, hvorfor det virker? Virker det altid? Hvis ikke, hvorfor ikke?

Hvis du vil vide svarene på disse spørgsmål, er du på det rigtige sted.

Jeg vil afmystificere det for dig.

et eksempel begrænset optimeringsproblem

Hvis du ikke er bekendt med, hvad begrænsede optimeringer er, har jeg skrevet en artikel, der forklarer det. Ellers, læs venligst videre.

Antag, at vi har et bjerg, der ligner nedenfor:

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:

dette betyder udbrudets kant er givet som følger:

så kanten ser sådan ud.

Antag, at vi vil vide den højeste position af udbruddet på dette bjerg.

dette betyder, at den højeste position skal være på kanten af udbruddet, som vi kan udtrykke som følger:

enhver placering (x, y) der opfylder g(x, y)=0 er på kanten af udbruddet.

derfor er det begrænsede optimeringsproblem at finde det maksimalef(x, y)tilfredsstillendeg(x, y) = 0.

Intuition om, hvordan man løser det begrænsede optimeringsproblem

intuitivt ved vi, at udbrudets maksimale højde er omkring, hvor den blå pil angiver.

vi leder efter den højeste konturlinie, der berører udbrudets kant.

lad os definere konturlinjens ligning:

f(x, y) = H

H er en konstant værdi, der angiver konturens højde.

for en given værdi af H er der et sæt (x, y) værdier, der opfylder f(x, y) = H.

gradienten aff(x, y) angiver retningen, hvor højden stiger, som er vinkelret på konturlinjen.

The gradient is a vector of partial derivatives.

Similarly, the gradient of g(x, y) is perpendicular to the edge of the eruption area.

den højeste konturlinje, der berører udbrudets kant, skal have gradienten af f(x, y) parallelt med udbrudets kant, skal den højeste konturlinje, der berører udbrudets kant, have gradienten f(x, y)gradient af g(x, y).

hvis konturlinjens gradient ikke er parallelt med gradienten af udbrudskanten, vil der være noget udbrudsområde, der er placeret i et område, der er placeret i det område, der er placeret i højere end konturlinjen.

så vi skal finde et sådant punkt (x, y) hvor gradienten af f(x, y) er parallelt med gradienten af g(x, y).

Lagrange multiplikatoren og Lagrangian

lad os sætte vores mål i en matematisk formel.

gradienten aff(x, y) og gradienten afg(x, y) skal være parallelt, men de kan have forskellig størrelse og retning.

grad f(x, y) = λ grad g(x, y)

detteλ kaldes Lagrange multiplikator efter navnet på matematikeren, der introducerede den Lagrangiske mekanik i 1788.

på dette stadium kender vi ikke værdien af λ som kunne være noget som 2.5, -1, ellers. Det betyder bare, at de to gradienter skal være parallelle.

Vi kan omarrangere ligningen som følger:

grad { f(x, y) - λ g(x, y) } = 0

nul her betyder vektoren med nuller:(0,0).

og vi kalder indersiden af de krøllede parenteser som LagrangianL.

L = f(x, y) - λ g(x, y)

så vi siger, at følgende er den krævede betingelse.

grad L = 0

lagrangianens gradient giver os to ligninger.

men vi har tre ukendte xy, og λ. Hvordan kan vi løse disse ligninger?

faktisk har vi endnu en ligning, der erg(x, y) = 0.

så vi kan løse de tre ligninger for at finde den højeste placering(x, y) der opfylder begrænsningen.

problemet bliver nu en aritmetisk øvelse.

svaret erf(x, y) = 2 where x = 1 and y = 1.

Du kan kontrollere værdierne med ligningerne.

også λ = -4/5 hvilket betyder, at disse gradienter er i modsatte retninger som forventet.

alt i alt er Lagrange-multiplikatoren nyttig til at løse problemer med begrænsningsoptimering.

Vi finder punktet(x, y) hvor gradienten af den funktion, vi optimerer, og gradienten af begrænsningsfunktionen er parallelt ved hjælp af multiplikatorenλ.

sammenfattende fulgte vi nedenstående trin:

• Identificer funktionen for at optimere (maksimere eller minimere): f(x, y)
• Identificer funktionen for begrænsningen: g(x, y) = 0
• Definer Lagrangian L = f(x, y) - λ g(x, y)
• Løs grad L = 0 opfylder begrænsningen

det er så mekanisk som ovenstående, og du ved nu, hvorfor det virker.

men der er et par flere ting at nævne.

når det ikke virker

jeg lavede et par antagelser, mens jeg forklarede Lagrange multiplikatoren.

først og fremmest antog jeg, at alle funktioner har gradienter (de første derivater), hvilket betyder funktionerne f(x, y) og g(x, y) er kontinuerlige og glatte.

for det andet antager jeg også, atf(x, y) har de andre derivater, så vi kan kontrollere, om løsningen(x, y) er faktisk det maksimale eller ej.

disse to antagelser er sande i dette eksempel, men i reelle problemer skal du kontrollere det for at kunne bruge Lagrange-multiplikatoren til at løse dit begrænsningsoptimeringsproblem.

for det tredje forenklede jeg spørgsmålet, så vi kun skal håndtere et maksimum.

med andre ord er bjergets form defineret således, at der kun er en løsning på det begrænsede optimeringsproblem.

i virkelige problemer kunne bjerget have mere komplicerede former med flere toppe og dale.

i så fald skal vi håndtere det globale optimeringsproblem (dvs.flere lokale Maksima).

i stedet handler eksemplet i denne artikel kun om et lokalt maksimum, som også er det globale maksimum.

Jeg håber, at din forståelse af Lagrange multiplikatoren er optimal nu.