Matemaattinen optimointi

Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä. Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan.

Matemaattinen optimointi tarkoittaa määritellyn parhaan ratkaisun valintaa kaikkien mahdollisten ratkaisujen joukosta. Yleensä matemaattinen optimointi liittyy funktioihin: kohde-, hyöty- tai kustannusfunktioihin. Kun kohdefunktio kuvaa ratkaisusta saatavaa hyötyä, jonka halutaan olevan mahdollisimman suuri, kutsutaan optimointitehtävää maksimoinniksi. Kun taas halutaan ratkaisusta koituvan mahdollisimman vähän kustannuksia tai haittaa, kutsutaan tehtävää minimoinniksi.

Formaalisti optimointi on sellaisen pisteen ${\displaystyle x^{*}}$ etsiminen ratkaisujoukosta ${\displaystyle \in A}$, missä funktio ${\displaystyle f:A\to \mathbb {R} }$ saa joko pienimmän tai suurimman arvonsa. Tätä pistettä ${\displaystyle x^{*}}$ kutsutaan minimipisteeksi.

Jokaista maksimointiongelmaa vastaa tietty minimointiongelma, joka ratkaisee maksimointiongelman. Funktion ${\displaystyle g}$ maksimointi on sama tehtävä kuin funktion ${\displaystyle f=-g}$ minimointi. Näin ollen matemaattisen optimointiteorian riittää tarkastella vain minimointiongelmaa.

Merkintätapa

Tehtävää, jonka tarkoituksena on etsiä ${\displaystyle f}$ pienin arvo, kutsutaan minimointitehtäväksi. Tehtäväkuvaus merkitään formaalisti

${\displaystyle \min _{x\in \mathbb {R} }f(x)}$

missä ${\displaystyle f}$ on tehtävän kohdefunktio.

Vastaavasti kohdefunktion maksimointitehtävää merkitään

${\displaystyle \max _{x\in \mathbb {R} }f(x)}$

Optimointitehtävässä

${\displaystyle \min f(\mathbf {x} )~,~\mathbf {x} \in S}$

joukkoa ${\displaystyle S}$ kutsutaan käyväksi ratkaisujoukoksi tai vain käyväksi joukoksi. Käypä joukko voidaan määritellä esimerkiksi

${\displaystyle S=[0,5]}$

Monen muuttujan tehtävässä käypä ratkaisujoukko voidaan määritellä esimerkiksi

${\displaystyle S=\{(x,y)|x>0{\text{ ja }}y<=5-2x\}}$

Optimointitehtävän globaali minimi on piste ${\displaystyle \mathbf {x} ^{*}}$, jolle pätee ${\displaystyle f(\mathbf {x} ^{*})\leq f(\mathbf {x} )}$ kaikilla ${\displaystyle \mathbf {x} }$, jotka kuuluvat käypään alueeseen. Tätä pienempää funktion arvoa ei voida saavuttaa käyvässä joukossa.

Funktiolla voi olla yksi tai useampi paikallinen optimipiste, lokaali optimi. Paikallinen minimi määritellään pisteeksi ${\displaystyle \mathbf {x} _{\mathrm {lok} }^{*}}$, jolle on olemassa ${\displaystyle \varepsilon >0}$ siten, että ${\displaystyle f(\mathbf {x} _{\mathrm {lok} }^{*})\leq f(\mathbf {x} _{\mathrm {lok} }^{*}+\mathbf {h} )~,\forall \mathbf {h} ,~||\mathbf {h} ||\leq \varepsilon }$ ja ${\displaystyle \mathbf {x} _{\mathrm {lok} }^{*}+\mathbf {h} }$ kuuluu käypään joukkoon. Toisin sanoen on olemassa jokin alue eli ympäristö, jossa piste ${\displaystyle \mathbf {x} _{\mathrm {lok} }^{*}}$ antaa pienempiä funktion arvoja kun muut pisteet.

Optimointitehtävätyyppejä

• Konveksin optimointitehtävän kohdefunktio sekä mahdolliset rajoitusehdot ovat konvekseja. Konveksin minimointitehtävän tärkeä ominaisuus on, että paikallinen minimipiste on myös tehtävän globaali minimipiste.
  • Lineaarisen optimointitehtävän (engl. lyh. LP) kohdefunktio ja rajoitusehdot ovat lineaarisia funktioita. Lineaarinen tehtävä on laajasti tutkittu ja tälle on kehitetty paljon tehokkaita ratkaisualgoritmeja kuten George Dantzigin vuonna 1947 ^lähde?.
  • Neliöllinen optimointitehtävä on konveksin optimointitehtävän erikoistapaus, missä kohdefunktio on neliöllinen ja käypä ratkaisujoukko monitahokas.
