Lagrangen kertoimet

Wikipedia
Loikkaa: valikkoon, hakuun

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

Määritelmä[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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 nollakodat 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.

Menetelmä[muokkaa | muokkaa wikitekstiä]

Olkoon f\, minimointitehtävän kohdefuntio 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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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{align}L(x,y,\lambda) & = d(x, y) + \lambda g(x, y) \\
 & = (x - x_0)^2 + (y - y_0)^2 + \lambda(ax + by + c)
\end{align}

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

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

Katso myös[muokkaa | muokkaa wikitekstiä]

Lähteet[muokkaa | muokkaa wikitekstiä]

  • Robert A. Adams (1999), Calculus - A Complete Course 5. painos, Addison Wesley Longman, ISBN 0-201-79131-5.
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.