Oráculo de separación

Concepto en la teoría matemática de la optimización convexa

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 los métodos de elipsoide . ^{[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}

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

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 es d-cerca de K si su distancia euclidiana desde K es como máximo d ;
• Un vector y tiene profundidad d 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 -cerca de K ;
• Encuentra un vector a en Q ⁿ , normalizado tal que su elemento máximo sea 1, tal que para todos los x que sean d -profundos en K . ${\displaystyle a\cdot y+d\geq a\cdot x}$

Implementación

Un caso especial de un conjunto convexo es un conjunto representado por desigualdades lineales: . Un conjunto de este tipo 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. ${\displaystyle K=\{x|Ax\leq b\}}$

Representación por desigualdades

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

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

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 da como entrada, de modo que la envoltura convexa de sus vértices. Entonces, decidir si y está en K requiere 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} ${\displaystyle K={\text{conv}}(v_{1},\ldots ,v_{k})=}$

• ${\displaystyle z_{1}\cdot v_{1}+\cdots +z_{k}\cdot v_{k}=y}$;
• ${\displaystyle 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

• ${\displaystyle 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 pueda representarse mediante un pequeño número de desigualdades, pero que tenga exponencialmente muchos vértices (por ejemplo, un cubo n -dimensional). A la inversa, 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, se puede escribir un oráculo de separación personalizado que funcione en tiempo polinómico. Algunos ejemplos son:

• Problema de arborescencia de costo mínimo : dado un grafo dirigido ponderado y un vértice r en él, encuentre un subgrafo de costo mínimo que contenga una ruta dirigida desde r a cualquier otro vértice. El problema puede presentarse como un LP con una restricción para cada subconjunto de vértices, que es 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 . Puede aproximarse mediante un PL con una restricción para cada ciclo de longitud impar. Si bien existen muchos ciclos de este tipo de forma exponencial, se puede implementar un oráculo de separación que funcione en tiempo polinómico simplemente encontrando un ciclo impar de longitud mínima, lo que se puede hacer en tiempo polinómico. ^[3]
• El dual del programa lineal de configuración para el problema de empaquetamiento de bins . Puede aproximarse mediante un LP con una restricción para cada configuración factible. Si bien existen muchos ciclos de este tipo exponencialmente, se puede implementar un oráculo de separación que funcione en tiempo pseudopolinomial resolviendo un problema de mochila . Esto lo utilizan los algoritmos de empaquetamiento de bins de Karmarkar-Karp .

Conjuntos no lineales

Sea f una función convexa en R ⁿ . El conjunto 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), uno puede verificar 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} Supóngase que algún vector ( y , s ) no está en K , entonces f ( y ) > s . Sea g el subgradiente de f en y ( g es un vector en R ⁿ ) . Denotemos . Entonces, , y para todo ( x , t ) en K : . Por definición de un subgradiente: para todo x en R ⁿ . Por lo tanto, , entonces , y c representa un hiperplano separador. ${\displaystyle K=\{(x,t)|f(x)\leq t\}}$ ${\displaystyle c:=(g,-1)}$ ${\displaystyle c\cdot (y,s)=g\cdot y-s>g\cdot y-f(y)}$ ${\displaystyle c\cdot (x,t)=g\cdot x-t\leq g\cdot x-f(x)}$ ${\displaystyle f(x)\geq f(y)+g\cdot (x-y)}$ ${\displaystyle g\cdot y-f(y)\geq g\cdot x-f(x)}$ ${\displaystyle c\cdot (y,s)>c\cdot (x,t)}$

Uso

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

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

Después de 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 un polinomio temporal con la precisión requerida.

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. 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, Sr.  1261419
2. "MIT 6.854 Primavera 2016 Clase 12: De la separación a la optimización y viceversa; Método elipsoide - YouTube" www.youtube.com . Consultado el 3 de enero de 2021 .
3. Vempala, Santosh (2016). "Oráculo de la separación" (PDF) .