Matemaattinen optimointi
Matemaattinen optimointi tarkoittaa määritellyn kohde-, hyöty- tai kustannusfunktion perusteella parhaan ratkaisun valintaa kaikkien mahdollisten ratkaisujen joukosta. Kun kohdefunkio 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 formula_1 etsiminen ratkaisujoukosta formula_2, missä funktio formula_3 saa joko pienimmän tai suurimman arvonsa. Tätä pistettä formula_1 kutsutaan minimipisteeksi.
Jokaista maksimointiongelmaa vastaa tietty minimointiongelma, joka ratkaisee maksimointiongelman. Funktion formula_5 maksimointi on sama tehtävä kuin funktion formula_6 minimointi. Näin ollen matemaattisen optimointiteorian riittää tarkastella vain minimointiongelmaa.
Tehtävää, jonka tarkoituksena on etsiä formula_7 pienin arvo, kutsutaan minimointitehtäväksi. Tehtäväkuvaus merkitään formaalisti
missä formula_7 on tehtävän kohdefunktio.
Vastaavasti kohdefunktion maksimointitehtävää merkitään
Optimointitehtävässä
joukkoa formula_12 kutsutaan käyväksi ratkaisujoukoksi tai vain käyväksi joukoksi. Käypä joukko voidaan määritellä esimerkiksi
Monen muuttujan tehtävässä käypä ratkaisujoukko voidaan määritellä esimerkiksi
Optimointitehtävän globaali minimi on piste formula_15, jolle pätee formula_16 kaikilla formula_17, 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. Lokaali minimi määritellään pisteeksi formula_18, jolle on olemassa formula_19 siten, että formula_20 ja formula_21 kuuluu käypään joukkoon. Toisin sanoen on olemassa jokin alue eli ympäristö, jossa piste formula_18 antaa pienempiä funktion arvoja kun muut pisteet.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
Tässä formula_27 ja formula_28 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
missä formula_32, formula_33 ja formula_34. 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 formula_35 ja formula_17 muuttuvat tehtävätyypin muunnoksessa.Lineaarinen optimointitehtävä
voidaan esittää standardimuodossa muunnoksella formula_54, missä formula_55 ja formula_56. Kun lisätään vielä ali- ja ylijäämämuuttujat formula_57 ja formula_58 saadaan tehtäväksi
Jos siis valitaan formula_63, formula_64, formula_65 ja
formula_66
on tehtävä saatu standardimuotoon. Huomaa, että optimipisteessä vain toinen muuttujista formula_55 ja formula_68 on nollasta poikkeava, joten ylimääräiset muuttujat eivät vaikuta rajoitusehtoihin.
Epälineaarisella optimoinnilla tarkoitetaan sellaisen optimointitehtävän ratkaisemista, joka on muotoa
missä formula_73, "f" on mielivaltainen kohdefunktio, funktiot formula_74 epäyhtälörajoitukset, formula_75 yhtälörajoitukset ja X käypä joukko. Vaikka yhtälörajoitukset voidaan esittää epäyhtälörajoitusten avulla (formula_76 ja formula_77), 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.
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 formula_15 on
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).
Olkoon käypä joukko epätyhjä ja avoin sekä formula_17 jonkin epälineaarisen tehtävän lokaali optimi. Tällöin on olemassa vektori formula_81 siten, että
missä formula_85 ja formula_86 ovat m ja l vektoreita joiden i:nnet komponintit ovat formula_87 ja formula_88. Luonnollisesti on oletettava, että gradientit ovat olemassa. FJ-ehdot saadaan toteutumaan mielivaltaiselle käyvälle pisteelle lisäämällä sopivia merkityksettömiä rajoituksia.
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 formula_89 on nollasta poikkeava, jolloin jakamalla sillä puolittain saadaan ns. KKT-ehdot.
Olkoon formula_17 jonkin epälineaarisen tehtävän lokaali optimi, jolla on sopivat rajoitusehdot. Tällöin on olemassa vektori formula_91 siten, että
missä formula_85 ja formula_86 ovat m ja l vektoreita joiden i:nnet komponentit ovat formula_87 ja formula_88.