Hjdcti

Lagrangen menetelmä on ranskalaisen matemaatikon Joseph-Louis Lagrangen mukaan nimetty menetelmä yhtälörajoitetun optimointitehtävän ratkaisemiseksi.

Määritelmä |

Olkoon fdisplaystyle f, minimointitehtävän kohdefunktio ja gdisplaystyle g, rajoite-ehtofunktio. Tarkastellaan näiden määrittämää rajoiteoptimointititehtävää

minf(x0,x1,…)displaystyle min f(x_0,x_1,dots )

ehdollagi(x0,x1,…)=0, i∈1,…,Ndisplaystyle textehdollaquad g_i(x_0,x_1,dots )=0,~iin 1,dots ,N

Tehtävä voidaan kirjoittaa muodossa, jota kutsutaan Lagrangen funktioksi L,displaystyle L,

L(x0,x1,…,λ)=f(x0,x1,…)+∑i=0Nλigi(x0,x1,…)displaystyle L(x_0,x_1,dots ,lambda )=f(x_0,x_1,dots )+sum _i=0^Nlambda _ig_i(x_0,x_1,dots )

Kertoimia λi∈Rdisplaystyle lambda _iin mathbb R kutsutaan Lagrangen kertoimiksi. Esitetyn optimointitehtävän käypä eli rajoite-ehdot täyttävä ratkaisu löydetään Lagrangen funktion L,displaystyle L, ääriarvopisteessä (x0∗,x1∗,…,xn∗)displaystyle (x_0^*,x_1^*,dots ,x_n^*), jossa siis ∇L(x0∗,x1∗,…,xn∗)=0displaystyle nabla L(x_0^*,x_1^*,dots ,x_n^*)=0. Voidaan tulkita, että kertoimet ohjaavat ratkaisun rajoite-ehtojen määräämään käypään joukkoon.

Esimerkki |

Minimointitehtävä minf(x,y),g(x,y)=0displaystyle min f(x,y),quad g(x,y)=0 ratkaistaan seuraavasti:

• kirjoita tehtävä funktiona L(x,y,λ)displaystyle L(x,y,lambda )
  


• etsi osittaisderivaatat muuttujien x,ydisplaystyle x,y ja λdisplaystyle lambda suhteen


• ratkaise derivaattojen nollakohdat yhtälöryhmästä

Langrangen funktio esimerkille

L(x,y)=f(x,y)−λg(x,y)displaystyle L(x,y)=f(x,y)-lambda g(x,y)

Etsitään osittaisderivaatat ja niiden muodostama yhtälöryhmä

