Optimointiteoriassa

Optimointiteoria on matematiikan ja soveltavien alojen tutkimusala, joka keskittyy siihen, kuinka löytää päätösmuuttujien joukosta optimaalisin ratkaisu. Ongelman perusmuoto määrittelee päätösmuuttujat x, tavoitefunktion f(x) sekä mahdolliset rajoitteet G(x) ≤ 0 ja H(x) = 0. Tavoitteena on minimoida tai maksimoida f(x).

Ongelmat jaetaan rajoitettuihin ja rajoittamattomiin sekä luokkiin kuten lineaarinen ohjelmointi (LP), epälineaarinen ohjelmointi (NLP) ja kokonaislukuohjelmointi (IP). Erityisen tärkeä alalaji on konveksinen optimointi, jossa sekä tavoitefunktio että rajoitteet muodostavat konveksin ongelman; tällöin paikallinen optimi on yleensä globaali.

Optimaalisuuden ehdoista käytetään Lagrangian-menetelmää ja Kuhn–Tucker -ehtoja (KKT). Näiden avulla muodostetaan järjestelmä, jonka ratkaiseminen antaa optimaalisen x:n ja mahdolliset Lagrangen multipliers -vektorit. Dualiteetti liittyy primal- ja duaaliongelmiin tiiviisti, ja konveksisissa tapauksissa vahva dualiteetti voi toteutua, mikä helpottaa laskentaa.

Menetelmät ja käytännön ratkaisutavat vaihtelevat ongelmaluokasta riippuen. Gradienttinen menetelmä ja Newtonin menetelmä soveltuvat epälineaarisiin tapauksin; sisäiset pisteet ovat keskeisiä epälineaarisen ohjelmoinnin käytännön ratkaisuissa. Lineaarisessa ohjelmoinnissa yleisesti käytetty menetelmä on simplex, ja kokonaislukuohjelmoinnissa tavataan hakumenetelmiä kuten branch-and-bound.

Optimointiteoriaa sovelletaan laajasti taloudessa, logistiikassa, suunnittelussa, energiateollisuudessa ja koneoppimisessa. Historiaan kuuluvat muun muassa Lagrangen ja Kuhn–Tuckerin kehitykset sekä niiden vaikutus matemaattisen ohjelmoinnin kehittymiseen.