oráculo de separación

Un oráculo de separación (también llamado oráculo de plano de corte ) es un concepto de la teoría matemática de la optimización convexa . Es un método para describir un conjunto convexo que se proporciona como entrada a un algoritmo de optimización . Los oráculos de separación se utilizan como entrada para métodos elipsoidales . ^{[ 1 ]}^{: 87, 96, 98}

Definición

Sea K un conjunto convexo y compacto en R ⁿ . Un oráculo de separación fuerte para K es un oráculo ( caja negra ) que, dado un vector y en R ⁿ , devuelve uno de los siguientes: ^{[ 1 ]}^{: 48}

Afirma que y está en K.
Encuentra un hiperplano que separe a y de K : un vector a en R ⁿ , tal que $a\cdot y>a\cdot x$ para todo x en K .

Un oráculo de separación fuerte es completamente preciso y, por lo tanto, puede ser difícil de construir. Por razones prácticas, se considera una versión más débil, que permite pequeños errores en el límite de K y las desigualdades. Dada una pequeña tolerancia de error d > 0, decimos que:

Un vector y está d-cerca de K si su distancia euclidiana a K es como máximo d ;
Un vector y es d-profundo en K si está en K , y su distancia euclidiana desde cualquier punto fuera de K es al menos d .

La versión débil también considera números racionales , que tienen una representación de longitud finita, en lugar de números reales arbitrarios. Un oráculo de separación débil para K es un oráculo que, dado un vector y en Q ⁿ y un número racional d >0, devuelve uno de los siguientes: ^{[ 1 ]}^{: 51}

Afirmar que y es d -cercano a K ;
Encuentra un vector a en Q ⁿ , normalizado de tal manera que su elemento máximo sea 1, tal que $a\cdot y+d\geq a\cdot x$ para todos los x que están d -profundidad en K.

Implementación

Un caso especial de conjunto convexo es un conjunto representado por desigualdades lineales : $K=\{x|Ax\leq b\}$ Dicho conjunto se denomina politopo convexo . Se puede implementar un oráculo de separación fuerte para un politopo convexo , pero su tiempo de ejecución depende del formato de entrada.

Representación por desigualdades

Si se proporcionan como entrada la matriz A y el vector b , de modo que $K=\{x|Ax\leq b\}$ , entonces se puede implementar un oráculo de separación fuerte de la siguiente manera. ^{[ 2 ]} Dado un punto y , calcular $Ay$ :

Si el resultado es como máximo $b$ , entonces y está en K por definición;
De lo contrario, hay al menos una fila. $c$ de A , tal que $c\cdot y$ es mayor que el valor correspondiente en $b$ ; esta fila $c$ nos da el hiperplano separador, como $c\cdot y>b\geq c\cdot x$ para todo x en K .

Este oráculo se ejecuta en tiempo polinomial siempre que el número de restricciones sea polinomial.

Representación por vértices

Supongamos que el conjunto de vértices de K se proporciona como entrada, de modo que $K={\text{conv}}(v_{1},\ldots ,v_{k})=$ la envoltura convexa de sus vértices. Luego, para decidir si y está en K, es necesario comprobar si y es una combinación convexa de los vectores de entrada, es decir, si existen coeficientes z ₁ ,..., z _k tales que: ^{[ 1 ]}^{: 49}

$z_{1}\cdot v_{1}+\cdots +z_{k}\cdot v_{k}=y$ ;
$0\leq z_{i}\leq 1$ para todo i en 1,..., k .

Este es un programa lineal con k variables y n restricciones de igualdad (una para cada elemento de y ). Si y no está en K , entonces el programa anterior no tiene solución, y el oráculo de separación necesita encontrar un vector c tal que

$c\cdot y>c\cdot v_{i}$ para todo i en 1,..., k .

