4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
  • $\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$ – Steve Huntsman Jan 2 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$ – Steve Huntsman Jan 2 at 14:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.