Motywacja do oszacowania objętości

12

Jakie są konkretne i przekonujące zastosowania do szacowania objętości wypukłych wielościanów tego rodzaju, rozważanych w nowszych artykułach na temat metod losowego chodzenia?

W tych pracach dotyczących szacowania objętości jako jedną z motywacji wymieniono integrację numeryczną. Jakie są przykłady całek, które ludzie chcą obliczać w praktyce, które są bardzo trudne do obliczenia przy użyciu poprzednich metod? A może jest jakaś inna ważna praktyczna aplikacja do obliczania objętości 1000-wymiarowego politopu?

cg.comp-geom na.numerical-analysis markov-chains

Zastanawiam się, czy uzyskasz więcej odpowiedzi typu, którego szukasz na physics.stackexchange.com ... Ponadto, dla tych z nas, którzy nie znają tego szczególnego podobszaru teorii, czy możesz podać jakieś odniesienia do „nowsze artykuły na temat metod losowego chodzenia”?

— Joshua Grochow

więcej przemyśleń na ten temat po udzieleniu odpowiedzi i przeszukiwaniu. niektóre prace wydają się wskazywać lub zmierzać w kierunku, że obliczanie objętości politopu jest czymś w rodzaju podstawowego problemu w teorii złożoności. nie jest to zaskakujące, biorąc pod uwagę, że obliczanie wyznacznika jest kolejnym kluczowym problemem w teorii złożoności, a wyznacznikiem jest objętość równoległościanu. jedną rozsądną odpowiedzią wydaje się być głębokie lub naturalne powiązania w teorii złożoności. więcej dowodów tego byłoby powiązanie z jakąś konkretną klasą złożoności .... może kopać więcej na ten temat ...

— dniu

zobacz także mathoverflow, algorytm znajdowania objętości złożonego politopu . tak, powyższe pytanie dotyczy aplikacji, a nie algorytmów, ale niektóre dokumenty dotyczące algorytmu podadzą motywacje / aplikacje.

— vzn

7

Oszacowanie objętości wypukłego politopu i ściśle powiązane zadanie próbkowania z niego ma zastosowania w prywatnym udostępnianiu danych.

Z grubsza problem, który chcesz rozwiązać, to: biorąc pod uwagę zbiór zapytań o wartości liczbowej w bazie danych, wymyśl odpowiedzi na te pytania, które są jak najbardziej zbliżone do rzeczywistych odpowiedzi, przy jednoczesnym zachowaniu zróżnicowanej prywatności. W niektórych zakresach parametrów optymalny algorytm rozwiązania tego problemu ma opis geometryczny, a jego wdrożenie obejmuje próbkowanie z wypukłego polytopa. Zobacz tutaj: http://arxiv.org/pdf/0907.3754v3.pdf

— Aaron Roth
źródło

4

$s$ $s$

W dziedzinie bezpieczeństwa komputerowego w pracy nad przepływem informacji ilościowych zastosowano te metody do oszacowania ilości poufnych informacji, które mogą wyciec przez określony program. Tutaj budujemy wielościan reprezentujący możliwe stany programu w określonym punkcie jego wykonania, a następnie chcemy oszacować coś o liczbie możliwych stanów (jest to związane z ilością uwolnionych informacji). Dlatego w pewnym momencie analizy próbują policzyć liczbę punktów całkowitych zawartych w wielościanie. Pachnie to związane z oszacowaniem objętości (dla mnie).

Oto wczesny artykuł, który jest reprezentatywny:

Automatyczne wykrywanie i kwantyfikacja wycieków informacji . Michael Backes, Boris Kopf, Andrey Rybalchenko. Bezpieczeństwo i prywatność IEEE 2009.

To powiedziawszy, może nie być dokładnie tym, czego szukasz. Wymaga to metod zliczania liczby punktów całkowitych wewnątrz wielościanu, która nie jest taka sama jak objętość wielościanu. Nie sądzę też, aby musieli analizować wielościany o wymiarze 1000 lub wyższym (choć nie jestem tego pewien).

