Matemaattinen optimointi

Wikipedia

Matemaattinen optimointi on sellaisen pisteen $x^{*} \in A$ etsimistä jossa funktio $f : A \to R$ saa pienimmän arvonsa. Pistettä $x *$ kutsutaan minimipisteeksi. Minimipisteen etsimistä kutsutaan minimoinniksi tai optimoinniksi. Rajoitetussa optimointitehtävässä lähtöavaruudessa $A$ on pisteitä, joita ei voida hyväksyä ratkaisuiksi.

Vastaavasti maksimointi on sellaisen pisteen $y^{*} \in B$ etsimistä, jossa funktio $g : B \to R$ saa suurimman arvonsa $g (y *)$ .

Jokaista maksimointiongelmaa vastaa tietty minimointiongelma, joka ratkaisee maksimointiongelman. Funktion $g$ maksimointi on sama tehtävä kuin funktion $f = - g$ minimointi. Näin ollen matemaattisen optimointiteorian riittää tarkastella pelkästään minimointiongelmia. Funktiolla voi olla lokaaleja sekä globaaleja minimejä. Globaali minimi määritellään pisteeksi $\mathbf{x}^*$ , jolle pätee $f(\mathbf{x}^*)\leq f(\mathbf{x})$ kaikilla $\mathbf{x}$ , jotka kuuluvat käypään alueeseen, eli sitä pienempää funktion arvoa ei voida saavuttaa käyvässä joukossa. Lokaali minimi määritellään pisteeksi $\mathbf{x}_{\mathrm{lok}}^*$ , jolle on olemassa $ε > 0$ siten, että $f(\mathbf{x}_{\mathrm{lok}}^*) \leq f(\mathbf{x}_{\mathrm{lok}}^*+\mathbf{h})~,\forall \mathbf{h},~||\mathbf{h}||\leq \epsilon$ ja $\mathbf{x}_{\mathrm{lok}}^*+\mathbf{h}$ kuuluu käypään joukkoon. Ts. on olemassa jokin alue eli ympäristö, jossa piste $\mathbf{x}_{\mathrm{lok}}^*$ antaa pienempiä funktion arvoja kun muut pisteet.

Optimointiongelma $P$ esitetään matemaattisesti yleensä muodossa $P: \min f(\mathbf{x})~,~\mathbf{x\in S}~,$ missä $f:\mathbb{R}^n\mapsto \mathbb{R}$ on kohdefunktio ja $S$ käypä joukko. Käyvällä joukolla tarkoitetaan sitä joukko johon x:n on kuuluttava.

Optimointiteoria perustuu suurelta osin funktion derivaatan nollakohtaan. Myös konveksin joukon ja konveksin funktion käsitteet ovat osoittautuneet hyödylliseksi etenkin kun on etsitty funktion globaalia optimia.

Sisällysluettelo

1 Esimerkkejä
2 Lineaarinen optimointi
- 2.1 Tuloksia
- 2.2 Esimerkkejä
3 Epälineaarinen optimointi
- 3.1 Välttämättömät optimaalisuusehdot
  - 3.1.1 Fritz-Johnin välttämättömät optimaalisuusehdot
  - 3.1.2 Karush-Kuhn-Tuckerin välttämättömät optimaalisuusehdot
4 Katso myös

[muokkaa] Esimerkkejä

Funktio $f (x) = a x 2 + b x + c$ , kun $a > 0$ , saavuttaa miniminsä pisteessä $\frac{-b}{2a}$ .
Funktiolla $f (x) = x$ , kun $x \in \mathbb{R}$ , ei ole minimipistettä, sillä jokaista pistettä $x$ kohden on aina olemassa pienempi piste $y < x$ .
Funktiolla $f (x) = (x + 1) 2 (x - 1) 2$ on kaksi nollakohtaa $x 1 = - 1$ ja $x 1 = 1$ . Se on aina ei-negatiivinen, joten funktion minimiarvo on nolla. Huomaa, että kaksi eri $x$ :n arvoa antavat saman optimin, eli optimi ei ole yksikäsitteinen. Jos optimointi tehdään rajoitetussa joukossa $x\geq 0$ , niin optimi on yksikäsitteinen.

[muokkaa] Lineaarinen optimointi

Lineaarinen optimointi tarkoittaa optimointia kun kohdefunktio ja käypää aluetta rajoittavat ehdot ovat lineaarisia. Lineaarista optimointi kutsutaan myös lineaariseksi ohjelmoinniksi. Yleinen linearinen tehtävä voidaan esittää muodossa

$\min \mathbf{c}^T \mathbf{x}$

$\mathbf{A_1 x} \leq \mathbf{b_1}$

$\mathbf{A_2 x} \geq \mathbf{b_2}$

$\mathbf{A_3 x} = \mathbf{b_3}$

