optimointialgoritmeja

Optimointialgoritmeja ovat menetelmät, joiden tehtävänä on löytää tavoitefunktion minimi tai maksimi annetun ongelman ehdoilla. Niitä käytetään laajasti esimerkiksi koneoppimisessa, suunnittelussa, resurssienhallinnassa ja taloudellisissa optimointitehtävissä. Tavoitefunktio voi kuvata kustannuksia, hyötyä tai virheen suuruutta, ja ehtoja voivat olla muuttujien sallitut arvot, epämuodolliset rajoitteet tai monimutkaisemmat tilarajoitteet.

Ongelmat voidaan luokitella monin tavoin. Yleisesti erotetaan jatkuvat ja diskreetit ongelmat sekä rajoitetut ja rajoittamattomat ongelmat. Lisäksi on erillisiä ryhmiä deterministiset vs. stokastiset menetelmät sekä tarkkoihin ratkaisuihin tähtäävät algoritmit ja likimääräiset/perusteettomat lähestymistavat. Koneteknisissä ja suurissa ongelmissa korostuvat usein sekä laskennalliset kustannukset että konvergenssivaatimukset.

Kantavana kategoriana ovat gradienttipohjaiset menetelmät ja niiden variaatiot. Unconstrained- eli rajoittamattomissa ongelmissa käytetään esimerkiksi gradienttihatkaa, Newtonin menetelmää sekä kvasi-Newton- menetelmiä kuten BFGS, sekä konjugoitua gradienttia. Rajoitettuihin ongelmiin sovelletaan esimerkiksi Lagrangen menetelmiä sekä menetelmiä kuten sequential quadratic programming (SQP) sekä sisärajamenetelmiä (interior-point).

Derivaatittomia ja stokastisia lähestymistapoja ovat Nelder–Mead -menetelmä, kuviohaku (pattern search), geneettiset algoritmit, simuloitu annealing sekäpartiikelasumennus (particle swarm optimization). Globaalin optimoinnin työkaluja ovat Bayesian-optimointi ja muut tilastolliset menetelmät, jotka hyödyntävät mallinnettuja todennäköisyyksiä.

Valinta optimointialgoritmille riippuu ongelman luonteesta, kuten konveksisuudesta, epälineaarisuudesta, häiriöistä ja tarvittavasta tarkkuudesta.