— DW
źródło

Dziękuję Ci. Problem ze znalezieniem liczby całkowitych rozwiązań zbioru nierówności liniowych jest moim zdaniem # P-zupełny ( math.ucdavis.edu/~deloera/RECENT_WORK/semesterberichte.pdf ma również kilka innych zastosowań). Natomiast oszacowanie objętości można wykonać w czasie wieloczasowym. Najwyraźniej możesz użyć tego drugiego do przybliżenia pierwszego, ale naprawdę szukam bezpośrednich konkretnych zastosowań szacowania objętości.

Obliczenie objętości politopu jest również trudne do wykonania. Sam ten fakt niewiele mówi o przybliżeniach.

— Sasho Nikolov

P \neq B P P

$P\neq BPP$

1

@Turbo Oczywiście nie dowodzi to, że P nie jest równe BPP, ponieważ te dwie klasy nie dotyczą modelu Oracle. Uważam, że deterministyczne przybliżenie objętości polytopu reprezentowanego przez nierówności jest otwarte.

— Sasho Nikolov

@SashoNikolov Jeśli można wiedzieć to z pozoru prosty problem, że byłoby miło mathoverflow.net/questions/336369/... .

— T ....

4

Hari Narayanan niedawno opublikował artykuł na temat arXiv, w którym wykorzystuje szacowanie objętości wypukłego polytopa, aby udowodnić pewne wyniki dotyczące współczynników Littlewooda-Richardsona (LR). Współczynniki LR są pewnymi liczbami całkowitymi w teorii reprezentacji, które znajdują zastosowanie w teorii złożoności geometrycznej, fizyce cząstek i wielu innych dziedzinach (więcej informacji można znaleźć we wstępie do powyższej pracy). Znów, prawdopodobnie nie dokładnie to, czego chciałeś, ale mimo to ciekawe połączenie.

— Joshua Grochow
źródło

3

patrz np .: N-wymiarowe oszacowanie objętości wypukłych ciał: algorytmy i zastosowania Sharmy, Prasanny, Aswal dla przykładu / studium przypadku w prognozowaniu ekonomicznym, tj. zarządzaniu łańcuchem dostaw.

Nasze metody mogą być stosowane do ilościowego określania zawartości informacji i niepewności w regionach z ograniczeniami w solidnych ramach optymalizacji. Pokazujemy zastosowania w zarządzaniu łańcuchem dostaw w warunkach przyszłej niepewności.

w zasadzie chodzi o to, że polytope może modelować „przyszły scenariusz” parametrów konfiguracji zarządzania łańcuchem dostaw. niepewność (lub „error”) w modelu / szacowania jest traktowana jako proporcjonalna do objętości Polytope (S). patrz slajdy 3,4. to pozwala:

ilościowe oszacowanie niepewności
generowanie równoważnych informacji
pomoc w analizie „co jeśli”

— vzn
źródło

Dziękuję Ci. Te przykłady są fajne, ale nadal trudno mi uwierzyć, że mają na myśli, gdy ludzie mówią, że szacowanie objętości wielowymiarowego wypukłego ciała jest jednym z najważniejszych zastosowań metody Monte Carlo Markov Chain.

zgodził się, że przykład na slajdach to „rozmiar zabawki” w zakresie liczby wymiarów, ale być może niektóre problemy zarządzania łańcuchem dostaw mają w praktyce duże wymiary. również ta linia badań wydaje mi się sugerować, że może mieć pewne zastosowanie w niektórych formach analizy danych.

— vzn

2

$B_n$ $n$

Polytopy Birkhoffa, jądra ciepła i złożoność wykresów - Francisco Escolano, Edwin R. Hancock, Miguel A. Lozano, 2008

— vzn
źródło