Multikriteriell optimering

Multikriteriell optimering (även multikriteriell programmering, eng. multi-objective optimization, multi-criteria optimization) — är en gren av matematisk optimering som studerar problem med simultan optimering av två eller flera målfunktioner (kriterier), vilka i regel står i konflikt med varandra. Formellt formuleras problemet som minimering av en vektoriell målfunktion på mängden av tillåtna lösningar.

Definition och terminologi

Problemet med multikriteriell optimering skrivs i allmän form på följande sätt: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ där $S\subseteq {\mathbb{ℝ}}^n$ är en icke-tom mängd av tillåtna lösningar, och $f_i:S\to \mathbb{ℝ}$ är målfunktionerna ($k\ge 2$). Vektorn $f(x)=(f_1(x),\dots ,f_k(x))$ kallas målvektor.

Till skillnad från skalär optimering finns det i en multikriteriell formulering vanligtvis ingen enskild lösning som förbättrar värdena för alla kriterier samtidigt. Därför generaliseras det klassiska begreppet optimum med hjälp av konceptet Pareto-optimalitet.

• Pareto-lösning (Pareto-optimal eller effektiv lösning): en tillåten lösning $x^{*}\in S$ för vilken det inte finns någon annan lösning $x\in S$ sådan att $f_i(x)\le f_i(x^{*})$ för alla $i=1,\dots ,k$, och samtidigt $f_j(x)<f_j(x^{*})$ för åtminstone ett index $j$. Med andra ord är en lösning Pareto-optimal om inget kriterievärde kan förbättras utan att försämra minst ett annat kriterium.
• Pareto-front (eller Pareto-mängd): mängden av alla målvektorer som motsvarar Pareto-optimala lösningar.
• Svagt Pareto-optimal lösning: en lösning $x^{*}\in S$ för vilken det inte finns någon annan lösning $x\in S$ sådan att $f_i(x)<f_i(x^{*})$ för alla $i$.

Viktiga egenskaper och satser

• Sats om viktad summa: I konvexa problem (där alla funktioner $f_i(x)$ och mängden $S$ är konvexa) är varje Pareto-optimal lösning $x^{*}$ en lösning till det skalära minimeringsproblemet med viktad summa av kriterier $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ för någon uppsättning icke-negativa vikter $w_i\ge 0$. I icke-konvexa problem kan denna metod dock misslyckas med att hitta vissa delar av Pareto-fronten.

• Karush-Kuhn-Tucker (KKT) optimalitetsvillkor: De nödvändiga optimalitetsvillkoren för glatta problem generaliseras till det multikriteriella fallet. I en Pareto-optimal punkt finns det en icke-noll uppsättning icke-negativa multiplikatorer (vikter) för vilka gradienterna av målfunktionerna och de aktiva bivillkoren är linjärt beroende.

• Egenskaper hos lösningens mängd: Pareto-fronten besitter ett antal viktiga kvalitativa egenskaper. Dess gräns begränsas av idealpunkten (sammansatt av elementvisa minima för alla kriterier) och nadirpunkten (av elementvisa maxima på fronten).

Exempel

• Linjärt problem: Minimera $f_1(x)=-x_1$ och $f_2(x)=-x_2$ med bivillkoret $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Här leder förbättring av ett kriterium (t.ex. ökning av $x_1$) oundvikligen till försämring av ett annat (minskning av $x_2$). Mängden av Pareto-optimala lösningar är ett linjesegment $x_1+x_2=1$.
• Icke-konvext problem: Minimera $f_1(x)=x^2$ och $f_2(x)=(x-2{)}^2$ på intervallet $[0,2]$. Pareto-fronten är icke-konvex. Metoden med viktade summor med positiva vikter kan inte hitta lösningar inuti detta intervall (t.ex. i punkten $x=1$), eftersom linjärkombinationen av kriterier uppnår sitt minimum endast i ändpunkterna $x=0$ eller $x=2$.

Relaterade begrepp och tillämpningar

Multikriteriell optimering är nära besläktad med multikriteriellt beslutsfattande (MCDM), som studerar valet av det bästa alternativet med hänsyn till beslutsfattarens preferenser. De viktigaste metoderna för att omvandla ett multikriteriellet problem till ett skalärt (skalering) inkluderar:

• Metoden med viktad summa.
• Metoden med $\epsilon$-begränsningar: Ett kriterium optimeras medan övriga omvandlas till bivillkor av typen $f_i(x)\le {\epsilon }_i$. Denna metod kan hitta lösningar på icke-konvexa delar av fronten.

Multikriteriell optimering har bred tillämpning inom teknisk konstruktion, ekonomi (t.ex. portföljoptimering), förvaltning och miljövård.

Se även

• Pareto-optimalitet
• Vektoroptimering
• Beslutsteori
• Beslutsstödssystem
• Operationsanalys