Motivação para estimativa de volume

12

Quais são algumas aplicações concretas e convincentes para estimar o volume de poliedros convexos do tipo considerado nos artigos mais recentes sobre métodos de caminhada aleatória?

Estes trabalhos sobre estimativa de volume mencionam a integração numérica como uma motivação. Quais são os exemplos de integrais que as pessoas desejam calcular na prática que são muito difíceis de calcular usando métodos anteriores? Ou existe alguma outra aplicação prática convincente para calcular o volume de um politopo 1000-dimensional?

cg.comp-geom na.numerical-analysis markov-chains
fonte
Gostaria de saber se você obterá mais respostas do tipo que procura em physics.stackexchange.com ... Além disso, para aqueles que não estão familiarizados com essa subárea específica da teoria, você pode incluir algumas referências para "trabalhos mais recentes sobre métodos de caminhada aleatória"?
Joshua Grochow
mais pensando nisso depois de responder e bisbilhotar. alguns trabalhos parecem apontar, ou seguir na direção, que calcular o volume do politopo é algo como um problema fundamental na teoria da complexidade. isso não é surpreendente, uma vez que o cálculo do determinante é outro problema-chave na teoria da complexidade e o determinante é o volume de uma resposta paralela. portanto, uma resposta razoável parece ser que parecem existir conexões profundas ou naturais na teoria da complexidade. mais evidências de que este seria um empate a alguma classe de complexidade específica .... pode cavar em volta mais sobre isso ....
vzn
veja também mathoverflow, algoritmo para encontrar o volume de politopo complexo . Sim, esta pergunta acima solicita aplicativos, não algoritmos, mas alguns documentos sobre algoritmos fornecerão motivações / aplicativos.
vzn

Respostas:

7

A estimativa do volume de um polítopo convexo e a tarefa intimamente relacionada de amostragem a partir dele têm aplicativos em liberação de dados privados.

Basicamente, o problema que você deseja resolver é: dada uma coleção de consultas com valores numéricos em um banco de dados, encontre respostas para as perguntas o mais próximo possível das respostas reais, enquanto satisfaz a privacidade diferencial. Em alguns parâmetros, o algoritmo ideal para resolver esse problema tem uma descrição geométrica, e sua implementação envolve amostragem de um polítopo convexo. Veja aqui: http://arxiv.org/pdf/0907.3754v3.pdf

Aaron Roth
fonte
4

ss

Em segurança de computadores, o trabalho sobre o fluxo quantitativo de informações aplicou esses métodos para estimar a quantidade de informações confidenciais que podem ser vazadas por um programa específico. Aqui, construímos um poliedro que representa possíveis estados do programa em um ponto específico de sua execução e, em seguida, queremos estimar algo sobre o número de possíveis estados (isso está relacionado à quantidade de informações liberadas). Assim, em um determinado ponto da análise, eles acabam tentando contar o número de pontos inteiros contidos no poliedro. Isso cheira a estimativa de volume (para mim).

Aqui está um artigo inicial que é representativo:

Dito isto, isso pode não ser exatamente o que você está procurando. Requer métodos para contar o número de pontos inteiros dentro do poliedro, que não é o mesmo que o volume do poliedro. Além disso, acho que eles não precisam analisar poliedros de dimensão 1000 ou superior (embora não tenha certeza disso).

DW
fonte
Obrigado. O problema de encontrar o número de soluções inteiras para um conjunto de desigualdades lineares é # P-completo, eu acho ( math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf também tem mais algumas aplicações). Considerando que a estimativa do volume pode ser feita em tempo poli. Aparentemente, você pode usar o último para aproximar o primeiro, mas estou realmente procurando por aplicações concretas diretas de estimativa de volume.
Computar o volume de um politopo também é difícil. Por si só, esse fato diz pouco sobre aproximações.
Sasho Nikolov 31/07/2013
P≠BPP
1
@Turbo Obviamente, isso não prova que P não seja igual ao BPP, porque essas duas classes não são sobre um modelo Oracle. Eu acredito que a aproximação determinística do volume de um politopo representado por desigualdades é aberta.
Sasho Nikolov
@SashoNikolov Se você conhece esse problema aparentemente simples, seria bom mathoverflow.net/questions/336369/… .
T ....
4

Hari Narayanan publicou recentemente um artigo sobre o arXiv, no qual ele usa a estimativa do volume de um polítopo convexo para provar certos resultados sobre os coeficientes de Littlewood-Richardson (LR). Os coeficientes LR são certos números inteiros na teoria das representações que têm aplicações na teoria da complexidade geométrica, na física de partículas e em muitos outros campos (consulte a introdução do artigo acima para obter mais referências). Novamente, provavelmente não exatamente o que você queria, mas uma conexão interessante, no entanto.

Joshua Grochow
fonte
3

veja, por exemplo: Estimativa de volume n-dimensional de corpos convexos: algoritmos e aplicações de Sharma, Prasanna, Aswal para um exemplo / estudo de caso em previsão econômica, isto é, gerenciamento da cadeia de suprimentos.

Nossos métodos podem ser usados ​​para quantificar o conteúdo e a incerteza das informações, em regiões de restrição, em uma estrutura de otimização robusta. Mostramos aplicações no gerenciamento da cadeia de suprimentos, sob condições de incerteza futura.

basicamente, a idéia é que um politopo pode modelar um "cenário futuro" de parâmetros de uma configuração de gerenciamento da cadeia de suprimentos. a incerteza (ou "erro") no modelo / estimativa é tomada como proporcional ao volume do (s) politopo (s). veja slides 3,4. isso permite:

  • estimativa quantitativa da incerteza
  • geração de informações equivalentes
  • ajuda na análise what-if
vzn
fonte
Obrigado. Esses exemplos são bons, mas ainda acho difícil acreditar que eles são o que significam quando as pessoas dizem que estimar o volume de um corpo convexo de alta dimensão é uma das aplicações mais importantes do método Monte Carlo da Cadeia de Markov.
concordamos que o exemplo nos slides é "tamanho do brinquedo" no que diz respeito ao número de dimensões, mas talvez alguns problemas de gerenciamento da cadeia de suprimentos tenham grandes dimensões na prática. também essa linha de pesquisa parece sugerir que pode ter alguma aplicação em algumas formas de datamining.
vzn