• Epälineaarinen optimointi on yleisnimitys optimointitehtävälle, jonka kohdefunktio ja mahdolliset rajoitusehdot ovat epälineaarisia
• Stokastisen optimointitehtävän kohdefunktiossa ja rajoitusehdoissa esiintyy yksi tai useampi satunnaismuuttuja.
• Kokonaislukuoptimointitehtävän käypä ratkaisujoukko kuuluu kokonaislukujen joukkoon. Kokonaislukuoptimointitehtävän ratkaiseminen on laskennallisesti haastavaa ja usein tyydytään riittävän hyvään ratkaisuun globaalin optimiratkaisun sijasta.
  • Dynaaminen ohjelmointitehtävä on tehokas kokonaislukutehtävän ratkaisumalli, jota voidaan soveltaa vain jos tehtävä on mahdollista esittää toisistaan riippumattomia alitehtävien yhdistelmänä. Ns. Bellmanin yhtälö määrää välttämättömät ehdot kohdetehtävlle, johon voidaan soveltaa dynaamisen ohjelmoinnin periaatetta.

Lineaarinen optimointi

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

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

${\displaystyle \mathbf {A_{1}x} \leq \mathbf {b_{1}} }$

${\displaystyle \mathbf {A_{2}x} \geq \mathbf {b_{2}} }$

${\displaystyle \mathbf {A_{3}x} =\mathbf {b_{3}} }$