Nótese que las dos representaciones anteriores pueden ser muy diferentes en tamaño: es posible que un politopo se pueda representar mediante un pequeño número de desigualdades, pero tenga exponencialmente muchos vértices (por ejemplo, un cubo n -dimensional). Por el contrario, es posible que un politopo tenga un pequeño número de vértices, pero requiera exponencialmente muchas desigualdades (por ejemplo, la envoltura convexa de los 2 n vectores de la forma (0,...,±1,...,0).

Representación específica del problema

En algunos problemas de optimización lineal, aunque el número de restricciones sea exponencial, aún se puede escribir un oráculo de separación personalizado que funcione en tiempo polinomial. Algunos ejemplos son:

El problema de arborescencia de costo mínimo : dado un grafo dirigido ponderado y un vértice r en él, encontrar un subgrafo de costo mínimo que contenga un camino dirigido desde r a cualquier otro vértice. El problema puede presentarse como un problema de programación lineal con una restricción para cada subconjunto de vértices, lo que implica un número exponencial de restricciones. Sin embargo, se puede implementar un oráculo de separación utilizando n - 1 aplicaciones del procedimiento de corte mínimo . ^{[ 3 ]}
El problema del conjunto independiente máximo . Se puede aproximar mediante un problema de programación lineal con una restricción para cada ciclo de longitud impar. Si bien existen exponencialmente muchos de estos ciclos, se puede implementar un oráculo de separación que funcione en tiempo polinomial simplemente encontrando un ciclo impar de longitud mínima, lo cual se puede hacer en tiempo polinomial. ^{[ 3 ]}
El dual del programa lineal de configuración para el problema de empaquetamiento de contenedores . Se puede aproximar mediante un programa lineal con una restricción para cada configuración factible. Si bien existen exponencialmente muchos ciclos de este tipo, se puede implementar un oráculo de separación que funciona en tiempo pseudopolinomial resolviendo un problema de la mochila . Esto es lo que utilizan los algoritmos de empaquetamiento de contenedores de Karmarkar-Karp .

Conjuntos no lineales

Sea f una función convexa en R ⁿ . El conjunto $K=\{(x,t)|f(x)\leq t\}$ es un conjunto convexo en R ^{n +1} . Dado un oráculo de evaluación para f (una caja negra que devuelve el valor de f para cada punto dado), se puede comprobar fácilmente si un vector ( y , t ) está en K . Para obtener un oráculo de separación, también necesitamos un oráculo para evaluar el subgradiente de f . ^{[ 1 ]}^{: 49} Supongamos que algún vector ( y , s ) no está en K , por lo que f ( y ) > s . Sea g el subgradiente de f en y ( g es un vector en R ⁿ ) . Denotemos $c:=(g,-1)$ .Entonces, $c\cdot (y,s)=g\cdot ys>g\cdot yf(y)$ y para todo ( x , t ) en K : $c\cdot (x,t)=g\cdot xt\leq g\cdot xf(x)$ . Por definición de subgradiente: $f(x)\geq f(y)+g\cdot (xy)$ para todo x en R ⁿ . Por lo tanto, $g\cdot yf(y)\geq g\cdot xf(x)$ , entonces $c\cdot (y,s)>c\cdot (x,t)$ y c representa un hiperplano separador.

Uso

Un oráculo de separación fuerte puede proporcionarse como entrada al método del elipsoide para resolver un programa lineal. Consideremos el programa lineal. ${\text{maximizar}}~~c\cdot x~~{\text{sujeto a}}~~Ax\leq b,x\geq 0$ El método del elipsoide mantiene un elipsoide que inicialmente contiene todo el dominio factible. $Ax\leq b$ En cada iteración t , toma el centro $x_{t}$ del elipsoide actual, y lo envía al oráculo de separación:

Si el oráculo dice que $x_{t}$ es factible (es decir, está contenido en el conjunto $Ax\leq b$ ), luego hacemos un "corte de optimalidad" en $x_{t}$ : recortamos del elipsoide todos los puntos x para los cuales $c\cdot x<c\cdot x_{t}$ Estos puntos definitivamente no son óptimos.
Si el oráculo dice que $x_{t}$ es inviable, entonces normalmente devuelve una restricción específica que es violada por $x_{t}$ , es decir, una fila $a_{j}$ en la matriz A, de tal manera que $a_{j}\cdot x_{t}>b_{j}$ . Desde $a_{j}\cdot x\leq b_{j}$ para todo x factible , esto implica que $a_{j}\cdot x_{t}>a_{j}\cdot x$ para todos los x factibles . Luego, hacemos un "corte de factibilidad" en $x_{t}$ : recortamos del elipsoide todos los puntos y para los cuales $a_{j}\cdot y>a_{j}\cdot x_{t}$ Estos puntos son definitivamente inviables.

Tras realizar un corte, construimos un nuevo elipsoide más pequeño que contiene la región restante. Se puede demostrar que este proceso converge a una solución aproximada en tiempo polinomial con la precisión requerida.

Cómo convertir un oráculo débil en un oráculo fuerte

Dado un oráculo de separación débil para un poliedro , es posible construir un oráculo de separación fuerte mediante un método cuidadoso de redondeo o mediante aproximaciones diofánticas . ^{[ 1 ]}^{: 159}

Véase también

Problemas algorítmicos sobre conjuntos convexos

Referencias

1 2 3 4 5 6 Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria , Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi : 10.1007/978-3-642-78240-4 , ISBN 978-3-642-78242-8, MR 1261419
↑ "MIT 6.854 Primavera 2016 Lección 12: De la separación a la optimización y viceversa; Método del elipsoide - YouTube" . www.youtube.com . 18 de marzo de 2016. Consultado el 3 de enero de 2021 .
1 2 Vempala, Santosh (2016). "Oráculo de separación" (PDF) .

[:0-1] 1 2 3 4 5 6 Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria , Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi : 10.1007/978-3-642-78240-4 , ISBN 978-3-642-78242-8, MR 1261419

[:03-2] "MIT 6.854 Primavera 2016 Lección 12: De la separación a la optimización y viceversa; Método del elipsoide - YouTube" . www.youtube.com . 18 de marzo de 2016. Consultado el 3 de enero de 2021 .

[:1-3] 1 2 Vempala, Santosh (2016). "Oráculo de separación" (PDF) .