Optimización lexicográfica de máximos y mínimos

El algoritmo de saturación funciona cuando el conjunto factible es un conjunto convexo y los objetivos son funciones cóncavas . Variantes de este algoritmo aparecen en muchos artículos. La primera aparición se atribuye a Alexander Kopelowitz ^{[ 1 ]} por Elkind y Pasechnik. ^{[ 6 ]} Otras variantes aparecen en. ^{[ 7 ] : 20–27 [ 8 ] [ 9 ] [ 5 ] : Alg.2 [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]}

El algoritmo mantiene un conjunto de objetivos que se consideran saturados (también llamados bloqueantes ). Esto significa que su valor no puede mejorarse sin perjudicar a los objetivos de menor valor. Los demás objetivos se denominan libres . Inicialmente, todos los objetivos son libres. En general, el algoritmo funciona de la siguiente manera:

• Si bien algunos objetivos son gratuitos:
  • (P1) Resuelva el siguiente problema de un solo objetivo, donde${\displaystyle z_{k}}$es el valor de saturación del objetivo${\displaystyle f_{k}}$:$${\displaystyle {\begin{aligned}\max ~~~z\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)=z_{k}{\text{ for all saturated objectives }}k,\\&f_{k}(x)\geq z{\text{ for all free objectives }}k\end{aligned}}}$$
  • Si el problema es inviable o no tiene límites, deténgase y declare que no existe solución.
  • De lo contrario, deja${\displaystyle z_{\max }}$sea ​​el valor máximo del primer problema.
  • Busca objetivos gratuitos cuyo valor no pueda aumentar más allá de${\displaystyle z_{\max }}$sin disminuir algún otro objetivo a continuación${\displaystyle z_{\max }}$En cualquier solución lexmaxmin, el valor de cualquier objetivo de este tipo debe ser exactamente${\displaystyle z_{\max }}$. Agregue todos esos objetivos al conjunto de objetivos saturados, establezca su valor de saturación en${\displaystyle z_{\max }}$y volver a (P1).

Queda por explicar cómo podemos encontrar nuevos objetivos saturados en cada iteración.

Método 1: optimizadores interiores . ^{[ 1 ] [ 6 ]} Un optimizador interior de un programa lineal es una solución óptima en la que el menor número posible de restricciones son estrictas. En otras palabras, es una solución en el interior de la cara óptima. Un optimizador interior de (P1) se puede encontrar resolviendo (P1) usando el método del elipsoide o métodos de punto interior .

El conjunto de restricciones estrictas en un optimizador interior es único. Demostración : Supongamos por contradicción que existen dos optimizadores interiores, x1 y x2, con conjuntos diferentes de restricciones estrictas. Dado que el conjunto factible es convexo, la solución promedio x3 = (x1+x2)/2 también es un optimizador. Toda restricción que no sea estricta ni en x1 ni en x2, tampoco lo es en x3. Por lo tanto, el número de restricciones estrictas en x3 es menor que en x1 y x2, lo que contradice la definición de un optimizador interior.

Por lo tanto, el conjunto de restricciones estrictas en el optimizador interno corresponde al conjunto de objetivos libres que se saturan. Mediante este método, la solución leximin se puede calcular con un máximo de n iteraciones.

Método 2: iterar sobre todos los objetivos . ^{[ 7 ]} Es posible encontrar al menos un objetivo saturado utilizando el siguiente algoritmo.

• Para cada objetivo libre${\displaystyle f_{j}}$:
  • (P2) Resuelva el siguiente problema de un solo objetivo:$${\displaystyle {\begin{aligned}\max ~~~f_{j}(x)\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)\geq z_{k}{\text{ for all saturated objectives }}k,\\&f_{k}(x)\geq z_{\max }{\text{ for all free objectives }}k\end{aligned}}}$$
  • Si el valor óptimo es igual a${\displaystyle z_{\max }}$, entonces el objetivo j se satura a partir de ahora.
  • De lo contrario, el valor óptimo debe ser mayor que${\displaystyle z_{\max }}$; Objective- J sigue siendo gratuito por ahora.
• Fin para

