Luentomateriaali e-kirjana

Lagrangen kertoimet ja PNS-menetelmä

Lagrangen kertoimet

Usein optimointitehtävissä halutaan asettaa rajoitusehtoja optimoitaville muuttujille. Tyypillinen esimerkki tällaisesta tehtävästä on peltipurkin muodon optimointi: Halutaan minimoida purkin pinta-ala (eli käytetty materiaali) \(A(h,r)=2\pi rh+2\pi r^2\) niin, että tilavuus \(V(r,h)=\pi r^2 h\) on vakio.

Duaalitehtävä: Halutaan maksimoida purkin tilavuus \(V(r,h)\) siten, että pinta-ala \(A(h,r)\) on vakio. Primaali- ja duaalitehtävillä on sama ratkaisu. Tämän sanoo maalaisjärkikin, mutta itse asiassa ratkaisuun johtavat yhtälötkin ovat (olennaisesti) samoja.

Havaitaan, että mikäli ongelmalla on ratkaisu, niin ratkaisupisteessä \((a,b)\) vektorien \(\nabla f\) ja \(\nabla g\) on oltava joko yhdensuuntaisia tai vastakkaissuuntaisia (mikäli \(\nabla g(a,b) \neq 0\)). Miksi? Koska muussa tapauksessa funktiolla \(f\) olisi nollasta poikkeva suunnattu derivaatta käyrän \(g(x,y)=0\) tangentin suuntaan pisteessä \((a,b)\), ja siis minimi ei voi olla pisteessä \((a,b)\).

Entä jos tehtävänä olisi maksimoida \(f(x,y)\) ehdolla \(g(x,y)=0\)? Entä jos tehtävänä olisi maksimoida \(g(x,y)\) ehdolla \(f(x,y)=c\)? Mikäli optimipiste on olemassa, se on Lagrangen funktion \[ L(x,y,\lambda) = f(x,y) + \lambda g(x,y) \]
kriittinen piste (eli gradientin nollakohta). Menetelmä yleistyy myös useammalle muuttujalle. Esimerkiksi kolmen muuttujan tapauksessa Lagrangen funktio on \[ L(x,y,z,\lambda,\mu) = f(x,y,z) + \lambda g(x,y,z) + \mu h(x,y,z), \]
missä \(f\) on minimoitava funktio ja rajoite-ehdot ovat \(g(x,y,z)=0\) sekä \(h(x,y,z)=0\).

Esimerkki

Minimoidaan funktio \(f(x,y)=x^2+y^2\) ehdolla \(g(x,y)=x^2y-16=0\). Muodostetaan aluksi Lagrangen funktio \[ L(x,y,\lambda)=x^2+y^2+\lambda(x^2y-16). \]
Yhtälöt kriittisille pisteille ovat \begin{align*} 0 &=\frac{\partial L}{\partial x} = 2x(1+\lambda y),\\ 0 &=\frac{\partial L}{\partial y} = 2y+\lambda x^2,\\ 0 &=\frac{\partial L}{\partial \lambda}= x^2y-16,\\ \end{align*} joista viimeinen on aina itse rajoitusehto.

Ensimmäisestä yhtälöstä saadaan \(x=0\) tai \(\lambda y=-1\), mutta \(x=0\) on ristiriidassa kolmannen yhtälön kanssa. Siten toisesta yhtälöstä \[ 0=2y^2+\lambda yx^2 = 2y^2-x^2. \]
Tästä saadaan edelleen \(x=\pm \sqrt{2}y\), ja \(2y^3=16\) eli \(y=2\). Ääriarvoja (mahdollisia minimejä) on siis kaksi \((x,y) = (\pm 2\sqrt{2},2)\). Pitää selvittää muilla keinoin, ovatko nämä minimejä vai maksimeja.

Esimerkki

Yritetään etsiä Lagrangen kertoimien menetelmällä funktion \(f(x,y)=y\) minimi ehdolla \(g(x,y)=y^3-x^2=0\). Helposti havaitaan, että minimi \(f(x,y)=0\) saavutetaan pisteessä \((0,0)\).

Muodostetaan Lagrangen funktio \[ L(x,y,\lambda)=y+\lambda(y^3-x^2). \]
Saadaan yhtälöt \[ -2\lambda x =0,\quad 1+3\lambda y^2=0,\text{ ja } y^3-x^2=0. \]
Nämä yhtälöt ovat keskenään ristiriidassa, joten ratkaisua niille ei ole. Huomaa, että \(\nabla g(0,0) =\mathbf{0}\) minimipisteessä. Tästä nähdään, Lagrangen kertoimet näkevät ääriarvoja vain pisteissä, joissa \(\nabla g(0,0) \neq \mathbf{0}\).

Esimerkki

Etsitään ääriarvot funktiolle \(f(x,y,z)=xy+2z\) ehdoilla \(x+y+z=0\) ja \(x^2+y^2+z^2=24\).

