Muestreo uniforme de Convexa Polytopes

Question

Cómo elegir un punto uniformemente de un convexo polytope $P \subset [0,1]^n$ definido por algunas desigualdades, Ax < b ? (Aquí es un m-por-n de la matriz, x es n-por-1 y b es m-por-1.) Me imagino que usted podría empezar con un uniforme de punto elegido en el cubo y hacer un proceso para obtener un punto con Ax < b.

Answer 1

Ver las respuestas a esta pregunta - muestreo uniforme de polytopes constituye la base para los algoritmos conocidos para el cálculo de los volúmenes. Los métodos de los documentos mencionados en las respuestas que en su mayoría tienen la forma de una caminata al azar en el interior de la polytope; difieren en los detalles de la caminata y en el análisis de su tiempo de mezcla.

Answer 2

Hit and run muestreo se realiza mucho mejor que el rechazo de muestreo para dimensiones superiores.

Se converge a una distribución uniforme en el tiempo polinomio. La idea básica es empezar en cualquier punto de $x_0$ dentro de la polytope, a continuación, siga el procedimiento siguiente forma iterativa:

• escoger una dirección $\alpha$ uniformemente al azar.
• encontrar el mínimo y máximo valor de $\theta$ tal que $x_n+\theta\cdot\alpha$ está contenida en el polytope
• escoge un $\theta^*$ uniformemente al azar de $[\theta_{min},\theta_{max}]$
• el nuevo punto es $x_{n+1}=x_n+\theta^*\cdot\alpha$

Answer 3

El rechazo de muestreo definitivamente el trabajo. Tomar un hipercubo de que usted sabe que contiene el polytope, muestra de la hipercubo, y aceptar sólo aquellas muestras que pertenecen a la polytope. Sin embargo, si el volumen relativo de la polytope es pequeño, usted va a terminar rechazando la mayoría de las muestras, y el método puede obtener dolorosamente lento. Dependiendo de sus necesidades, es posible que desee encontrar, por ejemplo, el más pequeño, adjuntando el balón primero, de modo que usted puede dibujar su uniforme de las muestras de que en lugar del hipercubo.
Véase Boyd & Vanderberghe, el libro de Optimización Convexa (en línea) para encontrar más pequeño que encierra conjuntos.

Answer 4

Si usted usa MATLAB cprnd en su Archivo de Intercambio resuelve el problema.

Answer 5

El rechazo de muestreo.