Ero sivun ”Matemaattinen optimointi” versioiden välillä

ei muokkausyhteenvetoa
===Tuloksia===
* Lineaarisen optimointitehtävän käypä alue on n [[dimensio|dimensioisen]] [[avaruus (matematiikka)|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 <math>-\infty</math> tai on olemassa optimaalinen ratkaisu <math>\mathbf{x}^*</math>. Huomaa, että optimipisteen <math>\mathbf{x}^*</math> yksikäsitteisyyttä ei ole taattu.
* Jos lineaarisen optimointitehtävän ratkaisu <math>\mathbf{x}^*</math> on äärellinen, tulee yksi ratkaisu löytymään jostain rajoittavan monitahokkaan ''S'' kulmasta. Jos kaksi pistettä <math>\mathbf{x}_1</math> ja <math>\mathbf{x}_2</math> ovat optimaalisia ovat myös pisteet muotoa <math>\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2~,\lambda\in (0,1)</math> 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 <math>\mathbf{x_1,x_2}\in S</math> pätee <math>\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2\in S~,\lambda\in (0,1)</math>. Koska annetut pisteet ovat optimaalisia, eli niitä pienempiä arvoja funktio ei voi monitahokkaassa saada, pätee<math>f(\mathbf{x}_1)= f(\mathbf{x}_2)=: z</math>. Toisaalta <math>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)}
</math>, mikä voidaan kirjoittaa <math>f(\lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2) = \lambda z + (1-\lambda) z = z~.~\square</math>. Helposti voidaan huomata, että tapaus voidaan yleistää koskemaan n:ää pistettä, eli jos pisteet <math>\mathbf{x}_i, i=1,... n</math> ovat optimaalisia, niin ovat myös niiden ns. konveksikombinaatiot <math>\sum_{i=1}^n a_n \mathbf{x}_n, \sum_{i=1}^n a_n =1, a_n\geq 0</math> myös optimaalisia. Todistus on analoginen kahden pisteen tapauksen kanssa.
:<math>\nabla f(\mathbf{x}^*) = 0</math>
 
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 John]]in 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ä <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ä
====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ä
65

muokkausta