Optimointialgoritmi

Optimointialgoritmi on algoritmi, jolla pyritään löytämään paras mahdollinen ratkaisu annetulle ongelmalle. Tavoitteena on minimoida tai maksimoida tavoitefunktio f(x) ja löytää kelvollinen ratkaisu x sallitun tilan S sisällä. Ongelmat voivat olla jatkuvia tai diskreettejä, lineaarisia tai epälineaarisia, ja niihin liittyy usein rajoitteita tai ehtoja.

Optimointialgoritmeja voidaan luokitella useilla tavoilla. Eksaktiin ratkaisuun pyrkivät menetelmät yrittävät taata optimaalisen ratkaisun, kun taas heuristiset menetelmät hakevat hyvää ratkaisua ilman takausta pareimmuuden todistamisesta. Lisäksi on ero lokalien ja globaalioptimoinnin välillä: lokaali optimointi löytää usein vain paikallisen, kun taas globaali etsii parasta mahdollista ratkaisua koko sovellusalalle. Ongelman ominaisuuksien mukaan erotetaan jatkuvat, diskreetit sekä konveksit ja ei-konveksit ongelmat.

Yleisimmät menetelmät jaetaan usein seuraavasti. Gradienttipohjaiset menetelmät, kuten gradienttien laskeutuminen ja Newtonin menetelmä, soveltuvat differentiable-ongelmiin. Konveksissa ongelmissa on erityisen tehokkaita ohjelmointimuotoja, kuten lineaarinen ohjelmointi, kvadratiopohjainen ohjelmointi ja semidefinite-ohjelmointi. Epälineaarisille ja ei-differioitaaville ongelmille käytetään derivaatittomia menetelmiä sekä metaheuristiikkoja, kuten Nelder–Mead -algoritmia, pattern searchia ja satunnaishakuja sekä geneettisiä algoritmeja ja hiukkasjoukko-optimointia.

Rajoitteiden käsittelyyn käytetään usein Lagrangen kertoimia, rangaistuksin tai este-, tilastoinnin ja sisäisten rajoitteiden menetelmiä. Onnistuneeseen optimointiin vaikuttavat myös konvergensi- ja luottamusmittarit sekä laskentateho ja toistettavuus. Optimointialgoritmeja sovelletaan laajasti suunnittelussa, resurssien kohdentamisessa, reitityksessä, tuotannossa, taloustieteissä ja koneoppimisessa hyperparametrien säätämisessä.