Ottimizzazione multicriterio

Ottimizzazione multicriterio (anche programmazione multicriterio, ingl. multi-objective optimization, multi-criteria optimization) — è una branca dell'ottimizzazione matematica che studia i problemi di ottimizzazione simultanea rispetto a due o più funzioni obiettivo (criteri), che, di norma, sono in conflitto tra loro. Formalmente il problema è formulato come minimizzazione di una funzione obiettivo vettoriale sull'insieme delle soluzioni ammissibili.

Definizione e terminologia

Il problema di ottimizzazione multicriterio nella forma generale è scritto come segue: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ dove $S\subseteq {ℝ}^n$ — è un insieme non vuoto di soluzioni ammissibili, e $f_i:S\to ℝ$ — sono le funzioni obiettivo ($k\ge 2$). Il vettore $f(x)=(f_1(x),\dots ,f_k(x))$ è detto vettore obiettivo.

A differenza dell'ottimizzazione scalare, nella formulazione multicriterio di norma non esiste un'unica soluzione che migliori simultaneamente i valori di tutti i criteri. Pertanto, il classico concetto di ottimo viene generalizzato mediante il concetto di ottimalità di Pareto.

• Soluzione di Pareto (soluzione Pareto-ottimale o efficiente): una soluzione ammissibile $x^{\ast }\in S$, per la quale non esiste un'altra soluzione $x\in S$ tale che $f_i(x)\le f_i(x^{\ast })$ per tutti $i=1,\dots ,k$, e inoltre $f_j(x)<f_j(x^{\ast })$ per almeno un indice $j$. In altre parole, una soluzione è Pareto-ottimale se nessun valore di criterio può essere migliorato senza peggiorare almeno un altro criterio.
• Fronte di Pareto (o insieme di Pareto): l'insieme di tutti i vettori obiettivo corrispondenti alle soluzioni Pareto-ottimali.
• Soluzione debolmente Pareto-ottimale: una soluzione $x^{\ast }\in S$, per la quale non esiste un'altra soluzione $x\in S$ tale che $f_i(x)<f_i(x^{\ast })$ per tutti $i$.

Proprietà chiave e teoremi

• Teorema della somma pesata: Nei problemi convessi (dove tutte le funzioni $f_i(x)$ e l'insieme $S$ sono convessi) qualsiasi soluzione Pareto-ottimale $x^{\ast }$ è soluzione del problema scalare di minimizzazione della somma pesata dei criteri $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ per un certo insieme di pesi non negativi $w_i\ge 0$. Tuttavia, nei problemi non convessi questo metodo potrebbe non trovare alcune parti del fronte di Pareto.

• Condizioni di ottimalità di Karush-Kuhn-Tucker (KKT): Le condizioni necessarie di ottimalità per problemi regolari sono generalizzate al caso multicriterio. In un punto di ottimo di Pareto esiste un insieme non nullo di moltiplicatori (pesi) non negativi per i quali i gradienti delle funzioni obiettivo e dei vincoli attivi sono linearmente dipendenti.

• Proprietà dell'insieme delle soluzioni: Il fronte di Pareto possiede una serie di importanti caratteristiche qualitative. Il suo confine è delimitato dal punto ideale (composto dai minimi elemento per elemento di tutti i criteri) e dal punto nadir (composto dai massimi elemento per elemento sul fronte).

Esempi

• Problema lineare: Minimizzare $f_1(x)=-x_1$ e $f_2(x)=-x_2$ con il vincolo $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Qui il miglioramento di un criterio (ad esempio, l'aumento di $x_1$) porta inevitabilmente al peggioramento dell'altro (riduzione di $x_2$). L'insieme delle soluzioni Pareto-ottimali è il segmento di retta $x_1+x_2=1$.
• Problema non convesso: Minimizzare $f_1(x)=x^2$ e $f_2(x)=(x-2{)}^2$ sul segmento $[0,2]$. Il fronte di Pareto è non convesso. Il metodo delle somme pesate con pesi positivi non riesce a trovare soluzioni all'interno di questo segmento (ad esempio, nel punto $x=1$), poiché la combinazione lineare dei criteri raggiunge il minimo solo nei punti estremi $x=0$ o $x=2$.

Concetti correlati e applicazioni

L'ottimizzazione multicriterio è strettamente legata al processo decisionale multicriterio (MCDM), che studia la scelta della migliore alternativa tenendo conto delle preferenze del decisore. I principali metodi di trasformazione del problema multicriterio in uno scalare (scalarizzazione) includono:

• Metodo della somma pesata.
• Metodo dei vincoli $\epsilon$: Si ottimizza un criterio, mentre gli altri vengono trasformati in vincoli della forma $f_i(x)\le {\epsilon }_i$. Questo metodo è in grado di trovare soluzioni nelle parti non convesse del fronte.

L'ottimizzazione multicriterio trova ampia applicazione nella progettazione ingegneristica, nell'economia (ad esempio, ottimizzazione del portafoglio), nella gestione e nell'ecologia.

Vedi anche

• Ottimalità di Pareto
• Ottimizzazione vettoriale
• Teoria delle decisioni
• Sistemi di supporto alle decisioni
• Ricerca operativa