Optimización multiobjetivo

La optimización multiobjetivo (también programación multicriterio, en inglés multi-objective optimization, multi-criteria optimization) es una rama de la optimización matemática que estudia problemas de optimización simultánea de dos o más funciones objetivo (criterios), que, por lo general, entran en conflicto entre sí. Formalmente, el problema se escribe como la minimización de una función objetivo vectorial sobre un conjunto de soluciones factibles.

Definición y terminología

Un problema de optimización multiobjetivo en su forma general se escribe de la siguiente manera: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ donde $S\subseteq {\mathbb{ℝ}}^n$ es un conjunto no vacío de soluciones factibles, y $f_i:S\to \mathbb{ℝ}$ son las funciones objetivo ($k\ge 2$). El vector $f(x)=(f_1(x),\dots ,f_k(x))$ se denomina vector objetivo.

A diferencia de la optimización escalar, en la formulación multiobjetivo generalmente no existe una única solución que mejore simultáneamente los valores de todos los criterios. Por lo tanto, el concepto clásico de óptimo se generaliza utilizando el concepto de optimalidad de Pareto.

• Solución de Pareto (solución Pareto-óptima o eficiente): una solución factible $x^{*}\in S$ para la cual no existe otra solución $x\in S$ tal que $f_i(x)\le f_i(x^{*})$ para todo $i=1,\dots ,k$, y $f_j(x)<f_j(x^{*})$ para al menos un índice $j$. En otras palabras, una solución es Pareto-óptima si no es posible mejorar el valor de un criterio sin empeorar al menos otro criterio.
• Frente de Pareto (o conjunto de Pareto): el conjunto de todos los vectores objetivo correspondientes a las soluciones Pareto-óptimas.
• Solución débilmente Pareto-óptima: una solución $x^{*}\in S$ para la cual no existe otra solución $x\in S$ tal que $f_i(x)<f_i(x^{*})$ para todo $i$.

Propiedades y teoremas clave

• Teorema de la suma ponderada: En problemas convexos (donde todas las funciones $f_i(x)$ y el conjunto $S$ son convexos), cualquier solución Pareto-óptima $x^{*}$ es una solución del problema escalar de minimización de la suma ponderada de los criterios $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ para algún conjunto de pesos no negativos $w_i\ge 0$. Sin embargo, en problemas no convexos, este método puede no encontrar algunas partes del frente de Pareto.

• Condiciones de optimalidad de Karush-Kuhn-Tucker (KKT): Las condiciones necesarias de optimalidad para problemas suaves se generalizan al caso multiobjetivo. En un punto Pareto-óptimo, existe un conjunto no nulo de multiplicadores no negativos (pesos) para los cuales los gradientes de las funciones objetivo y las restricciones activas son linealmente dependientes.

• Propiedades del conjunto de soluciones: El frente de Pareto posee una serie de características cualitativas importantes. Su frontera está limitada por el punto ideal (compuesto por los mínimos de cada criterio individual) y el punto nadir (compuesto por los máximos de cada criterio en el frente).

Ejemplos

• Problema lineal: Minimizar $f_1(x)=-x_1$ y $f_2(x)=-x_2$ sujeto a la restricción $x_1+x_2\le 1$, con $x_1,x_2\ge 0$. En este caso, la mejora de un criterio (por ejemplo, aumentar $x_1$) conduce inevitablemente al empeoramiento del otro (disminuir $x_2$). El conjunto de soluciones Pareto-óptimas es el segmento de la recta $x_1+x_2=1$.
• Problema no convexo: Minimizar $f_1(x)=x^2$ y $f_2(x)=(x-2{)}^2$ en el intervalo $[0,2]$. El frente de Pareto es no convexo. El método de la suma ponderada con pesos positivos no podrá encontrar soluciones dentro de este intervalo (por ejemplo, en el punto $x=1$), ya que la combinación lineal de los criterios alcanzará su mínimo solo en los puntos extremos $x=0$ o $x=2$.

Conceptos relacionados y aplicaciones

La optimización multiobjetivo está estrechamente relacionada con la toma de decisiones multicriterio (MCDM), que estudia la selección de la mejor alternativa teniendo en cuenta las preferencias de quien toma la decisión. Los principales métodos para transformar un problema multiobjetivo en uno escalar (escalarización) incluyen:

• Método de la suma ponderada.
• Método de las $\epsilon$-restricciones: Se optimiza un criterio, mientras que los demás se convierten en restricciones de la forma $f_i(x)\le {\epsilon }_i$. Este método es capaz de encontrar soluciones en partes no convexas del frente.

La optimización multiobjetivo tiene una amplia aplicación en el diseño de ingeniería, la economía (por ejemplo, la optimización de carteras de inversión), la gestión y la ecología.

Véase también

• Optimalidad de Pareto
• Optimización vectorial
• Teoría de la decisión
• Sistemas de soporte a la decisión
• Investigación de operaciones