Welche konkreten und überzeugenden Anwendungen zur Abschätzung des Volumens von konvexen Polyedern wurden in den neueren Arbeiten zu Random-Walk-Methoden untersucht?
Diese Arbeiten zur Volumenschätzung erwähnen die numerische Integration als eine Motivation. Was sind Beispiele für Integrale, die Menschen in der Praxis berechnen möchten und die mit früheren Methoden nur sehr schwer zu berechnen sind? Oder gibt es eine andere überzeugende praktische Anwendung zur Berechnung des Volumens eines 1000-dimensionalen Polytops?
Antworten:
Die Schätzung des Volumens eines konvexen Polytops und die damit verbundene Aufgabe der Probenahme aus diesem Polytop finden in der privaten Datenfreigabe Anwendung.
Das grobe Problem, das Sie lösen möchten, ist: Wenn Sie eine Sammlung von numerisch bewerteten Abfragen in einer Datenbank haben, finden Sie Antworten auf Fragen, die den tatsächlichen Antworten so nahe wie möglich kommen und gleichzeitig die unterschiedliche Vertraulichkeit gewährleisten. In einigen Bereichen von Parametern hat der optimale Algorithmus zur Lösung dieses Problems eine geometrische Beschreibung, und zur Implementierung wird von einem konvexen Polytop abgetastet. Siehe hier: http://arxiv.org/pdf/0907.3754v3.pdf
quelle
Bei der Arbeit an quantitativen Informationsflüssen im Bereich der Computersicherheit wurden diese Methoden angewendet, um die Menge an vertraulichen Informationen abzuschätzen, die möglicherweise von einem bestimmten Programm übertragen werden. Hier erstellen wir ein Polyeder, das mögliche Zustände des Programms zu einem bestimmten Zeitpunkt seiner Ausführung darstellt, und möchten dann etwas über die Anzahl der möglichen Zustände abschätzen (dies hängt mit der Menge der freigegebenen Informationen zusammen). Daher versuchen sie an einem bestimmten Punkt in der Analyse, die Anzahl der im Polyeder enthaltenen ganzzahligen Punkte zu zählen. Das riecht nach Volumenschätzung (für mich).
Hier ist eine frühe Veröffentlichung, die repräsentativ ist:
Dies ist jedoch möglicherweise nicht genau das, wonach Sie suchen. Es sind Methoden erforderlich, um die Anzahl der Ganzzahlpunkte innerhalb des Polyeders zu zählen, die nicht dem Volumen des Polyeders entspricht. Ich glaube auch nicht, dass sie Polyeder der Dimension 1000 oder höher analysieren müssen (obwohl ich mir nicht sicher bin).
quelle
Hari Narayanan hat kürzlich einen Artikel über das arXiv veröffentlicht, in dem er das Volumen eines konvexen Polytops schätzt, um bestimmte Ergebnisse über die Littlewood-Richardson (LR) -Koeffizienten zu belegen. Die LR-Koeffizienten sind bestimmte ganze Zahlen in der Darstellungstheorie, die in der geometrischen Komplexitätstheorie, der Teilchenphysik und vielen anderen Bereichen Anwendung finden (weitere Referenzen finden Sie in der Einleitung des obigen Dokuments). Wiederum wahrscheinlich nicht genau das, was Sie wollten, aber dennoch eine interessante Verbindung.
quelle
siehe zB: N-dimensionale Volumenschätzung von konvexen Körpern: Algorithmen und Anwendungen von Sharma, Prasanna, Aswal für ein Beispiel / eine Fallstudie zur Wirtschaftsprognose, dh zum Lieferkettenmanagement.
Grundsätzlich besteht die Idee darin, dass ein Polytop ein "Zukunftsszenario" von Parametern einer Supply-Chain-Management-Konfiguration modellieren kann. das Unsicherheit (oder der "Fehler") im Modell / in der Schätzung wird als proportional zum Volumen des / der Polytope (s) angesehen. siehe Folien 3,4. das erlaubt dann:
quelle
Birkhoff-Polytope, Wärmekerne und Graphkomplexität von Francisco Escolano, Edwin R. Hancock, Miguel A. Lozano, 2008
quelle