Tässä $\leq$ ja $\geq$ merkeillä tarkoitetaan, että jokaista alkiota verrataan riveittäin toisiinsa. Voidaan osoittaa, että kaikki lineaariset optimointitehtävät voidaan esittään ali- ja ylijäämämuuttujien (engl. slack variable) avulla ns. standardimuodossa

$\min \mathbf{c}^T \mathbf{x}$

$\mathbf{A x} = \mathbf{b}$

$\mathbf{x\geq 0}$

missä $\mathbf{c}\in \mathbb{R}^{n\times 1}$ , $\mathbf{b}\in \mathbb{R}^{m\times 1}$ ja $\mathbf{A}\in \mathbb{R}^{m\times n}$ . Ts. aina kun tarkastellan yleistä lineaarista tehtävää, voidaan tarkastella pelkästään standarditehtävää menettämättä tuloksien yleispätevyyttä. Huomaa, että myös vektorit $\mathbf{c}$ ja $\mathbf{x}$ muuttuvat tehtävätyypin muunnoksessa.

[muokkaa] Tuloksia

Lineaarisen optimointitehtävän käypä alue on n dimensioisen avaruuden monitahokas (engl. polyhedra).
Oletetaan, että tehtävänä on minimoida lineaarista kohdefunktiota epätyhjän monitahokkaan sisällä (ts. kyseessä on lineaarinen optimointitehtävä). Tällöin kohdefunktion optimaalinen arvo on $-\infty$ tai on olemassa optimaalinen ratkaisu $\mathbf{x}^*$ . Huomaa, että optimipisteen yksikäsitteisyyttä ei ole taattu.
Jos lineaarisen optimointitehtävän ratkaisu $\mathbf{x}^*$ on äärellinen, tulee yksi ratkaisu löytymään jostain rajoittavan monitahokkaan S kulmasta. Jos kaksi pistettä $\mathbf{x}_1$ ja $\mathbf{x}_2$ ovat optimaalisia ovat myös pisteet muotoa $\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2~,\lambda\in (0,1)$ optimaalisia. Tämän voi tulkita siten, että kahden kulman välillä oleva särmä on optimaalinen, jos kummatkin kulmat ovat optimaalisia. Todistus: Oletetaan, että annetut pisteet minimoivat kohdefunktion f. Voidaan osoittaa, että monitahokas on konveksi joukko, eli kaikilla $\mathbf{x_1,x_2}\in S$ pätee $\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2\in S~,\lambda\in (0,1)$ . Koska annetut pisteet ovat optimaalisia, eli niitä pienempiä arvoja funktio ei voi monitahokkaassa saada, pätee $f(\mathbf{x}_1)= f(\mathbf{x}_2)=: z$ . Toisaalta $f(\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2) = \mathbf{c}^T(\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2) = \underbrace{\mathbf{c}^T \lambda \mathbf{x}_1}_{= \lambda f(\mathbf{x}_1)} + \underbrace{\mathbf{c}^T(1-\lambda)\mathbf{x}_2}_{=(1-\lambda)f(\mathbf{x}_2)}$ , mikä voidaan kirjoittaa $f(\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2) = \lambda z + (1-\lambda) z = z~.~\square$ . Helposti voidaan huomata, että tapaus voidaan yleistää koskemaan n:ää pistettä, eli jos pisteet $\mathbf{x}_i, i=1,... n$ ovat optimaalisia, niin ovat myös niiden ns. konveksikombinaatiot $\sum_{i=1}^n a_n \mathbf{x}_n, \sum_{i=1}^n a_n =1, a_n\geq 0$ myös optimaalisia. Todistus on analoginen kahden pisteen tapauksen kanssa.

[muokkaa] Esimerkkejä

Lineaarinen optimointitehtävä

$\min~-x_1+x_2$

$x_1+x_2\leq 0$

$x_1\geq 1$

voidaan esittää standardimuodossa muunnoksella $x_i = x_i^+-x_i^-$ , missä $x_i^+$ ja $x_i^-~\geq 0$ . Kun lisätään vielä ali- ja ylijäämämuuttujat $s 1$ ja $s 2$ saadaan tehtäväksi

$\min -x_1^+ + x_1^- + x_2^+ - x_2^-$

$x_1^+ - x_1^- + x_2^+ - x_2^- + s_1 + 0\cdot s_2= 0$

$x_1^+ - x_1^- + 0\cdot x_2^+ - 0 \cdot x_2^- + 0\cdot s_1 - s_2= 1$

$x_i^{\pm}, s_i \geq 1~,i = 1,2$

Jos siis valitaan $\mathbf{c} = [-1, 1, 1, -1, 0, 0]^T$ , $\mathbf{b} = [0, 1]^T$ , $\mathbf{x} = [x_1^+, x_1^-, x_2^+, x_2^-, s_1, s_2]^T$ ja

$\mathbf{A} = \begin{bmatrix} 1 & -1 & 1 & -1 & 1 & 0 \\ 1 & -1 & 0 & 0 & 0 & -1 \\ \end{bmatrix}~,$

