Lagrangen kertoimet

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

Määritelmä

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

$\min f(x_0,x_1,\dots )$

$\text{ehdolla}{g}_i(x_0,x_1,\dots )=0,i\in \{1,\dots ,N\}$

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

$L(x_0,x_1,\dots ,\lambda )=f(x_0,x_1,\dots )+\sum _{i=0}^N{\lambda }_i{g}_i(x_0,x_1,\dots )$

Kertoimia ${\lambda }_i\in ℝ$ kutsutaan Lagrangen kertoimiksi. Esitetyn optimointitehtävän käypä eli rajoite-ehdot täyttävä ratkaisu löydetään Lagrangen funktion $L,$ ääriarvopisteessä $(x_0^{*},x_1^{*},\dots ,x_n^{*})$, jossa siis $\mathrm{\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ä $\min f(x,y),g(x,y)=0$ ratkaistaan seuraavasti:

• kirjoita tehtävä funktiona $L(x,y,\lambda )$
• etsi osittaisderivaatat muuttujien $x,y$ ja $\lambda$ suhteen
• ratkaise derivaattojen nollakohdat yhtälöryhmästä

Langrangen funktio esimerkille

$L(x,y)=f(x,y)-\lambda g(x,y)$

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

$\mathrm{\nabla }L(x,y,\lambda )=\{\begin{array}{c}\frac{\partial }{\partial x}L=\frac{\partial }{\partial x}f(x,y)+\lambda \frac{\partial }{\partial x}g(x,y)\\ \frac{\partial }{\partial y}L=\frac{\partial }{\partial y}f(x,y)+\lambda \frac{\partial }{\partial y}g(x,y)\\ \frac{\partial }{\partial \lambda }L=g(x,y)\end{array}$

Ratkaistaan saadusta yhtälöryhmästä ääriarvopisteet ($x^{*}$, $y^{*}$, ${\lambda }^{*}$) algebran menetelmin (ratkaisemalla derivaattojen nollakohdat yhtälöryhmästä).

Menetelmä

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

$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 $f$ käyrällä $g(x,y)=0$ sijaitsevat ääriarvot voidaan löytää etsimällä Lagrangen funktion ääriarvot. Ääriarvot löydetään ratkaisemalla funktion $L$ osittaisderivaatojen nollakohta

$0=\frac{\partial L}{\partial x}=f_1(x,y)+\lambda g(x,y)$

$0=\frac{\partial L}{\partial y}=f_1(x,y)+\lambda g(x,y)$

$0=\frac{\partial L}{\partial \lambda }=g(x,y)$

eli

$\mathrm{\nabla }L(x_0,x_1,\dots ,x_n,\lambda )=\mathrm{𝟎}$

Geometrinen tulkinta

Tiedosto:Lagrangian orthogonality.png

Kohdefunktion $𝐚=\mathrm{\nabla }f(x)$ ja rajoitusehdon $𝐛=\mathrm{\nabla }g(x)$ gradientit Lagrangen funktion ratkaisupisteessä.

Lagrangen kerroin $\lambda$ voidaan nähdä skaalaustekijänä, jolla rajoitusehdon gradienttivektoria $\mathrm{\nabla }g(x)$ tulee kertoa, että siitä tulee yhtä pitkä kuin kohdefunktion gradienttivektorista $\mathrm{\nabla }f(x)$ optimointitehtävän ratkaisupisteessä. Tulkinta yleistyy useamman rajoitusehdon tapaukseen, jolloin aktiivisia rajoitusehtoja vastaavat kertoimet ${\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 $\min f(x),h(x)=c$ muotoista tehtävää, missä $c$. Lagrangen kerroin ilmaisee kunka paljon kohdefunktion arvo muuttuu yhtälörajoituksen muuttuessa eli

${\mathrm{\nabla }}_{c}f(x)=-\lambda$

missä ${\mathrm{\nabla }}_c$ tarkoittaa gradienttia rajoitusehdon muutoksen suhteen.

Esimerkki: pisteen etäisyys suorasta

Tiedosto:Pisteen etaisyys suoralta.png

Pisteen $p$ etäisyys suoralta.

Esitetään tehtävä matemaattisessa muodossa ja ratkaistaan se Lagrangen menetelmällä. Olkoon piste $p=(x_0,y_0)$ ja suora $ax+by+c=0$, missä $a,b,c\in ℝ$ ovat mielivaltaisia vakioita.

Minimoidaan etäisyyden funktio

$\min d(x,y)=(x-x_0{)}^2+(y-y_0{)}^2$

ehdolla

$ax+by+c=0$

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

Muodostetaan etäisyysfunktiosta ja ehdosta Lagrangen funktio

$\begin{array}{cc}L(x,y,\lambda )& =d(x,y)+\lambda g(x,y)\\ & =(x-x_0{)}^2+(y-y_0{)}^2+\lambda (ax+by+c)\end{array}$

Ratkaistaan funktion $L$ ääriarvot muuttujien $x$, $y$ ja $\lambda$ suhteen etsimällä osittaisderivaattojen nollakohdat:

$\{\begin{array}{cc}\frac{\partial }{\partial x}L=2(x-x_0)+\lambda a& =0\\ \frac{\partial }{\partial y}L=2(y-y_0)+\lambda b& =0\\ \frac{\partial }{\partial \lambda }L=ax+by+c& =0\end{array}$

Katso myös

• Matemaattinen optimointi

Lähteet

• Robert A. Adams (1999), Calculus: A Complete Course 5. painos, Addison Wesley Longman, Malline:ISBN.