Minimointiongelmia

Minimointiongelmia ovat optimointiongelmia, joissa tavoitteena on löytää muuttujien arvo x, joka minimoi annettuun kustannus- tai energiafunktioon f(x) liittyvän arvon. Ratkaisu toteutetaan yleensä sallitulla alueella X, joka voi olla koko R^n tai jokin rajoitettu tai epälineaarisesti kuvattu alue. Minimointi voidaan tehdä sekä ilman rajoituksia että erilaisten yhtäläisyys- ja epäyhtäläisehtojen alaisena.

Perusmuoto on min f(x) x ∈ C, tai min f(x) s.t. g_i(x) ≤ 0 ja h_j(x) = 0, missä g_i ja h_j ovat epäyhtäläisiä ja yhtäläisiä rajoitteita. Unconstrained minimointi tarkoittaa tilannetta, jossa ei ole eksplisiittisiä rajoitteita, tai ne ovat piilotettuina kustannusfunktioon. Etsittäviä pisteitä kutsutaan minimoiksi: x* on paikallinen minimi, jos on pieni ympäristö x ympärillä and f(x) ≥ f(x*); globaali minimi on piste, jolla f(x) on pienin kaikkialla soveltuvalla alueella.

Oleellisessa roolissa ovat optimaalisuusehdot. Differenointisyydestä riippuen tarvitaan gradientin nolla-arvoa ja joskus Hessianin positiivista (semidefiniittii) jotta paikallinen minimi turvataan. Rajoitetuissa ongelmissa käytetään Lagrangen langin tai KKT-ehtoja, jotka yhdistävät kustannusfunktion ja rajoitteet.

Jos f on convex ja salliva alue C on convex, jokainen paikallinen minimum on globaali. Konveksisuus helpottaa ratkaisua ja mahdollistaa tehokkaat menetelmät, kuten gradienttini, Newtonin ja kvasi-Newtonin menetelmät, projektoivat gradient miehillä, sisärajamenetelmät tai dualisuuteen perustuvat menetelmät.

Esimerkkejä ovat yksinkertainen min f(x)=x^2, lineaarinen ohjelmointi min c^T x s.o. Ax=b, x≥0 sekä monimutkaisemmat epälineaariset minimoinnit koneoppimisessa ja taloustieteessä. Minimointiongelmien ratkaisuja käytetään laajasti insinööri- ja talousalalla sekä tietotekniikassa.