Optimizacija (matematika)

Za druge pomene glej Optimizacija.

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 $\to$ R iz množice A v realna števila

Iščemo takšen element x₀ v A, da je f(x₀) ≤ f(x) za vse x v A (minimizacija) ali da je f(x₀) ≥ 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 Rⁿ, 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

Preprost optimizacijski problem lahko definiramo na naslednji način:

min f(x) = x₁²+x₂²

pri pogojih

x₁ ≥ 1

in

x₂ = 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 ₁ (x) = 1-x₁ ≤ 0

in

c ₂ (x) = 1 - x₂ = 0

Pri tem smo uvedli omejitveni funkciji c ₁ in c ₂. 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

• Linearno programiranje se ukvarja s problemi, kjer je namenska funkcija f linearna, dovoljeno območje A pa je določeno le z linearnimi enačbami in neenačbami.
• Celo programiranje se ukvarja z linearnimi programi, kjer lahko nekatere ali vse spremenljivke zavzamejo le cele vrednosti.
• Kvadratično programiranje - namenska funkcija lahko vsebuje kvadratne člene, območje A pa je določeno le z linearnimi enačbami in neenačbami.
• Nelinearno programiranje - splošen primer, ko namenska funkcija ali omejitve ali oboji vsebujejo nelinearne člene.
• Konveksno programiranje - namenska funkcija je konveksna, prav tako dovoljeno območje.
• Semidefinitno programiranje je podpodročje konveksne optimizacije, jer so spremenljivke semidefinitne matrike
• Stohastično programiranje se ukvarja s primeri, kjer so nekatere od omejitev ali parametrov odvisne od naključnih spremenljivk.
• Robustno programiranje - pri tem podobno kot pri stohastičnem programiranju poskušamo zajeti negotovost v podatkih, na katerih temelji optimizacijski problem.
• Dinamično programiranje se ukvarja z reševanjem problemov, kjer strategija reševanja temelji na razcepu na manjše podprobleme.
• Kombinatorična optimizacija se ukvarja s problemi, kjer je množica dovoljenih rešitev diskretna.
• Neskončno dimenzionalna optimizacija se ukvarja s problemi, kjer je množica dovoljenih rešitev podmnožica nesknočnodimenzionalnega prostora (na primer prostora funkcij).
• Zadovoljitev omejitev se ukvarja s problemi, kjer je namenska funkcija f konstantna.

Metode reševanja

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:

• Metoda najstrmejšega sestopa (oz. dvigovanja pri maksimizaciji)
• Nelder-Meadova metoda ali nelinearna simpleksna metoda
• Simpleksna metoda za linearno programiranje
• Newtonova metoda
• Kvazi-Newtonova metoda
• Metode notranje točke
• Metoda konjugiranih gradientov
• Metoda konjugiranih smeri - ekvivalent metodi knjugiranih gradientov v primeru, ko nimamo na voljo odvdov funkcije
• Metoda aktivne množice
• Zaporedno kvadratično programiranje
• Metoda zaporednih aproksimacij
• Evolucijske metode, na primer genetski algoritmi
• Stohastično tuneliranje
• Metoda jate delcev
• Diferencialna evolucija
• Optimizacija s kolonijo mravelj

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

• arg min
• operacijske raziskave
• variacijski račun
• optimizacijske metode
• optimizacijski programi
• IOptLib
• Inverse
• brahistokrona

Zunanje povezave

• NEOS Guide (vodič po programju za optimizacijo) Arhivirano 2002-08-22 na Wayback Machine.
• Mathematical Programming Society
• Optimization FAQ Arhivirano 2012-04-18 na Wayback Machine. - pogosta vprašanja s področja optimizacije
• Mathematical optimization Arhivirano 2008-12-20 na Wayback Machine.
• Optimization online - povezave in članki s področja optimizacije
• Uporabne povezave s področja optimizacije

Modelski jeziki za optimizacijo

• GAMS — General Algebraic Modeling System
• AMPL
• MPL
• Inverse

Programi za reševanje optimizacijskih problemov

• CPLEX
• Mosek
• SAS OR Arhivirano 2008-12-06 na Wayback Machine.
• CONOPT
• Xpress-MP - Optimizacijski program, ki je prost za študente
• IPOPT Arhivirano 2006-10-09 na Wayback Machine. - metoda notranje točke za reševanje problemov nelinearnega programiranja, odprta koda.
• Free Optimization Software by Systems Optimization Laboratory, Stanford University

Optimizacijske knjižnice

• OOL (Open Optimization library) - zbirka optimizacijskih rutin v jeziku C.
• IOptLib (Investigative Optimization Library) - knjižica za razvoj optimizacijskih algoritmov (ANSI C, odprta koda).