Minimointiongelmat

Minimointiongelmat ovat optimoinnin osa-alue, jossa tavoitteena on löytää päätösvektori x, joka minimoi tavoitefunktion f(x) määrittelyjoukon X sisällä. X määritellään usein rajoitteiden avulla, kuten epäyhtälöillä, yhtälöillä sekä arvoalueilla (esimerkiksi x ≥ 0). Tavoitefktio voi kuvata kustannuksia, energian tarvetta, riskiä tai muuta mittaria, jota halutaan pienentää.

Tyypit ja peruskäsitteet. Epärajoittamaton minimointiongelma etsii x ∈ R^n, jolla f(x) on pienin ilman muita ehtoja. Rajoitettu minimointiongelma rajoittaa x:n joukkoon X, joka määritellään esimerkiksi lineaarisilla tai epälineaarisilla rajoitteilla. Lineaarisessa ohjelmoinnissa sekä f että rajoitteet ovat lineaarisia. Konveksisissa minimointiongelmissa f on konveksi funktio ja X on konveksi joukko, jolloin paikallinen minimi on usein globaali.

Menetelmät. Analyyttinen ratkaisu soveltuu pienille tai erityisen rakennetuille ongelmille. Numeeriset menetelmät ovat yleisiä: gradienttijohteiset menetelmät (gradient descent ja sen kehitteet), Newtonin ja quasi-Newtonin menetelmät sekä konveksissa ongelmissa sisärajaiset menetelmät (interior-point) ja aktiivisuusmenetelmät. Rajoitteiden säilyttämiseksi käytetään Lagrangen menetelmää ja KKT-ehtoja. Monimutkaisissa tai epälineaarisissa ja/tai combinatorisissa ongelmissa turvaudutaan heuristiikoihin, like branch-and-bound jne.

Sovellukset. Minimointiongelmia sovelletaan taloudessa, tuotannossa, logistiikassa, energiatehokkuudessa sekä koneoppimisessa ja tilastollisessa estimoinnissa. Niiden avulla optimoidaan kustannukset, resurssien käyttö ja suorituskyky eri järjestelmissä.