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} \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

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

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{\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, .