Többkritériumos optimalizálás

Többkritériumos optimalizálás (más néven többkritériumos programozás, angolul multi-objective optimization, multi-criteria optimization) — a matematikai optimalizálás azon területe, amely két vagy több, általában egymással konfliktusban álló célfüggvény (kritérium) egyidejű optimalizálásának feladatát vizsgálja. Formálisan a feladat egy vektoros célfüggvény minimalizálásaként írható fel a megengedett megoldások halmazán.

Definíció és terminológia

A többkritériumos optimalizálási feladat általános alakja a következő: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ ahol $S\subseteq {ℝ}^n$ a megengedett megoldások nemüres halmaza, $f_i:S\to ℝ$ pedig a célfüggvények ($k\ge 2$). A $f(x)=(f_1(x),\dots ,f_k(x))$ vektort célvektornak nevezzük.

Az egykritériumos optimalizálással ellentétben a többkritériumos felállásban általában nem létezik egyetlen olyan megoldás, amely egyszerre minden kritérium értékét javítja. Ezért az optimum klasszikus fogalmát a Pareto-optimalitás koncepciójával általánosítják.

• Pareto-megoldás (Pareto-optimális vagy hatékony megoldás): olyan megengedett $x^{\ast }\in S$ megoldás, amelyhez nem létezik olyan másik $x\in S$ megoldás, amelyre $f_i(x)\le f_i(x^{\ast })$ teljesül minden $i=1,\dots ,k$ esetén, és emellett $f_j(x)<f_j(x^{\ast })$ legalább egy $j$ indexre. Más szóval egy megoldás Pareto-optimális, ha egyetlen kritérium értéke sem javítható legalább egy másik kritérium értékének rontása nélkül.
• Pareto-front (vagy Pareto-halmaz): az összes Pareto-optimális megoldáshoz tartozó célvektor halmaza.
• Gyengén Pareto-optimális megoldás: olyan $x^{\ast }\in S$ megoldás, amelyhez nem létezik olyan másik $x\in S$ megoldás, amelyre $f_i(x)<f_i(x^{\ast })$ teljesül minden $i$ esetén.

Főbb tulajdonságok és tételek

• Súlyozott összeg tétele: Konvex feladatokban (ahol az összes $f_i(x)$ függvény és a $S$ halmaz konvex) minden Pareto-optimális $x^{\ast }$ megoldás megoldása a kritériumok $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ súlyozott összegét minimalizáló skaláris feladatnak valamely nemnegatív $w_i\ge 0$ súlykészlet mellett. Nemkonvex feladatokban azonban ez a módszer nem feltétlenül találja meg a Pareto-front egyes részeit.

• Karush–Kuhn–Tucker (KKT) optimalitási feltételek: A sima feladatokra vonatkozó szükséges optimalitási feltételek általánosíthatók a többkritériumos esetre. A Pareto-optimum pontjában létezik nemnegatív szorzók (súlyok) egy nullától különböző halmaza, amelyekre a célfüggvények és az aktív korlátok gradienseinek lineáris kombinációja nulla.

• A megoldáshalmaz tulajdonságai: A Pareto-front számos fontos minőségi jellemzővel rendelkezik. Határát az ideális pont (amelyet az összes kritérium elemenként vett minimumaiból alkotnak) és a nadírpont (a fronton elemenként vett maximumokból) határolja.

Példák

• Lineáris feladat: Minimalizálandó $f_1(x)=-x_1$ és $f_2(x)=-x_2$ a $x_1+x_2\le 1$, $x_1,x_2\ge 0$ korlátok mellett. Itt az egyik kritérium javítása (például $x_1$ növelése) szükségszerűen a másik rontásához vezet (a $x_2$ csökkenéséhez). A Pareto-optimális megoldások halmaza a $x_1+x_2=1$ egyenes egy szakasza.
• Nemkonvex feladat: Minimalizálandó $f_1(x)=x^2$ és $f_2(x)=(x-2{)}^2$ a $[0,2]$ szakaszon. A Pareto-front nemkonvex. A pozitív súlyokat alkalmazó súlyozott összeg módszer nem képes megtalálni a szakasz belső megoldásait (például a $x=1$ pontban), mivel a kritériumok lineáris kombinációja csak a $x=0$ vagy $x=2$ szélső pontokban veszi fel minimumát.

Kapcsolódó fogalmak és alkalmazások

A többkritériumos optimalizálás szorosan kapcsolódik a többkritériumos döntéshozatalhoz (MCDM), amely a döntéshozó preferenciáit figyelembe véve vizsgálja a legjobb alternatíva kiválasztását. A többkritériumos feladat skaláris feladattá alakításának (skalárizálásának) főbb módszerei:

• Súlyozott összeg módszer.
• $\epsilon$-korlát módszer: Egyetlen kritériumot optimalizálnak, a többit $f_i(x)\le {\epsilon }_i$ alakú korlátokká alakítják. Ez a módszer képes a front nemkonvex szakaszain lévő megoldásokat is megtalálni.

A többkritériumos optimalizálás széles körben alkalmazzák mérnöki tervezésben, közgazdaságtanban (például portfólióoptimalizálás), menedzsmentben és ökológiában.

Lásd még

• Pareto-optimalitás
• Vektoros optimalizálás
• Döntéselmélet
• Döntéstámogató rendszerek
• Operációkutatás