Lagrange Multiplier Demystified

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

Is it just a clever technique?Siden det er veldig enkelt å bruke, lærer vi det som en grunnleggende aritmetikk ved å praktisere det til vi kan gjøre det utenat.

men har du noen gang lurt på hvorfor det fungerer? Fungerer det alltid? Hvis ikke, hvorfor ikke?

hvis du vil vite svarene på disse spørsmålene, er du på rett sted.

jeg vil avmystifisere det for deg.

et eksempel begrenset optimaliseringsproblem

hvis du ikke er kjent med hvilke begrensede optimaliseringer som er, har jeg skrevet en artikkel som forklarer det. Ellers kan du lese videre.

Anta at vi har et fjell som ser ut som 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 betyr at kanten av utbruddet er gitt som følger:

så kanten ser slik ut.

Bilde av forfatter ved Hjelp Av Grapher på macOS

anta at vi vil vite den høyeste posisjonen til utbruddet på dette fjellet.

dette betyr at den høyeste posisjonen må være på kanten av utbruddet som vi kan uttrykke som følger:

ethvert sted(x, y)som tilfredsstillerg(x, y)=0er på kanten av utbruddet.

derfor er det begrensede optimaliseringsproblemet å finne maksimum f(x, y) tilfredsstillende g(x, y) = 0.

Intuisjon om hvordan du løser det begrensede optimaliseringsproblemet

Intuitivt vet Vi at maksimal høyde på utbruddet er rundt hvor den blå pilen indikerer.

Bilde av forfatter ved Hjelp Av Grapher på macOS

vi leter etter den høyeste konturlinjen som berører kanten av utbruddet.

la oss definere konturlinjekvasjonen:

f(x, y) = H

H er en konstant verdi som angir konturens høyde.

For en gitt verdi Av H er det et sett med (x, y) verdier som tilfredsstiller f(x, y) = H.

gradienten til f(x, y) indikerer retningen der høyden øker som er vinkelrett 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øyeste konturlinjen som berører kanten av utbruddet, må ha gradienten tilf(x, y)parallelt med utbruddets gradient avg(x, y).

hvis gradienten av konturlinjen ikke er parallell med gradienten av utbruddskanten, vil det være noe utbruddsområde som ligger i området.høyere enn konturlinjen.

Bilde av forfatter

så vi må finne et slikt punkt (x, y) hvor gradienten tilf(x, y) er parallell med gradienten tilg(x, y).

Lagrange multiplikatoren og Lagrange

La oss sette vårt mål i en matematisk formel.

gradienten til f(x, y) og gradienten til g(x, y) skal være parallell, men de kan ha forskjellig størrelse og retning.

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

dette λ Kalles Lagrange multiplikator etter navnet på matematikeren som introduserte Lagrangian mekanikk i 1788.

Joseph-Louis Lagrange (Wikipedia)

På dette stadiet kjenner vi ikke verdien avλsom kan være noe som 2.5, -1 eller annet. Det betyr bare at de to gradientene må være parallelle.

vi kan omorganisere ligningen som følger:

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

null her betyr vektoren med nuller: (0,0).

og vi kaller innsiden av de krøllete parentesene Som Lagrangian L.

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

Så, vi sier at følgende er den nødvendige betingelsen.

grad L = 0

Lagrangianens gradient gir oss to ligninger.

Men vi har tre ukjentexyogλ. Hvordan kan vi løse disse ligningene?

Faktisk har Vi en mer ligning som er g(x, y) = 0.

Så, vi kan løse de tre ligningene for å finne den høyeste plasseringen(x, y) som tilfredsstiller begrensningen.

problemet blir nå en aritmetisk øvelse.

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

du kan verifisere verdiene med ligningene.

Også λ = -4/5 som betyr at disse gradientene er i motsatt retning som forventet.Alt I alt Er Lagrange-multiplikatoren nyttig for å løse begrensningsoptimaliseringsproblemer.

Vi finner punktet (x, y) hvor gradienten av funksjonen som vi optimaliserer og gradienten av begrensningsfunksjonen er parallelt med multiplikatoren λ.

i sammendraget fulgte vi trinnene nedenfor:

• Identifiser funksjonen for å optimalisere (maksimere eller minimere): f(x, y)
• Identifiser funksjonen for begrensningen: g(x, y) = 0
• Definer LagrangianL = f(x, y) - λ g(x, y)
• Løsgrad L = 0 tilfredsstiller begrensningen

det er så mekanisk som det ovenfor, og du vet nå hvorfor det fungerer.

men det er noen flere ting å nevne.

Når det ikke virker

gjorde jeg noen forutsetninger mens jeg forklarte Lagrange-multiplikatoren.

Først av alt antok jeg at alle funksjoner har gradienter (de første derivatene), som betyr at funksjonene f(x, y)ogg(x, y) er kontinuerlige og glatte.For det Andre antar jeg også at f(x, y) har de andre derivatene slik at vi kan sjekke om løsningen(x, y) er faktisk maksimum eller ikke.

Disse to forutsetningene er sanne i dette eksemplet, men i virkelige problemer bør du sjekke det for å kunne bruke Lagrange-multiplikatoren for å løse begrensningsoptimaliseringsproblemet.

Tredje forenklet jeg spørsmålet slik at vi bare trenger å håndtere ett maksimum.med andre ord er formen på fjellet definert slik at det bare er en løsning på det begrensede optimaliseringsproblemet.

i virkelige problemer kan fjellet ha mer kompliserte former med flere topper og daler.

i så fall må vi håndtere det globale optimaliseringsproblemet (dvs.flere lokale maksima).

i stedet omhandler eksemplet i denne artikkelen bare ett lokalt maksimum som også er det globale maksimumet.

jeg håper at din forståelse av Lagrange multiplikatoren er optimal nå.