Lagrange Multiplier Demystified

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

Is it just a clever technique?

eftersom det är väldigt enkelt att använda lär vi oss det som en grundläggande aritmetik genom att öva det tills vi kan göra det av hjärtat.

men har du någonsin undrat varför det fungerar? Fungerar det alltid? Om inte, varför inte?

Om du vill veta svaren på dessa frågor Är du på rätt plats.

jag avmystifierar det åt dig.

ett exempel begränsad optimering problem

om du inte är bekant med vad begränsade optimeringar är, jag har skrivit en artikel som förklarar det. Annars, läs vidare.

Antag att vi har ett berg som ser ut som nedan:

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:

detta betyder att utbrottets kant ges enligt följande:

så ser kanten ut så här.

bild av författare som använder Grapher på macOS

Antag att vi vill veta den högsta positionen för utbrottet på detta berg.

detta betyder att den högsta positionen måste vara på utbrottets kantlinje som vi kan uttrycka enligt följande:

vilken plats som helst(x, y)som uppfyllerg(x, y)=0är på kanten av utbrottet.

därför är det begränsade optimeringsproblemet att hitta det maximala f(x, y)tillfredsställandeg(x, y) = 0.

Intuition om hur man löser det begränsade optimeringsproblemet

intuitivt vet vi att utbrottets maximala höjd är runt där den blå pilen indikerar.

bild av författare som använder Grapher på macOS

vi letar efter den högsta konturlinjen som berör kanten av utbrottet.

låt oss definiera konturlinjekvationen:

f(x, y) = H

H är ett konstant värde som indikerar konturens höjd.

för ett givet värde på H finns en uppsättning (x, y) värden som uppfyller f(x, y) = H.

gradienten för f(x, y) indikerar riktningen där höjden ökar som är vinkelrätt mot 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ögsta konturlinjen som berör utbrottets kant måste ha gradienten f(x, y) parallellt med utbrottets kant gradient av g(x, y).

ligger högre än konturlinjen.

Så vi måste hitta en sådan punkt (x, y) där gradienten för f(x, y) är parallell med gradienten för g(x, y).

Lagrange multiplikatorn och Lagrangian

Låt oss sätta vårt mål i en matematisk formel.

gradienten för f(x, y) och gradienten för g(x, y) bör vara parallella men de kan ha olika storlek och riktning.

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

detta λ kallas Lagrange multiplikator efter namnet på matematikern som introducerade Lagrangian mekaniken 1788.

i detta skede vet vi inte värdet av λ vilket kan vara något som 2.5, -1, annars. Det betyder bara att de två gradienterna måste vara parallella.

Vi kan ordna om ekvationen enligt följande:

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

noll här betyder vektorn med nollor: (0,0).

och vi kallar insidan av de lockiga parenteserna som Lagrangian L.

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

Så vi säger att följande är det nödvändiga villkoret.

grad L = 0

Lagrangians gradient ger oss två ekvationer.

men vi har tre okända xy och λ. Hur kan vi lösa dessa ekvationer?

egentligen har vi en mer ekvation som är g(x, y) = 0.

Så vi kan lösa de tre ekvationerna för att hitta den högsta platsen (x, y) som uppfyller begränsningen.

problemet blir nu en aritmetisk övning.

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

bild av författare som använder Grapher på macOS

Du kan verifiera värdena med ekvationerna.

också λ = -4/5 vilket innebär att dessa gradienter är i motsatta riktningar som förväntat.

Sammantaget är Lagrange multiplikatorn användbar för att lösa problem med begränsningsoptimering.

vi hittar punkten (x, y) där gradienten för funktionen som vi optimerar och gradienten för begränsningsfunktionen är parallell med multiplikatorn λ.

Sammanfattningsvis följde vi stegen nedan:

• identifiera funktionen för att optimera (maximera eller minimera): f(x, y)
• identifiera funktionen för begränsningen: g(x, y) = 0
• definiera LagrangianL = f(x, y) - λ g(x, y)
• Lösgrad L = 0 uppfyller begränsningen

det är lika mekaniskt som ovan och du vet nu varför det fungerar.

men det finns några fler saker att nämna.

när det inte fungerar

gjorde jag några antaganden medan jag förklarade Lagrange multiplikatorn.

först och främst antog jag att alla funktioner har gradienter (de första derivaten), vilket innebär att funktionerna f(x, y) och g(x, y) är kontinuerliga och smidiga.

För det andra antar jag också att f(x, y) har de andra derivaten så att vi kan kontrollera om lösningen (x, y) är faktiskt det maximala eller inte.

dessa två antaganden är sanna i det här exemplet men i verkliga problem bör du kontrollera det för att kunna använda Lagrange multiplikatorn för att lösa ditt begränsningsoptimeringsproblem.

För det tredje förenklade jag frågan så att vi bara behöver hantera ett maximum.

med andra ord definieras formen på berget så att det bara finns en lösning på det begränsade optimeringsproblemet.

i verkliga problem kan berget ha mer komplicerade former med flera toppar och dalar.

https://unsplash.com/@simonfitall

i så fall skulle vi behöva hantera det globala optimeringsproblemet (dvs flera lokala maxima).

istället handlar exemplet i den här artikeln bara om ett lokalt maximum som också är det globala maximumet.

Jag hoppas att din förståelse av Lagrange multiplikatorn är optimal nu.