Optimoitumisalgoritmit

Optimoitumisalgoritmit ovat algoritmeja, joiden tehtävänä on löytää parhain mahdollinen ratkaisu optimoitavalle ongelmalle: maksimoida tai minimoida tavoitefunktio rajoitteiden puitteissa. Niitä käytetään sekä jatkuvissa että diskreeteissä ongelmissa, ja niiden tarkoitus vaihtelee tarkkojen ratkaisujen etsimisestä hyväksi vaikuttaviin likiarvoihin.

Algoritmit voidaan luokitella monin tavoin. Eksakti- ja epävarmoina: eksakti menetelmä voi usein taata optimaalisen ratkaisun tietyissä ongelmissa (esimerkiksi lineaarinen ohjelmointi, kokonaislaskenta), kun taas likimääräiset tai metaheuristiset menetelmät (esim. geneettiset algoritmit, simulated annealing, partikkelipilvet, ant colony) hakevat hyviä ratkaisuja usein monimutkaisissa tai ei-konveksisissa tehtävissä. Jatkuvat ongelmat eroavat diskreeteistä; konveksia ongelmia ratkaistaan usein tehokkaasti, kun taas epäkonveksit tai suuret hesto- ja kombinatoriikkaongelmat voivat olla erittäin haastavia.

Tyypillisiä menetelmiä ovat gradienttietojaiset menetelmät (gradient descent, Newtonin menetelmä), sekä konveksien ongelmien lineaarinen ohjelmointi (LP) ja epälineaarinen ohjelmointi (NLP, SDP). Diskreeteissä ongelmissa käytetään esimerkiksi branch-and-bound, dynamic programming tai heuristiikkoja. Rajoitteet voivat olla yhtälö- tai epäyhtälörajoitteita, ja ne määrittelevät ratkaisun syntysijan.

Käyttökohteita löytyy teollisuudesta, logistiikasta, tuotannosta, resurssienhallinnasta sekä koneoppimisesta hyperparametrien optimoinnista. Tutkimuskenttä kattaa sekä käytännön sovellukset että teoreettiset konvergenssi- ja kompleksisuuskysymykset.