Lagrange Multiplier Demystified

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

Is it just a clever technique?

koska se on erittäin helppokäyttöinen, opimme sen kuin peruslaskun harjoittelemalla sitä, kunnes voimme tehdä sen ulkoa.

mutta oletko koskaan miettinyt, miksi se toimii? Toimiiko se aina? Jos ei, niin miksi ei?

Jos haluat tietää vastaukset näihin kysymyksiin, olet oikeassa paikassa.

i ’ ll demystify it for you.

esimerkki rajoitetusta optimointiongelmasta

Jos et tiedä, mitä rajoitetut optimoinnit ovat, Olen kirjoittanut artikkelin, joka selittää sen. Muussa tapauksessa jatka lukemista.

Oletetaan, että meillä on vuori, joka näyttää alapuolelta:

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:

tämä tarkoittaa, että purkauksen reuna ilmoitetaan seuraavasti:

joten reuna näyttää tältä.

oletetaan, että haluamme tietää purkauksen korkeimman paikan tällä vuorella.

tämä tarkoittaa, että korkeimman sijainnin on oltava purkauksen reunalinjalla, jonka voimme ilmaista seuraavasti:

mikä tahansa paikka(x, y)joka täyttääg(x, y)=0on purkauksen reunalla.

rajoittunut optimointiongelma on siis löytää maksimi f(x, y) täyttävä g(x, y) = 0.

intuitio rajoittuneen optimointiongelman ratkaisemisesta

intuitiivisesti tiedämme, että purkauksen suurin korkeus on suunnilleen siinä, missä sininen nuoli osoittaa.

etsimme korkeinta korkeuskäyrää, joka koskettaa purkauksen reunaa.

määritellään ääriviivayhtälö:

f(x, y) = H

H on ääriviivojen korkeutta ilmaiseva vakioarvo.

tietylle H-arvolle on olemassa joukko (x, y) arvoja, jotka täyttävät f(x, y) = H.

gradientti f(x, y) osoittaa korkeuden noususuunnan, joka on kohtisuorassa korkeusviivaan nähden.

The gradient is a vector of partial derivatives.

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

purkauksen reunaa sivuavan korkeimman korkeuskäyrän gradientin tulee ollaf(x, y)rinnakkain gradienttig(x, y).

Jos korkeuskäyrän gradientti ei ole samansuuntainen purkausreunan gradientin kanssa, on olemassa jokin purkausalue, joka on sijaitsee korkeammalla kuin korkeuskäyrä.

so, we need to find such point(x, y)missä f(x, y)gradientti on samansuuntainen g(x, y).

Lagrangen kerroin ja Lagrangen

laitetaan tavoitteemme matemaattiseen kaavaan.

f(x, y) ja g(x, y) gradientin tulisi olla samansuuntainen, mutta niillä voi olla eri koko ja suunta.

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

tätä λ kutsutaan Lagrangen kertojaksi sen matemaatikon nimen mukaan, joka esitteli Lagrangen mekaniikan vuonna 1788.

tässä vaiheessa ei tiedetäλ, joka voisi olla vaikka 2,5, -1 tai muuten. Se vain merkitsee sitä, että kahden kaltevuuden on oltava rinnakkain.

yhtälö voidaan järjestää uudelleen seuraavasti:

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

nolla tarkoittaa tässä vektoria nollilla: (0,0).

ja kiharasulkujen sisäpuolta kutsutaan Lagrangilaiseksi L.

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

näin ollen vaadittu ehto on seuraava.

grad L = 0

Lagrangen gradientti antaa meille kaksi yhtälöä.

mutta meillä on kolme tuntematonta xy, ja λ. Miten voimme ratkaista nämä yhtälöt?

oikeastaan meillä on vielä yksi yhtälö, joka on g(x, y) = 0.

voidaan siis ratkaista kolme yhtälöä, jotta löydetään korkein paikka (x, y), joka täyttää rajoituksen.

ongelma muuttuu nyt aritmeettiseksi harjoitukseksi.

vastaus on f(x, y) = 2 where x = 1 and y = 1.

arvot voi todentaa yhtälöillä.

myös λ = -4/5, mikä tarkoittaa, että nämä gradientit ovat odotetusti vastakkaisissa suunnissa.

kaiken kaikkiaan Lagrangen kerroin on hyödyllinen rajoitteiden optimointiongelmien ratkaisemisessa.

löydämme pisteen (x, y), jossa optimoimamme funktion gradientti ja rajoitefunktion gradientti ovat rinnakkain käyttämällä kerrointa λ.

yhteenvetona noudatimme seuraavia ohjeita:

• tunnista funktio optimoida (maksimoida tai minimoida): f(x, y)
• tunnista funktio rajoitukselle: g(x, y) = 0
• Määrittele lagrangilainen L = f(x, y) - λ g(x, y)
• ratkaise grad L = 0 täyttää rajoituksen

se on yhtä mekaaninen kuin yllä oleva Ja nyt tiedät, miksi se toimii.

mutta on vielä muutama mainittava asia.

kun se ei toimi

tein muutamia oletuksia selittäessäni Lagrangen kerrointa.

ensinnäkin oletin, että kaikilla funktioilla on gradientit (ensimmäiset derivaatat), eli funktiot f(x, y) ja g(x, y) ovat jatkuvia ja sileitä.

toiseksi oletan myös, että f(x, y) on toinen derivaatta, jotta voimme tarkistaa, onko ratkaisu (x, y) todella maksimi vai ei.

nämä kaksi oletusta ovat tosia tässä esimerkissä, mutta todellisissa ongelmissa kannattaa tarkistaa, että voi käyttää Lagrangen kerrointa rajoitteen optimointiongelman ratkaisemiseen.

kolmanneksi yksinkertaistin kysymystä niin, että meidän tarvitsee käsitellä vain yksi maksimi.

toisin sanoen vuoriston muoto määritellään siten, että rajoittuneeseen optimointiongelmaan on vain yksi ratkaisu.

tosielämän ongelmissa vuorella saattoi olla monimutkaisempia muotoja, joissa oli useita huippuja ja laaksoja.

tällaisessa tapauksessa olisi käsiteltävä globaalia optimointiongelmaa (eli useita paikallisia maksimeja).

sen sijaan tämän artikkelin esimerkissä käsitellään vain yhtä paikallista maksimia, joka on myös maailmanlaajuinen maksimi.

toivon, että ymmärryksenne Lagrangen kertoimesta on nyt optimaalinen.