Wikipedia

Ero sivun ”Matemaattinen optimointi” versioiden välillä

Selaa historiaa interaktiivisesti
[arvioimaton versio][arvioimaton versio]
← Vanhempi muutosUudempi muutos →
Poistettu sisältö Lisätty sisältö
VisuaalinenWikiteksti
Yonah (keskustelu | muokkaukset)
173 muokkausta
p pilkku lisätty ja reaalijoukon tunnus muutettu R -> \mathbb{R}
Yonah (keskustelu | muokkaukset)
173 muokkausta
kieliasua siistitty; pieniä kappaleiden jäsennyksiä
Rivi 1:
'''Matemaattinen optimointi''' on sellaisen pisteen <math>x^{*} \in A</math> etsiminen, jossa [[funktio]] <math>f : A \to \mathbb{R}</math> saa pienimmän arvonsa. Tätä pistettä <math>x^{*}</math> kutsutaan [[minimipiste|minimipisteeksi]]. Minimipisteen etsimistä kutsutaan ''minimoinniksi'' tai ''optimoinniksi''. Rajoitetussa optimointitehtävässä lähtöavaruudessa <math>A</math> on pisteitä, joita ei voida hyväksyä ratkaisuiksi. Vastaavasti ''maksimointi'' on sellaisen pisteen <math>y^{*} \in B</math> etsimistä, jossa funktio <math>g : B \to \mathbb{R}</math> saa suurimman arvonsa <math>g(y^{*})</math>.
 
Jokaista maksimointiongelmaa vastaa tietty minimointiongelma, joka ratkaisee maksimointiongelman. Funktion <math>g</math> maksimointi on sama tehtävä kuin funktion <math>f=-g</math> 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 <math>\mathbf{x}^*</math>, jolle pätee <math>f(\mathbf{x}^*)\leq f(\mathbf{x})</math> kaikilla <math>\mathbf{x}</math>, jotka kuuluvat käypään alueeseen, eli sitä pienempää funktion arvoa ei voida saavuttaa käyvässä joukossa. Lokaali minimi määritellään pisteeksi <math>\mathbf{x}_{\mathrm{lok}}^*</math>, jolle on olemassa <math>\epsilon > 0</math> siten, että <math>f(\mathbf{x}_{\mathrm{lok}}^*) \leq f(\mathbf{x}_{\mathrm{lok}}^*+\mathbf{h})~,\forall \mathbf{h},~||\mathbf{h}||\leq \epsilon</math> ja <math>\mathbf{x}_{\mathrm{lok}}^*+\mathbf{h}</math> kuuluu käypään joukkoon. Ts.Toisin sanoen on olemassa jokin alue eli ympäristö, jossa piste <math>\mathbf{x}_{\mathrm{lok}}^*</math> antaa pienempiä funktion arvoja kun muut pisteet.▼
Vastaavasti ''maksimointi'' on sellaisen pisteen <math>y^{*} \in B</math> etsimistä, jossa funktio <math>g : B \to \mathbb{R}</math> saa suurimman arvonsa <math>g(y^{*})</math>.
 
OptimointiongelmaOptimointitehtävä <math>P</math> esitetään matemaattisesti yleensä muodossa▼
▲Jokaista maksimointiongelmaa vastaa tietty minimointiongelma, joka ratkaisee maksimointiongelman. Funktion <math>g</math> maksimointi on sama tehtävä kuin funktion <math>f=-g</math> 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 <math>\mathbf{x}^*</math>, jolle pätee <math>f(\mathbf{x}^*)\leq f(\mathbf{x})</math> kaikilla <math>\mathbf{x}</math>, jotka kuuluvat käypään alueeseen, eli sitä pienempää funktion arvoa ei voida saavuttaa käyvässä joukossa. Lokaali minimi määritellään pisteeksi <math>\mathbf{x}_{\mathrm{lok}}^*</math>, jolle on olemassa <math>\epsilon > 0</math> siten, että <math>f(\mathbf{x}_{\mathrm{lok}}^*) \leq f(\mathbf{x}_{\mathrm{lok}}^*+\mathbf{h})~,\forall \mathbf{h},~||\mathbf{h}||\leq \epsilon</math> ja <math>\mathbf{x}_{\mathrm{lok}}^*+\mathbf{h}</math> kuuluu käypään joukkoon. Ts. on olemassa jokin alue eli ympäristö, jossa piste <math>\mathbf{x}_{\mathrm{lok}}^*</math> antaa pienempiä funktion arvoja kun muut pisteet.
:<math>P: \min f(\mathbf{x})~,~\mathbf{x\in S}~,</math>▼
missä <math>f:\mathbb{R}^n\mapsto \mathbb{R}</math> on kohdefunktio ja <math>S</math> käypä joukko. Käyvällä joukolla tarkoitetaan sitä joukkojoukkoa, johon tehtävän ratkaisun <math>\mathbf{x}^*</math>:n on kuuluttava.▼
 