Koska \(f\) on jatkuva ja annettujen leikkausjoukkojen leikkaus on ympyräviiva (eli rajoitettu ja suljettu joukko), niin ääriarvot ovat olemassa. Muodostetaan Lagrangen funktio \[ L(x,y,z,\lambda,\mu)=xy+2z+\lambda(x+y+z)+\mu(x^2+y^2+z^2-24). \]
Lagrangen funktion osittaisderivaatoista saadaan yhtälöt \begin{align*} & y+\lambda+2\mu x=0, \\ & x+\lambda+2\mu y=0, \\ & 2+\lambda+2\mu z=0, \\ & x+y+z = 0,\text{ ja } \\ & x^2+y^2+z^2-24=0. \end{align*} Kahden ensimmäisen yhtälön erotus johtaa yhtälöön \((x-y)(1-2\mu)=0\), joten joko \(\mu = 1/2\) tai \(x=y\). Tutkitaan molemmat tapaukset.

Tapaus I (\(\mu = 1/2\)): Toisen ja kolmannen yhtälön perusteella \[ x+\lambda +y =0\textrm{ ja } 2+\lambda +z =0,\text{ siis }x+y=2+z. \]
Neljännestä yhtälöstä saadaan \(z=-1\) ja \(x+y=1\). Viimeisen yhtälön perusteella \(x^2+y^2=24-z^2=23\). Koska \(x^2+y^2+2xy=(x+y)^2 =1\), saadaan \(2xy=1-23=-22\) ja \(xy=-11\). Nyt \((x-y)^2 = x^2+y^2-2xy = 23+22=45\), joten \(x-y=\pm 3\sqrt{5}\). Yhdessä yhtälön \(x+y=1\) tästä saadaan kaksi kriittistä pistettä \[ P_1 = \big((1+3\sqrt{5})/2,(1-3\sqrt{5})/2,-1\big)\text{ ja } P_2 = \big((1-3\sqrt{5})/2,(1+3\sqrt{5})/2,-1\big). \]
Kummassakin pisteessä \(f(x,y,z)=-11-2 = -13\).
Tapaus II (\(x=y\)): Neljännestä yhtälöstä nähdään, että \(z=-2x\), ja viimeisen yhtälön perusteella \(6x^2=24\) eli \(x=\pm 2\). Näin ollen, kriittiset pisteet ovat \[ P_3=(2,2,-4)\text{ ja } P_4=(-2,-2,4). \]
Saadaan \[ f(2,2,-4)=4-8=-4\text{ ja } f(-2,-2,4)=4+8=12. \]
Siten funktion \(f\) maksimi on \(12\) ja minimi \(-13\).

\(\bigstar\) Regressio-ongelma

Regressioanalyysissa pyritään valitsemaan parametrin \(\mathbf{\beta}\) arvo siten, että käyrä \[ y=f(x;\beta) \]
kulkisi mahdollisimman läheltä jokaista havaintopistettä \[ (x_j,y_j)\in \mathbb{R}^2,\, j=1,2,\ldots ,n. \]
Tällaista optimaalisesti valittua käyrää kutsutaan regressiomalliksi \(y=f(x;\beta)\), jossa funktion \(f\) muoto on valittu tilanteen ja harkinnan mukaan. Kunhan \(f\) on valittu, niin eräs ratkaisu käyränsovitusongelmaan on pienimmän neliösumman menetelmä.

\(\bigstar\) Pienimmän neliösumman menetelmä

Pienimmän neliösumman menetelmässä pyritään minimoimaan regressiomallin virhetermien \(\varepsilon_j\) \[ \varepsilon_j = y_j - f(x_j;\beta ) \, , \quad j=1,2,\ldots ,n \]
neliösummaa eli funktiota \[ F(\beta)= \sum_{j=1}^n\varepsilon_j^2 =\sum_{j=1}^n\big(y_j-f(x_j;\beta)\big)^2. \]
muuttamalla parametrivektorin \(\mathbf{\beta}=(\beta_0,\beta_1,\ldots,\beta_m)\) arvoa. Optimaalinen \(\mathbf{\beta}\):n arvo on parametrin \(\beta\) {\em pienimmän neliösumman estimaatti} eli PNS-estimaatti.
Kysymys: Miksi ei minimoitaisi lauseketta \(\sum_{j=1}^n|y_j-f(x_j;\beta)|\) neliösumman sijasta?

\(\bigstar\) PNS-sovitus

Kuvassa vihreällä parametreista \(\mathbf{\beta} = (\beta_1, \beta_2, \ldots , \beta_m)\) riippuva sovitettava funktio \(f(x;\mathbf{\beta})\) eräällä kiinteällä parametrin arvolla. Datapisteet \((x_j,y_j)\) ja vastaavat virhetermit \(\varepsilon_j\), kun \(j = 1, \ldots , n\).

\(\bigstar\) Lineaarinen regressio

