Lagrangen kertoimet

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

Olkoon ${\displaystyle f\,}$ minimointitehtävän kohdefunktio ja ${\displaystyle g\,}$ rajoite-ehtofunktio. Tarkastellaan näiden määrittämää rajoiteoptimointititehtävää

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

${\displaystyle {\text{ehdolla}}\quad g_{i}(x_{0},x_{1},\dots )=0,~i\in \{1,\dots ,N\}}$

Tehtävä voidaan kirjoittaa muodossa, jota kutsutaan Lagrangen funktioksi ${\displaystyle L,}$

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle L,}$ ääriarvopisteessä ${\displaystyle (x_{0}^{*},x_{1}^{*},\dots ,x_{n}^{*})}$, jossa siis ${\displaystyle \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.

Minimointitehtävä ${\displaystyle \min f(x,y),\quad g(x,y)=0}$ ratkaistaan seuraavasti:

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

Langrangen funktio esimerkille

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

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

${\displaystyle \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 (${\displaystyle x^{*}}$, ${\displaystyle y^{*}}$, ${\displaystyle \lambda ^{*}}$) algebran menetelmin (ratkaisemalla derivaattojen nollakohdat yhtälöryhmästä).

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

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

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

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

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

eli

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

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

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

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

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

Esitetään tehtävä matemaattisessa muodossa ja ratkaistaan se Lagrangen menetelmällä. Olkoon piste ${\displaystyle p=(x_{0},y_{0})}$ ja suora ${\displaystyle ax+by+c=0}$, missä ${\displaystyle a,b,c\in \mathbb {R} }$ ovat mielivaltaisia vakioita.

Minimoidaan etäisyyden funktio

${\displaystyle \min d(x,y)=(x-x_{0})^{2}+(y-y_{0})^{2}\,}$

ehdolla

${\displaystyle ax+by+c=0}$

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

Muodostetaan etäisyysfunktiosta ja ehdosta Lagrangen funktio

${\displaystyle {\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 ${\displaystyle L}$ ääriarvot muuttujien ${\displaystyle x}$, ${\displaystyle y}$ ja ${\displaystyle \lambda }$ suhteen etsimällä osittaisderivaattojen nollakohdat:

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

• Matemaattinen optimointi

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