Motivation pour l'estimation du volume

12

Quelles sont les applications concrètes et convaincantes pour estimer le volume de polyèdres convexes du type considéré dans les articles les plus récents sur les méthodes de marche aléatoire?

Ces articles sur l'estimation du volume mentionnent l'intégration numérique comme une motivation. Quels sont les exemples d'intégrales que les gens veulent calculer dans la pratique et qui sont très difficiles à calculer en utilisant les méthodes précédentes? Ou existe-t-il une autre application pratique convaincante pour calculer le volume d'un polytope à 1000 dimensions?

cg.comp-geom na.numerical-analysis markov-chains
la source
Je me demande si vous obtiendrez plus de réponses du type que vous recherchez sur physics.stackexchange.com ... De plus, pour ceux d'entre nous qui ne connaissent pas ce sous-domaine particulier de la théorie, pourriez-vous peut-être inclure des références pour "des articles plus récents sur les méthodes de marche aléatoire"?
Joshua Grochow
plus de réflexion à ce sujet après avoir répondu et fouillé. certains articles semblent indiquer, ou aller dans le sens, que le calcul du volume de polytope est quelque chose comme un problème fondamental dans la théorie de la complexité. cela n'est pas surprenant étant donné que le calcul du déterminant est un autre problème clé dans la théorie de la complexité, et le déterminant est le volume d'un parallélépipède. une réponse raisonnable semble donc être qu'il semble y avoir des connexions profondes ou naturelles dans la théorie de la complexité. plus de preuves de cela serait un lien avec une classe de complexité spécifique .... peut creuser plus à ce sujet ....
vzn
voir aussi mathoverflow, algorithme pour trouver le volume d'un polytope complexe . oui cette question ci-dessus demande des applications, pas des algorithmes, mais certains des articles d'algorithmes donneront des motivations / applications.
vzn

Réponses:

7

L'estimation du volume d'un polytope convexe et la tâche étroitement liée d'en échantillonner ont des applications dans la diffusion de données privées.

En gros, le problème que vous souhaitez résoudre est le suivant: étant donné une collection de requêtes à valeur numérique sur une base de données, trouvez des réponses à ces questions qui sont aussi proches que possible des vraies réponses, tout en satisfaisant la confidentialité différentielle. Dans certains paramètres, l'algorithme optimal pour résoudre ce problème a une description géométrique et sa mise en œuvre implique l'échantillonnage à partir d'un polytope convexe. Voir ici: http://arxiv.org/pdf/0907.3754v3.pdf

Aaron Roth
la source
4

ss

Dans le domaine de la sécurité informatique, les travaux sur le flux d'informations quantitatives ont appliqué ces méthodes pour estimer la quantité d'informations confidentielles susceptibles d'être divulguées par un programme particulier. Ici, nous construisons un polyèdre représentant les états possibles du programme à un moment particulier de son exécution, puis nous voulons estimer quelque chose sur le nombre d'états possibles (cela est lié à la quantité d'informations publiées). Ainsi, à un certain moment de l'analyse, ils finissent par essayer de compter le nombre de points entiers contenus à l'intérieur du polyèdre. Cela sent l'odeur du volume (pour moi).

Voici un premier article représentatif:

Cela dit, ce n'est peut-être pas exactement ce que vous recherchez. Il nécessite des méthodes pour compter le nombre de points entiers à l'intérieur du polyèdre, qui n'est pas le même que le volume du polyèdre. De plus, je ne pense pas qu'ils aient besoin d'analyser les polyèdres de dimension 1000 ou plus (bien que je n'en sois pas sûr).

DW
la source
Je vous remercie. Le problème de trouver le nombre de solutions entières à un ensemble d'inégalités linéaires est # P-complet je pense ( math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf a aussi d'autres applications). Alors que l'estimation du volume peut se faire en poly temps. Vous pouvez apparemment utiliser ce dernier pour approximer le premier, mais je recherche vraiment des applications concrètes directes d'estimation de volume.
Le calcul du volume d'un polytope est également # P-difficile. En soi, ce fait en dit peu sur les approximations.
Sasho Nikolov
P≠BPP
1
@Turbo Évidemment, cela ne prouve pas que P n'est pas égal à BPP, car ces deux classes ne concernent pas un modèle Oracle. Je crois que l'approximation déterministe du volume d'un polytope représenté par des inégalités est ouverte.
Sasho Nikolov
@SashoNikolov Si vous pouviez connaître ce problème apparemment simple, ce serait bien mathoverflow.net/questions/336369/… .
T ....
4

Hari Narayanan a récemment publié un article sur l'arXiv dans lequel il utilise l'estimation du volume d'un polytope convexe pour prouver certains résultats sur les coefficients de Littlewood-Richardson (LR). Les coefficients LR sont certains entiers dans la théorie de la représentation qui ont des applications dans la théorie de la complexité géométrique, la physique des particules et de nombreux autres domaines (voir l'introduction de l'article ci-dessus pour plus de références). Encore une fois, probablement pas exactement ce que vous vouliez, mais une connexion intéressante néanmoins.

Joshua Grochow
la source
3

voir par exemple: N-Dimensional Volume Estimation of Convex Bodies: Algorithms and Applications par Sharma, Prasanna, Aswal pour un exemple / étude de cas en prévision économique, c'est-à-dire la gestion de la chaîne d'approvisionnement.

Nos méthodes peuvent être utilisées pour quantifier le contenu et l'incertitude de l'information, dans les régions de contraintes, dans un cadre d'optimisation robuste. Nous montrons des applications dans la gestion de la chaîne d'approvisionnement, dans des conditions d'incertitude future.

Fondamentalement, l'idée est qu'un polytope peut modéliser un "scénario futur" de paramètres d'une configuration de gestion de la chaîne d'approvisionnement. l' incertitude (ou "erreur") dans le modèle / estimation est considérée comme proportionnelle au volume du ou des polytopes. voir les diapositives 3,4. cela permet alors:

  • estimation quantitative de l'incertitude
  • génération d'informations équivalentes
  • aide à l'analyse des hypothèses
vzn
la source
Je vous remercie. Ces exemples sont agréables, mais j'ai encore du mal à croire que c'est ce que l'on entend quand les gens disent que l'estimation du volume d'un corps convexe de grande dimension est l'une des applications les plus importantes de la méthode Markov Chain Monte Carlo.
convenu que l'exemple dans les diapositives est la "taille du jouet" en ce qui concerne le nombre de dimensions mais peut-être que certains problèmes de gestion de la chaîne d'approvisionnement ont de grandes dimensions dans la pratique. aussi cette ligne de recherche semble me suggérer qu'elle peut avoir une certaine application dans certaines formes de datamining.
vzn