Meerkriteria-optimalisatie

Meerkriteria-optimalisatie (ook wel meerkriteria-programmering, Engels: multi-objective optimization, multi-criteria optimization) — is een deelgebied van de wiskundige optimalisatie dat vraagstukken bestudeert waarbij tegelijkertijd wordt geoptimaliseerd naar twee of meer doelfuncties (criteria) die doorgaans met elkaar in conflict zijn. Formeel wordt het probleem genoteerd als de minimalisatie van een vectoriële doelfunctie op de verzameling van toelaatbare oplossingen.

Definitie en terminologie

Het meerkriteria-optimalisatieprobleem wordt in algemene vorm als volgt genoteerd: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ waar $S\subseteq {ℝ}^n$ — een niet-lege verzameling van toelaatbare oplossingen is, en $f_i:S\to ℝ$ — de doelfuncties zijn ($k\ge 2$). De vector $f(x)=(f_1(x),\dots ,f_k(x))$ wordt de doelvector genoemd.

In tegenstelling tot scalaire optimalisatie bestaat er bij een meerkriteria-formulering doorgaans geen unieke oplossing die de waarden van alle criteria tegelijkertijd verbetert. Daarom wordt het klassieke optimaliteitsbegrip gegeneraliseerd met behulp van het concept van Pareto-optimaliteit.

• Pareto-oplossing (Pareto-optimale of efficiënte oplossing): een toelaatbare oplossing $x^{\ast }\in S$ waarvoor geen andere oplossing $x\in S$ bestaat zodanig dat $f_i(x)\le f_i(x^{\ast })$ voor alle $i=1,\dots ,k$, en waarbij $f_j(x)<f_j(x^{\ast })$ voor ten minste één index $j$. Met andere woorden: een oplossing is Pareto-optimaal als geen enkel criterium kan worden verbeterd zonder ten minste één ander criterium te verslechteren.
• Pareto-front (of Pareto-verzameling): de verzameling van alle doelvectoren die overeenkomen met Pareto-optimale oplossingen.
• Zwak Pareto-optimale oplossing: een oplossing $x^{\ast }\in S$ waarvoor geen andere oplossing $x\in S$ bestaat zodanig dat $f_i(x)<f_i(x^{\ast })$ voor alle $i$.

Belangrijkste eigenschappen en stellingen

• Stelling over de gewogen som: In convexe problemen (waarbij alle functies $f_i(x)$ en de verzameling $S$ convex zijn) is elke Pareto-optimale oplossing $x^{\ast }$ een oplossing van het scalaire minimalisatieprobleem van de gewogen som van de criteria $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ voor een bepaalde verzameling niet-negatieve gewichten $w_i\ge 0$. Bij niet-convexe problemen kan deze methode echter bepaalde delen van het Pareto-front niet vinden.

• Karush-Kuhn-Tucker (KKT) optimaliteitsvoorwaarden: De noodzakelijke optimaliteitsvoorwaarden voor gladde problemen worden uitgebreid naar het meerkriteria-geval. In een Pareto-optimaal punt bestaat er een niet-nulverzameling van niet-negatieve multiplicatoren (gewichten) waarvoor de gradiënten van de doelfuncties en de actieve beperkingen lineair afhankelijk zijn.

• Eigenschappen van de oplossingsverzameling: Het Pareto-front bezit een aantal belangrijke kwalitatieve kenmerken. De grens ervan wordt bepaald door het ideale punt (samengesteld uit de elementgewijze minima van alle criteria) en het nadirpunt (samengesteld uit de elementgewijze maxima op het front).

Voorbeelden

• Lineair probleem: Minimaliseer $f_1(x)=-x_1$ en $f_2(x)=-x_2$ onder de beperking $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Hier leidt verbetering van het ene criterium (bijvoorbeeld verhoging van $x_1$) onvermijdelijk tot verslechtering van het andere (verlaging van $x_2$). De verzameling van Pareto-optimale oplossingen is een lijnstuk $x_1+x_2=1$.
• Niet-convex probleem: Minimaliseer $f_1(x)=x^2$ en $f_2(x)=(x-2{)}^2$ op het interval $[0,2]$. Het Pareto-front is niet-convex. De methode van gewogen sommen met positieve gewichten kan geen oplossingen vinden in het binnenste van dit interval (bijvoorbeeld in het punt $x=1$), omdat de lineaire combinatie van de criteria alleen in de eindpunten $x=0$ of $x=2$ een minimum bereikt.

Verwante begrippen en toepassingen

Meerkriteria-optimalisatie is nauw verwant aan meerkriteria-besluitvorming (MCDM), dat de keuze van het beste alternatief bestudeert rekening houdend met de voorkeuren van de beslisser. De belangrijkste methoden om een meerkriteria-probleem om te zetten in een scalair probleem (scalarisatie) zijn:

• Methode van gewogen sommen.
• Methode van $\epsilon$-beperkingen: Eén criterium wordt geoptimaliseerd, terwijl de overige worden omgezet in beperkingen van de vorm $f_i(x)\le {\epsilon }_i$. Deze methode is in staat oplossingen te vinden op niet-convexe delen van het front.

Meerkriteria-optimalisatie vindt brede toepassing in technisch ontwerp, economie (bijvoorbeeld portefeuilleoptimalisatie), management en milieukunde.

Zie ook

• Pareto-optimaliteit
• Vectoroptimalisatie
• Beslissingstheorie
• Beslissingsondersteunende systemen
• Operationeel onderzoek