∇L(x,y,λ)={∂∂xL=∂∂xf(x,y)+λ∂∂xg(x,y)∂∂yL=∂∂yf(x,y)+λ∂∂yg(x,y)∂∂λL=g(x,y)displaystyle nabla L(x,y,lambda )=begincasesfrac partial partial xL=frac partial partial xf(x,y)+lambda frac partial partial xg(x,y)\frac partial partial yL=frac partial partial yf(x,y)+lambda frac partial partial yg(x,y)\frac partial partial lambda L=g(x,y)endcases

Ratkaistaan saadusta yhtälöryhmästä ääriarvopisteet (x∗displaystyle x^*, y∗displaystyle y^*, λ∗displaystyle lambda ^*) algebran menetelmin (ratkaisemalla derivaattojen nollakohdat yhtälöryhmästä).

Menetelmä |

Olkoon fdisplaystyle f, minimointitehtävän kohdefunktio ja gdisplaystyle g, rajoite-ehtofunktio. Kutsutaan ehdon g(x,y)=0displaystyle g(x,y)=0, määräämien pisteiden joukkoa käyräksi Cdisplaystyle C,. Olkoot funktiot derivoituvia kaikkien muuttujiensa suhteen käyrän Cdisplaystyle C, pisteissä. Oletetaan myös, että kohdefunktio fdisplaystyle f, on derivoituva tehtävän ratkaisupisteen (x0,y0)displaystyle (x_0,y_0), ympäristössä. Kun lisäksi oletetaan, että piste (x0,y0)displaystyle (x_0,y_0), ei ole käyrän Cdisplaystyle C, päätepiste, ja gradientti ∇g(x0,y0)≠0displaystyle nabla g(x_0,y_0)neq 0,, on olemassa sellainen luku λ0displaystyle lambda _0, niin, että piste (x0,y0,λ0)displaystyle (x_0,y_0,lambda _0), on ns. Lagrangen funktion Ldisplaystyle L,

L(x0,x1,…,λ)=f(x0,x1,…)+λg(x0,x1,…)displaystyle L(x_0,x_1,dots ,lambda )=f(x_0,x_1,dots )+lambda g(x_0,x_1,dots )

kriittinen piste. Toisin sanoen funktion fdisplaystyle f, käyrällä g(x,y)=0displaystyle g(x,y)=0, sijaitsevat ääriarvot voidaan löytää etsimällä Lagrangen funktion ääriarvot. Ääriarvot löydetään ratkaisemalla funktion Ldisplaystyle L osittaisderivaatojen nollakohta

0=∂L∂x=f1(x,y)+λg(x,y)displaystyle 0=frac partial Lpartial x=f_1(x,y)+lambda g(x,y)

0=∂L∂y=f1(x,y)+λg(x,y)displaystyle 0=frac partial Lpartial y=f_1(x,y)+lambda g(x,y)

0=∂L∂λ=g(x,y)displaystyle 0=frac partial Lpartial lambda =g(x,y)

eli

∇L(x0,x1,…,xn,λ)=0displaystyle nabla L(x_0,x_1,dots ,x_n,lambda )=mathbf 0

Geometrinen tulkinta |

Kohdefunktion a=∇f(x)displaystyle mathbf a =nabla f(x) ja rajoitusehdon b=∇g(x)displaystyle mathbf b =nabla g(x) gradientit Lagrangen funktion ratkaisupisteessä.

Lagrangen kerroin λdisplaystyle lambda , voidaan nähdä skaalaustekijänä, jolla rajoitusehdon gradienttivektoria ∇g(x)displaystyle nabla g(x), tulee kertoa, että siitä tulee
yhtä pitkä kuin kohdefunktion gradienttivektorista ∇f(x)displaystyle nabla f(x), optimointitehtävän ratkaisupisteessä. Tulkinta yleistyy useamman rajoitusehdon tapaukseen, jolloin
aktiivisia rajoitusehtoja vastaavat kertoimet λidisplaystyle lambda _i, valitaan niin, että niiden lineaarikombinaatio vastaavien gradienttien kanssa kumoaa kohdefunktion
gradientin.

Herkkyystulkinta |

Herkkyystulkinnassa tarkastellaan, miten kohdefunktion arvo muuttuu, kun yhtälörajoitetta muutetaan. Tarkastellaan minf(x), h(x)=cdisplaystyle min f(x),~h(x)=c muotoista tehtävää, missä
cdisplaystyle c. Lagrangen kerroin ilmaisee kunka paljon kohdefunktion arvo muuttuu yhtälörajoituksen muuttuessa eli

∇cf(x)=−λdisplaystyle nabla _cf(x)=-lambda ,

missä ∇cdisplaystyle nabla _c tarkoittaa gradienttia rajoitusehdon muutoksen suhteen.

Esimerkki: pisteen etäisyys suorasta |

Pisteen pdisplaystyle p etäisyys suoralta.

Esitetään tehtävä matemaattisessa muodossa ja ratkaistaan se Lagrangen menetelmällä. Olkoon piste p=(x0,y0)displaystyle p=(x_0,y_0) ja suora ax+by+c=0displaystyle ax+by+c=0, missä a,b,c∈Rdisplaystyle a,b,cin mathbb R ovat mielivaltaisia vakioita.

Minimoidaan etäisyyden funktio

mind(x,y)=(x−x0)2+(y−y0)2displaystyle min d(x,y)=(x-x_0)^2+(y-y_0)^2,

ehdolla

ax+by+c=0displaystyle ax+by+c=0

Suoran yhtälö on siis optimointitehtävän ehto.

Muodostetaan etäisyysfunktiosta ja ehdosta Lagrangen funktio

L(x,y,λ)=d(x,y)+λg(x,y)=(x−x0)2+(y−y0)2+λ(ax+by+c)displaystyle beginalignedL(x,y,lambda )&=d(x,y)+lambda g(x,y)\&=(x-x_0)^2+(y-y_0)^2+lambda (ax+by+c)endaligned

Ratkaistaan funktion Ldisplaystyle L ääriarvot muuttujien xdisplaystyle x, ydisplaystyle y ja λdisplaystyle lambda suhteen etsimällä osittaisderivaattojen nollakohdat:

{∂∂xL=2(x−x0)+λa=0∂∂yL=2(y−y0)+λb=0∂∂λL=ax+by+c=0displaystyle begincasesfrac partial partial xL=2(x-x_0)+lambda a&=0\frac partial partial yL=2(y-y_0)+lambda b&=0\frac partial partial lambda L=ax+by+c&=0\endcases

Katso myös |

• Matemaattinen optimointi

Lähteet |

• Robert A. Adams (1999), Calculus: A Complete Course 5. painos, Addison Wesley Longman, ISBN 0-201-79131-5.