En cada paso, al menos un objetivo libre debe saturarse. Esto se debe a que, si ningún objetivo estuviera saturado, entonces la media de todas las soluciones óptimas para (P2) sería una solución factible en la que todos los valores de los objetivos son mayores que${\displaystyle z_{\max }}$- contradiciendo la optimalidad de la solución a (P1). Por ejemplo, supongamos que${\displaystyle z_{\max }=1}$, el objetivo 1 no está saturado porque hay una solución con vector de valores (3,1), y el objetivo 2 no está saturado porque existe una solución con vector de valores y (1,3). Entonces, existe una solución con vector de valores al menos (2,2), pero${\displaystyle z_{\max }}$Deberían haber sido al menos 2.

Por lo tanto, después de como máximo n iteraciones, todas las variables están saturadas y se encuentra una solución óptima leximin. En cada iteración t , el algoritmo resuelve como máximo n - t + 1 programas lineales; por lo tanto, el tiempo de ejecución del algoritmo es como máximo${\displaystyle (n+2)(n+1)/2\in O(n^{2})}$veces el tiempo de ejecución del solucionador LP.

En algunos casos, se puede mejorar el tiempo de ejecución del algoritmo de saturación. En lugar de encontrar todos los objetivos saturados, podemos salir del bucle interno después de encontrar un objetivo saturado; el algoritmo sigue deteniéndose después de un máximo de n iteraciones y puede reducir el número de programas lineales (P2) que necesitamos resolver. ^{[ 5 ] : Alg.3}

Además, en lugar de iterar sobre todos los objetivos para encontrar uno saturado, el algoritmo puede encontrar un objetivo saturado utilizando el problema dual de (P1). En algunos casos, las variables duales se obtienen como subproducto de la resolución de (P1), por ejemplo, cuando los objetivos y las restricciones son lineales y el solucionador es el algoritmo simplex . En este caso, (P2) no es necesario en absoluto, y el tiempo de ejecución del algoritmo es como máximo${\displaystyle n}$veces el tiempo de ejecución del solucionador de (P1). ^{[ 5 ] : Alg.4}

Todas estas variantes solo funcionan para problemas convexos. Para problemas no convexos, es posible que no exista una función objetivo saturada, por lo que el algoritmo podría no detenerse.

