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ää minimointitehtä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\,$ Lagrangen funktiossa kutsutaan Lagrangen kertoimiksi. Esitetyn rajoiteoptimointitehtävän käypä 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$. Tulkitaan, että kertoimet $\lambda_i \in \mathbb{R}$ 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 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ä

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

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

$L(x,y,\lambda) = (x - x_0)^2 + (y - y_0)^2 + \lambda(ax + by + c)$

Ratkaistaan funktion $L$ ääriarvot muuttujien $x$, $y$ ja $\lambda$ suhteen derivoimalla:

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

• Matemaattinen optimointi

Lähteet

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