Optimizacija (matematika)

V matematiki se izraz optimizacija ali matematično programiranje nanaša na iskanje minimuma ali maksimuma dane realne funkcije na dovoljeni množici točk. Problem predstavimo na sledeči način:

Pri dani namenski funkciji f : A R iz množice A v realna števila
Iščemo takšen element x0 v A, da je f(x0) ≤ f(x) za vse x v A (minimizacija) ali da je f(x0) ≥ f(x) za vse x v A (maksimizacija).

Tako definiran problem imenujemo optimizacijski problem ali problem matematičnega programiranja. Zadnji pojem ni povezan z računalniškim programiranjem, vendar se še vedno pogosto uporablja v zvezah kot so linearno programiranje ali kvadratično programiranje.

Množica dopustnih rešitev A je tipično neka podmnožica evklidskega vektorskega prostora Rn, ki je določena z množico omejitev, ki jih predstavimo z enačbami ali neenačbami, ki jim morajo zadoščati elementi A. Funkcijo f imenujemo namenska ali ciljna funkcija.

Primer

uredi

Preprost optimizacijski problem lahko definiramo na naslednji način:

min f(x) = x12+x22

pri pogojih

x1 ≥ 1

in

x2 = 1

V prvi vrstici je definirana namenska funkcija f(x), ki jo minimiziramo. druga in tretja vrstica predstavljata omejitvi, ki določata množico dopustnih rešitev A. Druga vrstica predstavlja neeenakostno omejitev, tretja pa enakostno. Po dogovoru navadno omejitve pišemo tako, da je na eni strani enačaja ali neenačaja ničla:

c 1 (x) = 1-x1 ≤ 0

in

c 2 (x) = 1 - x2 = 0

Pri tem smo uvedli omejitveni funkciji c 1 in c 2. Različni avtorji uporabljajo različne dogovore o definiciji omejitvenih funkcij pri neenakostnih omejitvah glede na to, ali je omejitvena funkcija na dovoljenem območju manjša ali enaka 0 oziroma večja ali enaka 0.

Glavna področja

uredi

Metode reševanja

uredi

Pri dvakrat zvezno diferenciabilnih funkcijah lahko probleme brez omejitev (enostavna minimizacija ali maksimizacija) rešujemo z iskanjem stacionarnih točk, v katerih je gradient namenske funkcije nič. Pri tem uporabimo Hessovo matriko za dolo;itev tipa stacionarne točke. Če je Hessova matrika pozitivno definitna, je točka lokalni minimum, če je negativno definitna, je lokalni maksimum, če pa je nedefinitna, je to sedelna točka.

Obstoj odvodov ni vedno zagotovljen ali pa jih je težko izračunati (na primer, kadar je namenska funcija definirana preko rešitve zapletenega sistema diferencialnih enačb). Zato delimo metode reševanja optimizacijskih problemov na razrede glede na potrebno glaskost namenske in omejitvenih funkcij, ki so:

  • Kombinatorične metode
  • Metode brez uporabe odvodov
  • Metode prvega reda
  • Metode drugega reda

Spodaj je naštetih nekaj ožjih skupin metod:

Pri gradientnih metodah v glavnem uporabljamo dva osnovna pristopa reševanja optimizacijskih problemov (imenujemo ju tudi prototipna algoritma): minimizacija v dani smeri in minimizacija z omejenim korakom. Oba pristopa pogosto kombiniramo z metodo aktivne množice.

Probleme z omejitvami pogosto prevedemo na problem iskanja ekstremov funkcije brez omejitev s pomočjo Lagrangeevih množiteljev.

Glej tudi

uredi

Zunanje povezave

uredi
Modelski jeziki za optimizacijo
Programi za reševanje optimizacijskih problemov
Optimizacijske knjižnice