Optimointimenetelmät

Optimointimenetelmät ovat algoritmeja, joiden tarkoituksena on löytää muuttujien joukosta sellainen arvo x, jolla tavoiteltu funktio f(x) saa parhaan mahdollisen arvon. Ongelma määritellään minimoinnin tai maksimoimisen tavoitteena sekä mahdollisilla rajoitteilla. Ratkaisussa etsitään x*, joka täyttää rajoitteet ja minimoi tai maksimoi f(x). Ongelman ominaisuudet, kuten differentiabiliteetti ja konveksisuus, vaikuttavat käytettäviin menetelmiin ja tulosten laatuun.

Luokittelun perusteella optimointi jaetaan ilman rajoitteita oleviin menetelmiin sekä rajoitettuihin optimointeihin. Ilman rajoitteita olevat menetelmät käsittelevät ongelmia, joissa muuttujat voivat olla vapaasti. Näihin kuuluvat gradienttipohjaiset menetelmät, kuten gradientti­pohjainen descent, sekä Newtonin menetelmä ja sen lähestymistavat (quasi-Newton, esim. BFGS, L-BFGS). Konjugoitujen gradienttien menetelmä on tehokas suurten dimensioiden ongelmissa. Derivaatittomat menetelmät, kuten Nelder–Mead -menetelmä ja pattern search, soveltuvat epäderivatiivisille kohteille.

Rajoitetuissa optimoinneissa ongelmaan sisältyy sallitut ehdot. Lineaarisessa ohjelmoinnissa käytetään usein simplex- tai interior-point -menetelmiä. Epälineaarisissa rajoitteissa puhutaan nonlinear programmingista (NLP); ratkaisut voivat nojata aktiivisen joukko -menetelmiin, interior-point -menetelmiin sekä rajoitteiden käsittelyyn penality-, barrier- tai augmented Lagrangian -menetelmin.

Globaalin optimoinnin tavoitteena on löytää koko ratkaisuavaruuden globaali optimi, ei vain paikallinen. Tälle käytetään metaheuristiikkoja (geenialgoritmit, simulated annealing, swarm-optimointi), sekä branch-and-bound- sekä Lipschitz-tyyppisiä hakumenetelmiä. Ongelman luonne ja vaadittu tarkkuus ohjaavat valintaa.