I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO questions Uniformly Sampling from Convex Polytopes and Is it possible to sample uniformly on the surface of a high-dimensional polytope?. A bit of poking around Google Scholar hasn't turned anything up.
$\begingroup$
$\endgroup$
4
asked Jan 2, 2019 at 14:10
-
2$\begingroup$ I recently asked a question that turned out to be equivalent: cstheory.stackexchange.com/questions/42705/… I found some interesting references, but nothing definitive yet. $\endgroup$– Elle NajtCommented Apr 14, 2019 at 4:30
-
$\begingroup$ I think I was able to show it is NP-hard. Take a look and see if you believe my argument. :-) $\endgroup$– Elle NajtCommented Apr 20, 2019 at 5:17
-
1$\begingroup$ It is $NP$-hard. See updated answer. $\endgroup$– Elle NajtCommented Nov 13, 2019 at 0:22
-
$\begingroup$ @LorenzoNajt- Thanks for the update! $\endgroup$– Steve HuntsmanCommented Nov 13, 2019 at 15:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Here is one efficient approach, performing a random walk with a rapid mixing time, that has been implemented for a particular class of polytopes, but which might well be adaptable to a more general setting: Random Walks on the Vertices of Transportation Polytopes (2008).
answered Jan 2, 2019 at 14:44
-
$\begingroup$ Interesting bit from the first page: "Markov chain Monte Carlo (MCMC) has not been well explored as a means of sampling, or approximately counting, vertices of general polytopes." $\endgroup$ Commented Jan 2, 2019 at 14:52
-
$\begingroup$ ...and from the conclusions: "The question of whether we can sample vertices of a general [transportation polytope], when the number of sources is not constant, is still open." $\endgroup$ Commented Jan 2, 2019 at 14:53