El algoritmo de resultados ordenados funciona en dominios arbitrarios (no necesariamente convexos). Fue desarrollado por Ogryczak y Śliwiński ^{[ 16 ]} y también presentado en el contexto de redes de telecomunicaciones por Ogryczak, Pioro y Tomaszewski ^{[ 5 ]} , y en el contexto de problemas de localización por Ogryczak ^{[ 17 ]} . El algoritmo reduce la optimización lexmaxmin al problema más sencillo de la optimización lexicográfica . La optimización lexicográfica se puede realizar con un algoritmo secuencial simple , que resuelve como máximo n programas lineales. La reducción comienza con la siguiente presentación de lexmaxmin:$${\displaystyle {\begin{aligned}(L1)\\\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

Este problema no se puede resolver tal cual, porque${\displaystyle f_{[t]}(x)}$(el t -ésimo valor más pequeño en${\displaystyle \mathbf {f} (x)}$) no es una función simple de x . El problema (L1) es equivalente al siguiente problema, donde${\displaystyle f_{[1..t]}(x):=\sum _{i=1}^{t}f_{[i]}(x)=}$la suma de los t valores más pequeños en${\displaystyle \mathbf {f} (x)}$:$${\displaystyle {\begin{aligned}(L2)\\\operatorname {lex} \max &&f_{[1..1]}(x),f_{[1..2]}(x),\ldots ,f_{[1..n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

Este problema puede resolverse iterativamente mediante optimización lexicográfica , pero el número de restricciones en cada iteración t es C( n , t ), que representa el número de subconjuntos de tamaño t . Este número crece exponencialmente con n . Es posible reducir el problema a otro diferente, en el que el número de restricciones es polinomial en n .

Para cada t , la suma${\displaystyle f_{[1..t]}(x)}$se puede calcular como el valor óptimo para el siguiente problema, con n + 1 variables auxiliares (una variable no acotada)${\displaystyle r_{t}}$y variables no negativas${\displaystyle d_{t,j}}$para todo j en 1,..., n ), y n restricciones adicionales: ^{[ 5 ] : Teorema 8 [ 18 ]}$${\displaystyle {\begin{aligned}(L3)\\\max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}}$$

Demostración . Calculemos los valores de las variables auxiliares en la solución óptima.

• Para todo j , ${\displaystyle d_{t,j}}$debe ser al menos tan grande como 0 y${\displaystyle r_{t}-f_{j}(x)}$y sujeto a esto, debe minimizarse, ya que aparece en el objetivo con un signo menos. Por lo tanto,${\displaystyle d_{t,j}=\max(0,r_{t}-f_{j}(x))}$Por lo tanto, el objetivo se puede escribir como: ${\displaystyle t\cdot r_{t}-\sum _{j=1}^{n}\max(0,r_{t}-f_{j}(x))}$.
• Para cualquier k entre 0 y n, si${\displaystyle r_{t}}$es mayor que los valores objetivos k más pequeños (es decir,${\displaystyle r_{t}\geq f_{[k]}(x)}$), entonces la suma del lado derecho contiene exactamente k elementos positivos:${\displaystyle \sum _{j=1}^{k}(r_{t}-f_{[j]}(x))=k\cdot r_{t}-f_{[1..k]}(x)}$En ese caso, el objetivo se puede escribir como: ${\displaystyle (t-k)\cdot r_{t}+f_{[1..k]}(x)}$. Tenga en cuenta que${\displaystyle (t-k)\cdot r_{t}}$está aumentando con${\displaystyle r_{t}}$cuando k < t y disminuye con${\displaystyle r_{t}}$cuando k > t . Por lo tanto, el valor máximo se alcanza cuando k = t , es decir,${\displaystyle r_{t}}$es mayor que los valores objetivos t más pequeños ; en ese caso, el objetivo es exactamente igual a${\displaystyle f_{[1..t]}(x)}$, como se afirma.

Por lo tanto, el problema (L2) es equivalente al siguiente problema de maximización lexicográfica: ^{[ 5 ] : (32)}$${\displaystyle {\begin{aligned}(L4)\\\operatorname {lex} \max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})_{t=1}^{n}\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}}$$

Este problema (L4) tiene${\displaystyle n^{2}+n}$variables adicionales y${\displaystyle n^{2}}$restricciones adicionales. Puede resolverse mediante cualquier algoritmo para resolver la maximización lexicográfica , por ejemplo: el algoritmo secuencial que utiliza n programas lineales, o el algoritmo simplex lexicográfico (si los objetivos y las restricciones son lineales).

El algoritmo de valores ordenados funciona en cualquier dominio en el que el conjunto de valores posibles de las funciones objetivo sea finito. Fue desarrollado por Ogryczak y Śliwiński. ^{[ 16 ]} Sea${\displaystyle V=\{v_{1},\ldots ,v_{r}\}}$sea ​​el conjunto de todos los valores que pueden ser devueltos por las funciones${\displaystyle f_{1},\ldots ,f_{n}}$, de tal manera que${\displaystyle v_{1}<\cdots <v_{r}}$. Dada una solución x y un entero k en {1,.., r }, defina${\displaystyle h_{k}(x)}$como el número de ocurrencias del valor v _r en el vector ${\displaystyle f_{1}(x),\ldots ,f_{n}(x)}$Entonces, el problema lexmaxmin puede enunciarse como el siguiente problema de minimización lexicográfica:$${\displaystyle {\begin{aligned}(H1)\\\operatorname {lex} \min &&h_{1}(x),\ldots ,h_{r-1}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$Dado que deseamos que la menor cantidad posible de funciones alcancen el valor más pequeño, y sujeto a esto, que la menor cantidad posible de funciones alcancen el siguiente valor más pequeño, y así sucesivamente. Ogryczak y Śliwiński ^{[ 16 ]} muestran cómo transformar este programa no lineal en un programa lineal con variables auxiliares. En sus experimentos computacionales, el algoritmo de Valores Ordenados se ejecuta mucho más rápido que el algoritmo de Saturación y el algoritmo de Resultados Ordenados.

Behringer ^{[ 4 ]} presentó un algoritmo secuencial para la optimización lexmaxmin cuando los objetivos son funciones cuasiconvexas y el conjunto factible X es un conjunto convexo .

Yager ^{[ 20 ]} presentó una forma de representar analíticamente el ordenamiento leximin utilizando el operador de agregación de promedio ponderado ordenado . Supone que todos los valores objetivo son números reales entre 0 y 1, y que la diferencia más pequeña entre dos valores posibles es una constante d < 1 (de modo que los valores con una diferencia menor que d se consideran iguales). El peso${\displaystyle w_{t}}$de${\displaystyle f_{[t]}(x)}$está configurado para aproximadamente${\displaystyle d^{t}}$Esto garantiza que se maximice la suma ponderada.${\displaystyle \sum _{t}w_{t}f_{[t]}(x)}$es equivalente a lexmaxmin.