Ero sivun ”Matemaattinen optimointi” versioiden välillä

1 081 merkkiä lisätty ,  12 vuotta sitten
jäsennyksia; tavallisimmat optimointitehtävätyypit lisätty oman alaotsikon alle
(kieliasua siistitty; pieniä kappaleiden jäsennyksiä)
(jäsennyksia; tavallisimmat optimointitehtävätyypit lisätty oman alaotsikon alle)
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.
 
== Optimointitehtävätyypit ==
==Esimerkkejä==
* [[Konveksi optimointi]] tutkii konveksin funktion ja konveksin rajoitusjoukon muodostamaa tehtävää.
* Funktio <math>f(x)=ax^2+bx+c</math>, kun <math>a > 0</math>, saavuttaa miniminsä pisteessä <math>\frac{-b}{2a}</math>.
* [[Lineaarinen optimointi]] (LP) on konveksin optimointitehtävän erikoistapaus, missä kohdefunktio lineaarinen ja käypä joukko monitahokas.
* Funktiolla <math>f(x)=x</math>, kun <math>x \in \mathbb{R}</math>, ei ole minimipistettä, sillä jokaista pistettä <math>x</math> kohden on aina olemassa pienempi piste <math>y < x</math>.
* [[Kokonaislukuoptimointi]] tutkii lineaarisen tehtävää kokonaislukurajoitteilla. Kokonaislukuoptimointitehtävät ovat laskennallisesti erittäin haastavia.
* Funktiolla <math>f(x)=(x+1)^2(x-1)^2</math>on kaksi nollakohtaa <math>x_1=-1</math> ja <math>x_1=1</math>. Se on aina ei-negatiivinen, joten funktion minimiarvo on nolla. Huomaa, että kaksi eri <math>x</math>:n arvoa antavat saman optimin, eli optimi ei ole yksikäsitteinen. Jos optimointi tehdään rajoitetussa joukossa <math>x\geq 0</math>, niin optimi on yksikäsitteinen.
* [[Neliöllinen optimointi]] on konveksin optimointitehtävän erikoistapaus, missä kohdefunktio on neliöllinen ja käypä joukko monitahokas.
* [[Epälineaarinen optimointi]] tutkii yleistä optimointitehtävää.
* [[Stokastinen optimointi]] tutkii optimointitehtävää, jossa kohdefunktiossa tai rajoitusehdoissa esiintyy [[Satunnaismuuttuja#Satunnaismuuttuja|satunnaismuuttujia]].
* [[Dynaaminen ohjelmointi]] tutkii optimointimenetelmiä, jotka perustuvat tehtävän ratkaisemiseen pilkkomalla tehtävä pienempiin osatehtäviin. Osatehtävät kytkeytyvät toisiinsa ns. '''Bellmanin yhtälön''' kautta.
 
==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
 
:<math>\min \mathbf{c}^T \mathbf{x}</math>
:<math>\mathbf{A_2A_1 x} \geqleq \mathbf{b_2b_1}</math>
 
:<math>\mathbf{A_1A_2 x} \leqgeq \mathbf{b_1b_2}</math>
:<math>\mathbf{A_3 x} = \mathbf{b_3}</math>
 
<math>\mathbf{A_2 x} \geq \mathbf{b_2}</math>
 
<math>\mathbf{A_3 x} = \mathbf{b_3}</math>
 
Tässä <math>\leq</math> ja <math>\geq</math> 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
 
:<math>\min \mathbf{c}^T \mathbf{x}</math>
:<math>\mathbf{A x\geq} 0= \mathbf{b}</math>
 
:<math>\mathbf{A x}\geq = \mathbf{b0}</math>
 
<math>\mathbf{x\geq 0}</math>
 
missä <math>\mathbf{c}\in \mathbb{R}^{n\times 1}</math>, <math>\mathbf{b}\in \mathbb{R}^{m\times 1}</math> ja <math>\mathbf{A}\in \mathbb{R}^{m\times n}</math>. 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 <math>\mathbf{c}</math> ja <math>\mathbf{x}</math> muuttuvat tehtävätyypin muunnoksessa.
Lineaarinen optimointitehtävä
 
:<math>\min~-x_1+x_2</math>
:<math>x_1+x_2\geqleq 10</math>
 
:<math>x_1+x_2\leqgeq 01</math>
 
<math>x_1\geq 1</math>
 
voidaan esittää standardimuodossa muunnoksella <math>x_i = x_i^+-x_i^-</math>, missä <math>x_i^+</math> ja <math>x_i^-~\geq 0</math>. Kun lisätään vielä ali- ja ylijäämämuuttujat <math>s_1</math> ja <math>s_2</math> saadaan tehtäväksi
 
:<math>\min -x_1^+ + x_1^- + x_2^+ - x_2^-</math>
:<math>x_1^+ - x_1^- + 0\cdot x_2^+ - 0 \cdot x_2^- + s_1 + 0\cdot s_1 - s_2= 10</math>
 
:<math>x_1^+ - x_1^- + 0\cdot x_2^+ - 0 \cdot x_2^- + s_1 + 0\cdot s_1 - s_2= 01</math>
:<math>x_i^{\pm}, s_i \geq 1~,i = 1,2</math>
 
<math>x_1^+ - x_1^- + 0\cdot x_2^+ - 0 \cdot x_2^- + 0\cdot s_1 - s_2= 1</math>
 
<math>x_i^{\pm}, s_i \geq 1~,i = 1,2</math>
 
Jos siis valitaan <math>\mathbf{c} = [-1, 1, 1, -1, 0, 0]^T</math>, <math>\mathbf{b} = [0, 1]^T</math>, <math>\mathbf{x} = [x_1^+, x_1^-, x_2^+, x_2^-, s_1, s_2]^T</math> ja
Epälineaarisella optimoinnilla tarkoitetaan sellaisen optimointitehtävän ratkaisemista, joka on muotoa
 
:<math>\min f(\mathbf{x})</math>
:<math>g_i(\mathbf{x})\leq 0, i = 1,...,m</math>
:<math>h_j(\mathbf{x})=0, j= 1,...,l</math>
:<math>x\in X\subseteq \mathbb{R}^n</math>
 
missä <math>f,g_i,h_j:\mathbb{R}^n\mapsto \mathbb{R}</math>, ''f'' on mielivaltainen 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.
<math>g_i(\mathbf{x})\leq 0, i = 1,...,m</math>
 
<math>h_j(\mathbf{x})=0, j= 1,...,l</math>
 
<math>x\in X\subseteq \mathbb{R}^n</math>
 
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. Epälineaarisessa tehtävässä käyvän alueen muoto voi olla mielivaltainen, kun LP-tehtävän käypä joukko on aina monitahokas. Toiseksi LP-tehtävän kohdefunktio on aina konveksi, joten etsittäessä funktion globaalia optimia voidaan hyödyntää konveksioptimoinnin tuloksia.
 
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>.
 
 
==Esimerkkejä==
* Funktio <math>f(x)=ax^2+bx+c</math>, kun <math>a > 0</math>, saavuttaa miniminsä pisteessä <math>\frac{-b}{2a}</math>.
* Funktiolla <math>f(x)=x</math>, kun <math>x \in \mathbb{R}</math>, ei ole minimipistettä, sillä jokaista pistettä <math>x</math> kohden on aina olemassa pienempi piste <math>y < x</math>.
* Funktiolla <math>f(x)=(x+1)^2(x-1)^2</math>on kaksi nollakohtaa <math>x_1=-1</math> ja <math>x_1=1</math>. Se on aina ei-negatiivinen, joten funktion minimiarvo on nolla. Huomaa, että kaksi eri <math>x</math>:n arvoa antavat saman optimin, eli optimi ei ole yksikäsitteinen. Jos optimointi tehdään rajoitetussa joukossa <math>x\geq 0</math>, niin optimi on yksikäsitteinen.
 
== Katso myös ==
173

muokkausta