Frente de Pareto

En la optimización multiobjetivo , el frente de Pareto (también llamado frontera de Pareto o curva de Pareto ) es el conjunto de todas las soluciones eficientes de Pareto . ^{[ 1 ]} Coloquialmente, esto significa que cuando hay muchos objetivos distintos a considerar en un problema de optimización , un frente de Pareto representa el conjunto de soluciones donde ninguna solución supera a ninguna otra solución del conjunto en cada objetivo, y cada solución que no está en el conjunto es superada por al menos una solución del frente de Pareto en cada objetivo. ^{[ 2 ]} El concepto se utiliza ampliamente en ingeniería . ^{[ 3 ] : 111–148} Permite al diseñador restringir la atención al conjunto de opciones eficientes y realizar compensaciones dentro de este conjunto, en lugar de considerar todo el rango de cada parámetro. ^{[ 4 ] : 63–65 [ 5 ] : 399–412}

La frontera de Pareto, P ( Y ), puede describirse más formalmente de la siguiente manera. Consideremos un sistema con función${\displaystyle f:X\rightarrow \mathbb {R} ^{m}}$donde X es un conjunto compacto de decisiones factibles en el espacio métrico.${\displaystyle \mathbb {R} ^{n}}$y Y es el conjunto factible de vectores de criterios en${\displaystyle \mathbb {R} ^{m}}$, de tal manera que${\displaystyle Y=\{y\in \mathbb {R} ^{m}:\;y=f(x),x\in X\;\}}$.

Suponemos que se conocen las direcciones preferidas de los valores de los criterios. Un punto${\displaystyle y^{\prime \prime }\in \mathbb {R} ^{m}}$se prefiere a (domina estrictamente) otro punto${\displaystyle y^{\prime }\in \mathbb {R} ^{m}}$, escrito como${\displaystyle y^{\prime \prime }\succ y^{\prime }}$La frontera de Pareto se escribe, por lo tanto, como:

${\displaystyle P(Y)=\{y^{\prime }\in Y:\;\{y^{\prime \prime }\in Y:\;y^{\prime \prime }\succ y^{\prime },y^{\prime }\neq y^{\prime \prime }\;\}=\emptyset \}.}$

Un aspecto significativo de la frontera de Pareto en economía es que, en una asignación eficiente de Pareto, la tasa marginal de sustitución es la misma para todos los consumidores. ^{[ 6 ]} Se puede derivar una formulación formal considerando un sistema con m consumidores y n bienes, y una función de utilidad de cada consumidor como${\displaystyle z_{i}=f^{i}(x^{i})}$dónde${\displaystyle x^{i}=(x_{1}^{i},x_{2}^{i},\ldots ,x_{n}^{i})}$es el vector de bienes, tanto para todo i . La restricción de factibilidad es${\displaystyle \sum _{i=1}^{m}x_{j}^{i}=b_{j}}$para${\displaystyle j=1,\ldots ,n}$Para encontrar la asignación óptima de Pareto, maximizamos el lagrangiano :

${\displaystyle L_{i}((x_{j}^{k})_{k,j},(\lambda _{k})_{k},(\mu _{j})_{j})=f^{i}(x^{i})+\sum _{k=2}^{m}\lambda _{k}(z_{k}-f^{k}(x^{k}))+\sum _{j=1}^{n}\mu _{j}\left(b_{j}-\sum _{k=1}^{m}x_{j}^{k}\right)}$

dónde${\displaystyle (\lambda _ {k})_ {k}}$y${\displaystyle (\mu _ {j})_ {j}}$son los vectores de multiplicadores. Tomando la derivada parcial del lagrangiano con respecto a cada bien${\displaystyle x_{j}^{k}}$para${\displaystyle j=1,\ldots ,n}$y${\displaystyle k=1,\ldots ,m}$proporciona el siguiente sistema de condiciones de primer orden:

${\displaystyle {\frac {\partial L_{i}}{\partial x_{j}^{i}}}=f_{x_{j}^{i}}^{1}-\mu _{j}=0{\text{ para }}j=1,\ldots ,n,}$

${\displaystyle {\frac {\partial L_{i}}{\partial x_{j}^{k}}}=-\lambda _{k}f_{x_{j}^{k}}^{i}-\mu _{j}=0{\text{ para }}k=2,\ldots ,m{\text{ y }}j=1,\ldots ,n,}$

dónde${\displaystyle f_{x_{j}^{i}}}$denota la derivada parcial de${\displaystyle f}$con respecto a${\displaystyle x_{j}^{i}}$Ahora, arregla cualquier${\displaystyle k\neq i}$y${\displaystyle j,s\in \{1,\ldots ,n\}}$. La condición de primer orden anterior implica que

${\displaystyle {\frac {f_{x_{j}^{i}}^{i}}{f_{x_{s}^{i}}^{i}}}={\frac {\mu _{j}}{\mu _{s}}}={\frac {f_{x_{j}^{k}}^{k}}{f_{x_{s}^{k}}^{k}}}.}$

Por lo tanto, en una asignación óptima de Pareto, la tasa marginal de sustitución debe ser la misma para todos los consumidores. ^{[ 7 ]}

En informática e ingeniería eléctrica se han estudiado algoritmos para calcular la frontera de Pareto de un conjunto finito de alternativas. ^{[ 8 ]} Estos incluyen:

• "Los máximos de un conjunto de puntos "
• "El problema del vector máximo" o la consulta skyline ^{[ 9 ] [ 10 ] [ 11 ]}
• "El algoritmo de escalarización" o el método de sumas ponderadas ^{[ 12 ] [ 13 ]}
• "El${\displaystyle \epsilon }$-método de restricciones" ^{[ 14 ] [ 15 ] [ 16 ]}
• Algoritmos evolutivos multiobjetivo ^{[ 17 ] [ 18 ]}

Dado que generar el frente de Pareto completo suele ser computacionalmente difícil, existen algoritmos para calcular un frente de Pareto aproximado. Por ejemplo, Legriel et al. ^{[ 19 ]} denominan a un conjunto S una ε -aproximación del frente de Pareto P si la distancia de Hausdorff dirigida entre S y P es como máximo ε . Observan que se puede encontrar una ε -aproximación de cualquier frente de Pareto P en d dimensiones utilizando (1/ ε ) ^d consultas.

Zitzler, Knowles y Thiele ^{[ 20 ]} comparan varios algoritmos para aproximaciones de conjuntos de Pareto en varios criterios, como la invariancia a la escala, la monotonicidad y la complejidad computacional.