Lineaarisessa regressiossa\(f(x;\beta) = \beta_0-\beta_1 x\) jossa \(\beta = (\beta_0, \beta_1)\) ja neliösumma on \[ F(\beta_0,\beta_1)=\sum_i (y_i -\beta_0-\beta_1 x_i)^2. \]
Etsitään piste \((\beta_0,\beta_1)\) siten, että \(\nabla F(\beta_0,\beta_1)=0\).

Lasketaan osittaisderivaatta \[ \frac{\partial}{\partial \beta_0}F(\beta_0,\beta_1) = 2\big(\beta_1\sum_i x_i+n\beta_0-\sum_i y_i\big). \]
Ratkaistaan nollakohta \[ \beta_0=\frac{1}{n}\sum_i y_i-\frac{\beta_1}{n} \sum_i x_i =\overline{\mathbf{y}} -\beta_1 \overline{\mathbf{x}} \]
missä \(\overline{\mathbf{x}}\) on datavektorin \(\mathbf{x} = (x_1, x_2, \ldots , x_n)\) komponenttien aritmeettinen keskiarvo.

Lasketaan seuraavaksi osittaisderivaatta \[ \frac{\partial}{\partial \beta_1}F(\beta_0,\beta_1) = 2\big(\beta_0\sum_i x_i+\beta_1\sum_i x_i^2-\sum_i x_iy_i\big). \]
Sijoittamalla \(\beta_0\):n lauseke, saadaan \[ n\overline{\mathbf{x}} \overline{\mathbf{y}} - n \beta_1 \overline{\mathbf{x}} ^2+\beta_1 \sum_i x_i^2-\sum_i x_i y_i=0. \]
Ratkaistaan nollakohta \[ \beta_1=\frac{n\overline{\mathbf{x}} \overline{\mathbf{y}} -\sum_i x_iy_i}{n\overline{\mathbf{x}} ^2-\sum_i x_i^2} = \frac{\sum_i(x_i-\overline{\mathbf{x}})(y_i-\overline{\mathbf{y}})}{\sum_i(x_i-\overline{\mathbf{x}})^2}. \]
Tarkista jälkimmäinen yhtälö!

Esimerkki

Sovita PNS-suora dataan

\(x_i\)	0.0	1.0	2.0	3.0	4.0
\(y_i\)	2.10	1.92	1.84	1.71	1.64

ja estimoi (ekstrapoloi) \(y\) kun \(x=5\).

Saadaan \(\overline{\mathbf{x}}=2.0\), \(\overline{\mathbf{y}}= 1.842\), ja \[ \beta_1 = \frac{-1.13}{10.0} = -0.113. \]
Siten \(\beta_0=1.842 +0.113\cdot 2.0= 2.068\). Näin ollen \(y=-0.113x + 2.068\), ja haluttu estimaatti pisteessä \(x=5\) on \(y=-0.113\cdot 5 + 2.068=1.503\).

Esimerkki: Toisen asteen sovitus

Tutkitaan lisäaineen määrän \(x\) vaikutusta kuivumisaikaan \(y\). Eri lisäaineen määrillä \(x_i\) (grammaa) saatiin kuivumisajat \(y_i\) (tuntia), \(i=1,\ldots,9\):

Huomataan, että kuivumisajan riippuvuus lisäaineen määrästä on epälineaarista. Minimikohdan estimoimiseksi sovitetaan havaintoihin paraabeli \[y=\beta_0+\beta_1x+\beta_2x^2.\]
Pienimmän neliösumman yhtälöryhmä mallille on \[ \frac{\partial}{\partial \beta_k} \sum(y_i-\beta_0-\beta_1x_i-\beta_2x_i^2)^2 = 0, \qquad k=0,1,2. \]
Näistä saadaan yhtälöryhmä \[ \left\{ \begin{array}{rcl} n\beta_0 + \beta_1\sum x_i +\beta_2 \sum x_i^2 &=& \sum y_i,\\ \beta_0\sum x_i+\beta_1 \sum x_i^2+\beta_2 \sum x_i^3 &=& \sum x_iy_i\\ \beta_0\sum x_i^2+\beta_1 \sum x_i^3+\beta_2 \sum x_i^4 &=& \sum x_i^2y_i. \end{array}\right. \]
Laskemalla yhtälöryhmän kertoimet havainnoista saadaan \[ \left\{ \begin{array}{rcl} 9\beta_0 + 36\beta_1 + 204\beta_2 &=& 72.1\\ 36\beta_0 +204\beta_1 + 1296 \beta_2 &=& 266.6 \\ 204 \beta_0 +1296\beta_1 + 8772\beta_2 &=& 1515.4 \end{array}\right. \]
Ratkaisuna ovat \( \beta_0=11.15\), \(\beta_1=-1.806\) ja \( \beta_2=0.1803\). Pienimmän neliösumman mielessä parhaiten havaintoihin liittyvä paraabeli on siis \[ y=11.15 - 1.806x + 0.1803 x^2. \]