Tässä ${\displaystyle \leq }$ ja ${\displaystyle \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

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

${\displaystyle \mathbf {Ax} =\mathbf {b} }$

${\displaystyle \mathbf {x\geq 0} }$

missä ${\displaystyle \mathbf {c} \in \mathbb {R} ^{n\times 1}}$, ${\displaystyle \mathbf {b} \in \mathbb {R} ^{m\times 1}}$ ja ${\displaystyle \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 ${\displaystyle \mathbf {c} }$ ja ${\displaystyle \mathbf {x} }$ muuttuvat tehtävätyypin muunnoksessa.

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 ${\displaystyle -\infty }$ tai on olemassa optimaalinen ratkaisu ${\displaystyle \mathbf {x} ^{*}}$. Huomaa, että optimipisteen ${\displaystyle \mathbf {x} ^{*}}$ yksikäsitteisyyttä ei ole taattu.
• Jos lineaarisen optimointitehtävän ratkaisu ${\displaystyle \mathbf {x} ^{*}}$ on äärellinen, tulee yksi ratkaisu löytymään jostain rajoittavan monitahokkaan S kulmasta. Jos kaksi pistettä ${\displaystyle \mathbf {x} _{1}}$ ja ${\displaystyle \mathbf {x} _{2}}$ ovat optimaalisia ovat myös pisteet muotoa ${\displaystyle \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 ${\displaystyle \mathbf {x_{1},x_{2}} \in S}$ pätee ${\displaystyle \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${\displaystyle f(\mathbf {x} _{1})=f(\mathbf {x} _{2})=:z}$. Toisaalta ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \mathbf {x} _{i},i=1,...n}$ ovat optimaalisia, niin ovat myös niiden ns. konveksikombinaatiot ${\displaystyle \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.

Esimerkkejä

Lineaarinen optimointitehtävä

${\displaystyle \min ~-x_{1}+x_{2}}$

${\displaystyle x_{1}+x_{2}\leq 0}$

${\displaystyle x_{1}\geq 1}$

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

${\displaystyle \min -x_{1}^{+}+x_{1}^{-}+x_{2}^{+}-x_{2}^{-}}$

${\displaystyle x_{1}^{+}-x_{1}^{-}+x_{2}^{+}-x_{2}^{-}+s_{1}+0\cdot s_{2}=0}$

${\displaystyle x_{1}^{+}-x_{1}^{-}+0\cdot x_{2}^{+}-0\cdot x_{2}^{-}+0\cdot s_{1}-s_{2}=1}$

${\displaystyle x_{i}^{\pm },s_{i}\geq 1~,i=1,2}$

Jos siis valitaan ${\displaystyle \mathbf {c} =[-1,1,1,-1,0,0]^{T}}$, ${\displaystyle \mathbf {b} =[0,1]^{T}}$, ${\displaystyle \mathbf {x} =[x_{1}^{+},x_{1}^{-},x_{2}^{+},x_{2}^{-},s_{1},s_{2}]^{T}}$ ja

${\displaystyle \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 ${\displaystyle x_{i}^{+}}$ ja ${\displaystyle x_{i}^{-}}$ on nollasta poikkeava, joten ylimääräiset muuttujat eivät vaikuta rajoitusehtoihin.

Epälineaarinen optimointi

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

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

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

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

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

missä ${\displaystyle f,g_{i},h_{j}:\mathbb {R} ^{n}\mapsto \mathbb {R} }$, f on mielivaltainen kohdefunktio, funktiot ${\displaystyle g_{i}}$ epäyhtälörajoitukset, ${\displaystyle h_{j}}$ yhtälörajoitukset ja X käypä joukko. Vaikka yhtälörajoitukset voidaan esittää epäyhtälörajoitusten avulla (${\displaystyle h_{i}\leq 0}$ ja ${\displaystyle -h_{i}\leq 0}$), tämä ei käytännössä aina ole mahdollista, sillä jotkin ratkaisumenetelmät olettavat tehtävän rajoitusten olevan optimipisteessä lineaarisesti riippumattomat.

Epälineaarinen ja lineaarinen tehtävä (LP) eroavat toisistaan seuraavasti. Epälineaarisessa tehtävässä käypä alue voi olla mielivaltainen, kun LP-tehtävän käypä joukko on aina monitahokas. Toiseksi LP-tehtävän lineaarinen kohdefunktio on aina myös konveksi, joten tehtävälle löydetään globaali optimi hyödyntämällä konveksin optimoinnin tuloksia. Epälineaarinen tehtävä on lineaarista tehtävää yleisempi, joten kaikki tulokset, jotka on johdettu epälineaariselle tehtävälle, pätevät myös lineaariselle tehtävälle.

Välttämättömät optimaalisuusehdot

Kun jokin optimointitehtävän käyvän alueen piste on optimaalinen, se täyttää välttämättömät optimaalisuusehdot. Lause ei päde toisin päin, eli tehtävälle voi olla mahdollista löytää optimaalisuusehdot täyttävä piste, joka ei välttämättä ole optimipiste.

Rajoittamattoman tehtävän välttämätön optimaalisuusehto optimointitehtävän ratkaisupisteelle ${\displaystyle \mathbf {x} ^{*}}$ on

${\displaystyle \nabla f(\mathbf {x} ^{*})=0}$

Yleiselle rajoitetulle tehtävälle 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 optimaalisuusehdot (välttämättömät FJ-ehdot).

Fritz Johnin välttämättömät optimaalisuusehdot

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

${\displaystyle 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}$

${\displaystyle u_{i}g_{i}(\mathbf {x} )=0,i=1,...,m}$

${\displaystyle u_{0}\geq 0,u_{i}\geq 0,i=1,...,m}$

missä ${\displaystyle \mathbf {u} }$ ja ${\displaystyle \mathbf {v} }$ ovat m ja l vektoreita joiden i:nnet komponintit ovat ${\displaystyle u_{i}}$ ja ${\displaystyle v_{i}}$. Luonnollisesti on oletettava, että gradientit ovat olemassa. FJ-ehdot saadaan toteutumaan mielivaltaiselle käyvälle pisteelle lisäämällä sopivia merkityksettömiä rajoituksia.

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

Fritz Johnin ehdot redusoituvat tietyin ehdoin KKT-ehdoiksi. KKT-ehdot ovat FJ-ehtoja hyödyllisempiä, sillä ne karsivat pois turhia kandidaattipisteitä. Käytännössä näiden ehtojen on taattava, että FJ-ehtojen ${\displaystyle u_{0}}$ on nollasta poikkeava, jolloin jakamalla sillä puolittain saadaan ns. KKT-ehdot.

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

${\displaystyle \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}$

${\displaystyle u_{i}g_{i}(\mathbf {x} )=0,i=1,...,m}$

${\displaystyle u_{i}\geq 0,i=1,...,m}$

missä ${\displaystyle \mathbf {u} }$ ja ${\displaystyle \mathbf {v} }$ ovat m ja l vektoreita joiden i:nnet komponentit ovat ${\displaystyle u_{i}}$ ja ${\displaystyle v_{i}}$.

Esimerkkejä

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

Kirjallisuutta

• Kaleva, Osmo: Optimointi 1. Opintomoniste 138. Tampere: TTKK, 1993. ISBN 951-722-073-1.
• Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 292. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.