Motivación para la estimación del volumen.

12

¿Cuáles son algunas aplicaciones concretas y convincentes para estimar el volumen de poliedros convexos del tipo considerado en los documentos más recientes sobre métodos de caminata aleatoria?

Estos documentos sobre estimación de volumen mencionan la integración numérica como una motivación. ¿Cuáles son ejemplos de integrales que la gente quiere calcular en la práctica que son muy difíciles de calcular utilizando métodos anteriores? ¿O hay alguna otra aplicación práctica convincente para calcular el volumen de un politopo de 1000 dimensiones?

cg.comp-geom na.numerical-analysis markov-chains
fuente
Me pregunto si obtendrá más respuestas del tipo que está buscando en physics.stackexchange.com ... Además, para aquellos de nosotros que no estamos familiarizados con esta subárea particular de la teoría, ¿podrían incluir algunas referencias para ¿"documentos más recientes sobre métodos de caminata aleatoria"?
Joshua Grochow
más pensando en esto después de responder y hurgar. Algunos documentos parecen señalar, o ir en la dirección, que calcular el volumen del politopo es algo así como un problema fundamental en la teoría de la complejidad. Esto no es sorprendente dado que calcular el determinante es otro problema clave en la teoría de la complejidad, y el determinante es el volumen de un tubo paralelo. Entonces, una respuesta razonable parece ser que parece haber conexiones profundas o naturales en la teoría de la complejidad. Más evidencia de esto sería un vínculo con alguna clase de complejidad específica ... puede cavar más en esto ...
vzn
ver también mathoverflow, algoritmo para encontrar el volumen del politopo complejo . Sí, esta pregunta anterior solicita aplicaciones, no algoritmos, pero algunos de los documentos sobre algoritmos darán motivaciones / aplicaciones.
vzn

Respuestas:

7

La estimación del volumen de un politopo convexo y la tarea estrechamente relacionada de tomar muestras de él tienen aplicaciones en la liberación de datos privados.

Aproximadamente, el problema que desea resolver es: dada una colección de consultas con valores numéricos en una base de datos, encontrar respuestas a esas preguntas que estén lo más cerca posible de las respuestas reales, al tiempo que satisface la privacidad diferencial. En algún rango de parámetros, el algoritmo óptimo para resolver este problema tiene una descripción geométrica, y su implementación implica el muestreo de un politopo convexo. Ver aquí: http://arxiv.org/pdf/0907.3754v3.pdf

Aaron Roth
fuente
4

ss

En seguridad informática, el trabajo sobre el flujo de información cuantitativa ha aplicado estos métodos para estimar la cantidad de información confidencial que un programa en particular podría filtrar. Aquí construimos un poliedro que representa posibles estados del programa en un punto particular de su ejecución, y luego queremos estimar algo sobre el número de posibles estados (esto está relacionado con la cantidad de información publicada). Por lo tanto, en cierto punto del análisis, terminan tratando de contar el número de puntos enteros contenidos dentro del poliedro. Esto huele relacionado con la estimación de volumen (para mí).

Aquí hay un documento temprano que es representativo:

Dicho esto, esto podría no ser exactamente lo que estás buscando. Requiere métodos para contar el número de puntos enteros dentro del poliedro, que no es lo mismo que el volumen del poliedro. Además, no creo que necesiten analizar poliedros de dimensión 1000 o superior (aunque no estoy seguro de eso).

DW
fuente
Gracias. El problema de encontrar el número de soluciones enteras para un conjunto de desigualdades lineales es # P-complete, creo ( math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf también tiene algunas aplicaciones más). Mientras que la estimación del volumen se puede hacer en tiempo poli. Aparentemente puede usar el último para aproximar el primero, pero realmente estoy buscando aplicaciones concretas directas de estimación de volumen.
Calcular el volumen de un politopo también es # P-hard. Por sí mismo, este hecho dice poco acerca de las aproximaciones.
Sasho Nikolov
P≠BPP
1
@Turbo Obviamente, no prueba que P no sea igual a BPP, porque estas dos clases no son sobre un modelo de oráculo. Creo que la aproximación determinista al volumen de un politopo representado por desigualdades está abierta.
Sasho Nikolov
@SashoNikolov Si conoces este problema aparentemente simple, sería bueno mathoverflow.net/questions/336369/… .
T ....
4

Hari Narayanan recientemente publicó un artículo sobre el arXiv en el que usa la estimación del volumen de un politopo convexo para probar ciertos resultados sobre los coeficientes de Littlewood-Richardson (LR). Los coeficientes LR son ciertos enteros en la teoría de la representación que tienen aplicaciones en la teoría de la complejidad geométrica, la física de partículas y muchos otros campos (consulte la introducción del documento anterior para obtener más referencias). De nuevo, probablemente no sea exactamente lo que querías, pero una conexión interesante, no obstante.

Joshua Grochow
fuente
3

véase, por ejemplo: Estimación del volumen N-dimensional de cuerpos convexos: Algoritmos y aplicaciones de Sharma, Prasanna, Aswal para un ejemplo / estudio de caso en pronósticos económicos, es decir, gestión de la cadena de suministro.

Nuestros métodos se pueden utilizar para cuantificar el contenido de información y la incertidumbre, en regiones de restricción, en un marco de optimización robusto. Mostramos aplicaciones en la gestión de la cadena de suministro, en condiciones de incertidumbre futura.

Básicamente, la idea es que un politopo puede modelar un "escenario futuro" de parámetros de una configuración de gestión de la cadena de suministro. La incertidumbre (o "error") en el modelo / estimación se toma como proporcional al volumen de los politopes. ver diapositivas 3,4. esto luego permite:

  • estimación cuantitativa de la incertidumbre
  • generación de información equivalente
  • ayuda en análisis hipotético
vzn
fuente
Gracias. Estos ejemplos son agradables, pero aún me cuesta creer que sean lo que se quiere decir cuando la gente dice que estimar el volumen de un cuerpo convexo de alta dimensión es una de las aplicaciones más importantes del método Markov Chain Monte Carlo.
acordó que el ejemplo en las diapositivas es "tamaño de juguete" en cuanto al número de dimensiones, pero tal vez algunos problemas de gestión de la cadena de suministro tienen grandes dimensiones en la práctica. También esta línea de investigación parece sugerirme que puede tener alguna aplicación en algunas formas de minería de datos.
vzn