Considere un politopo racional que se define por medio de un oráculo de separación. Es decir, puede describirse implícitamente como , pero dado que es muy grande, utilizamos un oráculo, que da un punto , o bien dice o devuelve una media-espacio tal que .P P = { x ∈ R k : A x ≤ b , A ∈ Z m × k , b ∈ Z m } m x ∈ R k x ∈ P x ∉ S
Mi objetivo es encontrar un punto en o determinar que está vacío. Mi objetivo para un polinomio de tiempo de ejecución en el tamaño de representación de y , donde es el valor absoluto más grande de . Es decir, el algoritmo solo debe hacer muchas llamadas polinómicas al oráculo de separación.P U k U A
En general, podría estar contenido en un hiperplano de dimensión inferior y, por lo tanto, es problemático utilizar el método elipsoide. Así, como en el truco de Khachiyan, me alter (y el oráculo de separación) para utilizar , en donde es algo así como . Intuitivamente, los medios espacios que definen son los mismos que los que definen solo que son traducidos por . El politopo tiene las siguientes propiedades: está vacío si está vacío, y si no está vacío,P P ϵ ϵ 1 / U P ϵ P Es de dimensiones completas.
Mi pregunta es la siguiente: suponga que el algoritmo encuentra un punto . ¿Es posible generar un punto en usando ?
Si su objetivo es encontrar un punto en o determinar que P está vacío, ¿por qué no hace lo siguiente?P P
Sea un conjunto de medios espacios, inicialmente vacíos.H
Sea un punto, inicialmente igual a 0 k .x 0k
Dale al oráculo.x
Si el oráculo dijo , lo has hecho.x∈P
De lo contrario, sea el medio espacio violado devuelto por el oráculo. Vamos y la proyección ortogonal de x en S .S y x S
Regrese a 1.
fuente