on tehtävä saatu standardimuotoon. Huomaa, että optimipisteessä vain toinen muuttujista $x_i^+$ ja $x_i^-$ on nollasta poikkeava, joten ylimääräiset muuttujat eivät vaikuta rajoitusehtoihin.

[muokkaa] Epälineaarinen optimointi

Epälineaarisella optimoinnilla tarkoitetaan sellaisen optimointitehtävän ratkaisemista, joka on muotoa

$\min f(\mathbf{x})$

$g_i(\mathbf{x})\leq 0, i = 1,...,m$

$h_j(\mathbf{x})=0, j= 1,...,l$

$x\in X\subseteq \mathbb{R}^n$

missä $f,g_i,h_j:\mathbb{R}^n\mapsto \mathbb{R}$ , f on kohdefunktio, funktiot $g i$ epäyhtälörajoitukset, $h i$ yhtälörajoitukset ja X käypä joukko. Huomaa, että vaikka yhtälörajoitukset voidaan esittää pelkästään epäyhtälörajoitusten avulla ( $h_i = 0 \Rightarrow h_i \leq 0 \wedge -h_i \leq 0$ ), ei näin kuitenkaan kannata tehdä: Monet johdetut tulokset olettavat rajoitusten lineaarista riippumattomuutta, jolloin kätevin tapa ratkaista on erotella yhtälö- ja epäyhtälörajoitukset.

Epälineaarinen ja lineaarinen tehtävä (LP) eroavat toisistaan monissa kohdissa. Ensinnäkin käyvän alueen muoto voi olla mielivaltainen epälineaarisessa tehtävässä, kun taas LP-tehtävän käypä joukko on aina monitahokas (joka on aina konveksi joukko). Toiseksi LP-tehtävän kohdefunktio on aina konveksi, joten etsittäessä funktion globaalia optimia voidaan hyödyntää konveksioptimoinnin tuloksia. Lisäksi huomataan, että epälineaarisen tehtävän optimi ei aina ole rajoittavan joukon reunoilla, vaan se voi sijaita muualla. Voidaan todistaa, että optimi sijaitsee tällöin kohdefunktion derivaatan nollakohdassa.

Epälineaarinen tehtävä on siis yleisempi muoto kuin lineaarinen tehtävä. Näin ollen kaikki tulokset, jotka on johdettu epälineaariselle tehtävälle, pätevät myös lineaariselle tehtävällä.

[muokkaa] Välttämättömät optimaalisuusehdot

Kaikkille epälineaarisille optimintitehtäville voidaan johtaa ns. välttämättömät optimaalisuusehdot. Niiden avulla voi tarkistaa voiko jokin piste olla optimi vai ei. Ts. jos jokin piste on optimaalinen, täyttää se optimaalisuusehdot. Matemaattisesti esitettynä: piste x on optimaalinen $\Rightarrow$ välttämättömät ehdot toteutuvat.

Epälineaariselle tehtävällä voidaan johtaa Karush-Kuhn-Tuckerin välttämättömät optimaalisuusehdot (välttämättömät KKT-ehdot), ja hieman yleisemmät Fritz-Johnin välttämättömät optimaalisuus ehdot (välttämättömät FJ ehdot). Näistä KKT-ehdot ovat hyödyllisempiä, sillä ne todella karsivat pois optimikandidaatteja. FJ-ehdot saadaan toteutumaan mielivaltaiselle käyvälle pisteelle lisäämällä sopivia merkityksettömiä rajoituksia.

[muokkaa] Fritz-Johnin välttämättömät optimaalisuusehdot

Olkoon käypä joukko epätyhjä ja avoin sekä $\mathbf{x}$ jonkin epälineaarisen tehtävän lokaali optimi. Tällöin on olemassa vektori $(u_0,\mathbf{u,v})$ siten, että

$u_0\nabla f(\mathbf{x})+\sum_{i=1}^m u_i \nabla g_i(\mathbf{x})+\sum_{i=1}^l v_i \nabla h_i(\mathbf{x}) = 0$

$u_i g_i(\mathbf{x}) = 0, i = 1,...,m$

$u_0 \geq 0, u_i \geq 0, i = 1,...,m$

missä $\mathbf{u}$ ja $\mathbf{v}$ ovat m ja l vektorita joiden i:nnet komponintit ovat $u i$ ja $v i$ . Luonnollisesti on oletettava, että gradientit ovat olemassa.

[muokkaa] Karush-Kuhn-Tuckerin välttämättömät optimaalisuusehdot

Fritz-Johnin ehdot redusoituvat tietyin ehdoin KKT-ehdoiksi. Käytännössä näiden ehtojen on taattava, että FJ-ehtojen $u 0$ on nollasta poikkeava, jolloin jakamalla sillä puolittain saadaan ns. KKT-ehdot.

Olkoon $\mathbf{x}$ jonkin epälineaarisen tehtävän lokaali optimi, jolla on sopivat rajoitusehdot. Tällöin on olemassa vektori $(\mathbf{u,v})$ siten, että