Optimointiteoriassa hyödynnetään usein funktion derivaatan nollakohtaa. [[konveksi funktio|Konveksin funktion]] optimointi [[konveksi joukko|konveksissa]] käyvässä joukossa ja mahdollistaa epälineaarisen tehtävän globaalian optimin löytämisen.
▲Optimointiongelma <math>P</math> esitetään matemaattisesti yleensä muodossa
▲<math>P: \min f(\mathbf{x})~,~\mathbf{x\in S}~,</math>
▲missä <math>f:\mathbb{R}^n\mapsto \mathbb{R}</math> on kohdefunktio ja <math>S</math> käypä joukko. Käyvällä joukolla tarkoitetaan sitä joukko johon x:n on kuuluttava.
 
Optimointiteoria perustuu suurelta osin funktion derivaatan nollakohtaan. Myös [[konveksi joukko|konveksin joukon]] ja [[konveksi funktio|konveksin funktion]] käsitteet ovat osoittautuneet hyödylliseksi etenkin kun on etsitty funktion globaalia optimia.
 
==Esimerkkejä==
Rivi 86 ⟶ 84:
missä <math>f,g_i,h_j:\mathbb{R}^n\mapsto \mathbb{R}</math>, ''f'' on kohdefunktio, funktiot <math>g_i</math> epäyhtälörajoitukset, <math>h_j</math> yhtälörajoitukset ja X käypä joukko. Huomaa, että vaikka yhtälörajoitukset voidaan esittää pelkästään epäyhtälörajoitusten avulla (<math>h_i = 0 \Rightarrow h_i \leq 0 \wedge -h_i \leq 0</math>), 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äkinEpälineaarisessa tehtävässä 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 lineaarista tehtävää siis yleisempi, muoto kuin lineaarinen tehtävä. Näin ollenjoten 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 ===▼
 
Jos jokin piste on optimaalinen, se täyttää välttämättömät optimaalisuusehdot. Lause ei päde toisin päin, eli tehtävälle voidaan löytää optimaalisuusehdot täyttävä piste, joka ei ole optimipiste.
▲===Välttämättömät optimaalisuusehdot===
 
Rajoittamattoman tehtävän välttämätön optimaalisuusehto optimointitehtävän ratkaisupisteelle <math>\mathbf{x}^*</math> on
Kaikille epälineaarisille optimointitehtä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 <math>\Rightarrow</math> välttämättömät ehdot toteutuvat.
:<math>u_i\nabla g_if(\mathbf{x}^*) = 0, i = 1,...,m</math>▼
 
EpälineaariselleYleiselle tehtävällä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 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.
 
====Fritz-Johnin välttämättömät optimaalisuusehdot====
Rivi 101:
Olkoon käypä joukko epätyhjä ja avoin sekä <math>\mathbf{x}</math> jonkin epälineaarisen tehtävän lokaali optimi. Tällöin on olemassa vektori <math>(u_0,\mathbf{u,v})</math> siten, että
 
:<math>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</math>
:<math>u_i g_i(\geqmathbf{x}) = 0, i = 1,...,m</math>▼
:<math>u_0 \geq 0, u_i \geq 0, i = 1,...,m</math>▼
 
missä <math>\mathbf{u}</math> ja <math>\mathbf{v}</math> ovat m ja l vektoreita joiden i:nnet komponintit ovat <math>u_i</math> ja <math>v_i</math>. Luonnollisesti on oletettava, että gradientit ovat olemassa. FJ-ehdot saadaan toteutumaan mielivaltaiselle käyvälle pisteelle lisäämällä sopivia merkityksettömiä rajoituksia.▼
▲<math>u_i g_i(\mathbf{x}) = 0, i = 1,...,m</math>
 
▲<math>u_0 \geq 0, u_i \geq 0, i = 1,...,m</math>
 
▲missä <math>\mathbf{u}</math> ja <math>\mathbf{v}</math> ovat m ja l vektoreita joiden i:nnet komponintit ovat <math>u_i</math> ja <math>v_i</math>. Luonnollisesti on oletettava, että gradientit ovat olemassa.
 
====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 <math>u_0</math> on nollasta poikkeava, jolloin jakamalla sillä puolittain saadaan ns. KKT-ehdot.
 
Olkoon <math>\mathbf{x}</math> jonkin epälineaarisen tehtävän lokaali optimi, jolla on sopivat rajoitusehdot. Tällöin on olemassa vektori <math>(\mathbf{u,v})</math> siten, että
 
:<math>\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</math>
:<math>u_i g_i(\mathbf{x}) = 0, i = 1,...,m</math>
 
:<math>u_i g_i(\mathbf{x}) =geq 0, i = 1,...,m</math>
 
▲<math>u_i \geq 0, i = 1,...,m</math>
 
missä <math>\mathbf{u}</math> ja <math>\mathbf{v}</math> ovat m ja l vektoreita joiden i:nnet komponentit ovat <math>u_i</math> ja <math>v_i</math>.
Noudettu kohteesta ”https://fi.wikipedia.org/wiki/Matemaattinen_optimointi”