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 kohdefuntio ja $g\,$ rajoite-ehtofunktio. Tarkastellaan näiden määrittämää rajoiteoptimointititehtävää

$\min f(x_{0},x_{1},\dots )$

$s.t.\quad 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 \mathbb {R}$ 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 $\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),\quad 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ä

$\nabla L(x,y,\lambda )={\begin{cases}{\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{cases}}$

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 $\nabla g(x_{0},y_{0})\neq 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

$\nabla L(x_{0},x_{1},\dots ,x_{n},\lambda )=\mathbf {0}$

Geometrinen tulkinta

Kohdefunktion $\mathbf {a} =\nabla f(x)$ ja rajoitusehdon $\mathbf {b} =\nabla g(x)$ gradientit Lagrangen funktion ratkaisupisteessä.

Lagrangen kerroin $\lambda \,$ voidaan nähdä skaalaustekijänä, jolla rajoitusehdon gradienttivektoria $\nabla g(x)\,$ tulee kertoa, että siitä tulee yhtä pitkä kuin kohdefunktion gradienttivektorista $\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

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

missä $\nabla _{c}$ tarkoittaa gradienttia rajoitusehdon muutoksen suhteen.

Esimerkki: pisteen etäisyys suorasta

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 \mathbb {R}$ 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{aligned}L(x,y,\lambda )&=d(x,y)+\lambda g(x,y)\\&=(x-x_{0})^{2}+(y-y_{0})^{2}+\lambda (ax+by+c)\end{aligned}}$

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

${\begin{cases}{\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{cases}}$

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.