My notesUpdate 2:
My feeling There is that this sampling problem might be NP-hard, possibly by finding some polynomial size representation of the convex hull of the indicators of some set of objects that are hard to approximately uniformly sample, and then appealing to some known casea 2 line proof of the Mihail-Vazirani conjecture on $0/1$ polytopes.$NP$-hardness (As Heng Guo points out below, this strategy is unlikely to be successful, because if we can describegiven the right combinatorial polytope (polynomially) we can optimize over it, and even then the degrees of the vertices can vary exponentiallyI was able to find it an article by Khachiyan. Another strategySee answer for hardness might be to engineer a polytope such that the neighbors of a vertex give a hard uniform sampling problemdescription and link.) :-D
This formulation of the question has been asked before: https://mathoverflow.net/questions/319930/sampling-uniformly-from-the-vertices-of-a-polytope
I've started to feel that the problem of uniformly sampling from the vertices of a polytope is equivalent to approximately computing the vertex centroid (the average of all vertices).
(I will give a reference that it is hard to approximate the vertex centroid below. I misunderstood, the reference only proves this for unbounded polyhedra.)
If we could sample the vertices, then we could estimate the vertex centroid by averaging them. (I'm happy to assume that all the points are in $[0,1]^n$, so the empirical means concentrate rapidly by Hoeffding's.)
Via the trick in Theorem 1 from https://arxiv.org/pdf/0806.3456.pdf , one can turn an approximation for the vertex centroid into an approximation for the number of vertices. (I think that approximation needs to be extremely good to avoid blow-up in error, so this may not give a reduction.)
Is it known to be $\# P$ hard to approximate the vertices of a polytope?
This paper (from 2016) says:
To the best of our knowledge, the problem of estimating the number of vertices of a convex polytope does not have a FPRAS. That is, for this particular problem, an efficient randomized approximation algorithm is not known to exist.
In the other direction, here are a few ideas for going from the vertex centroid to sampling. None of these work efficiently in generality.
1. Picking a good distribution over functionals:
This doesn't appear to generalize past the simplest cases, but maybe there is a way to save it.
For every polytope, define a point in it called the 'magic'-centroid.
Algorithm: Translate the polytope so the 'magic'-centroid is at the origin. Pick an approximately uniform point $p$ from the (translated polytope). Output the maximizer to $f_p(x) = p \cdot x$.
Call a point a magic centroid if this algorithm outputs an approximately uniform distribution over the vertices.
For simple shapes (e..g line segments, rectangles, anything with vertex transitive symmetry group...) the vertex centroid is a magic centroid. This doesn't appear to generalize past these simple cases -- irregular 2D polygons already provide examples where the vertex centroid isn't a magic centroid (and neither is the center of gravity). In fact, I think many irregular 2D polygons provide examples where there cannot be a magic centroid.
- If you can approximate the vertex centroid, you can use the trick in Theorem 1 of https://arxiv.org/pdf/0806.3456.pdf to approximate the number of vertices in the polytope, and then use the algorithm described here: https://pdfs.semanticscholar.org/3fff/d6a1f29e668448901ef07313f7a65495395a.pdf
On the other hand, in that article Pak writes:
Note that when faster approximation algorithms are available, one can use them in place of a counting oracle everywhere when determining which hyperplane to use. But the probabilities must be determined by the precise counting oracle since the errors will blow up otherwise.
I think his point is that while there only $d$ iterations, so the blow up in error per element is like $(1 - \epsilon)^d$, since there exponentially many elements, $\epsilon$ needs to be exponentially small in order to sample from an approximately uniform distribution.
- For polytopes defined as the convex hull of indicators of some collection $\mathscr{S}(E)$ of subsets of a set $E$, the vertex-centroid records the marginals: for a given $e \in E$, the probability that a uniformly chosen element of $\mathscr{S}(E)$ contains $e$. For a self-reducible structure $S$, describing the collection $\mathscr{S}$ over all input, this is enough to sample uniformly from $\mathscr{S}(E)$.
So, if you could prove that you could always compute the vertex centroid (for the class of polytopes arising from the problem $S$), then you could uniformly sample the vertexes.
I think any errors also blow up here the way they would for using an approximate count of $\mathscr{S}(E)$ in Pak's article.
- I also thought a bit about sampling random basis of the matrix $A$ (assuming the polytope is in equational form $Ax = b$, $x \geq 0$), using the basis exchange Markov chain (which is known to mix rapidly). This has two problems that make it unusable in many situations: 1) The probability that a basis gives a basic feasible solution is potentially extremely low 2) Basic feasible solutions (especially those with many zeros) correspond to lots of basis.
However for non-degenerate polytopes the second problem goes away, and I have some numerical evidence that 1) isn't always as big a problem as it could for some distributions over polytopes ... for random (say, absolute value of Gaussian) entries, this would amount to estimating the number vertices in a random polytope of the form $Ax = b$, $x \geq 0$ (since every set of columns of the right size is a basis). For the models I coded on my computer, this acceptance rate decays with the dimension, of course, but (for some models) not nearly as rapidly as one might expect...
(Most polytopes were it would be interesting to sample the vertices are highly degenerate, however...)
Notes on computational complexity of computing centroids:
There appear to be at least two kinds of centroid in higher dimensions: the center of gravity, and the vertex-centroid (which is the average of the vertices).
Exact computation of the center of gravity is $\sharp P$ hard (see this paper) , but it can be efficiently approximated because points in the polytope can be approximately sampled.
On the other hand, even approximating the vertex-centroid of a polyhedron is already hard -- see this paper.
The hardness of approximating the vertex-centroid may give an answer to this question - if you can uniformly sample the vertices then you can presumably approximate the centroid. However, the authors of that paper only prove their result for unbounded polyhedrons, and it's unclear if it extends to polytopes.
Even though we do not have any idea about the complexity of approximating the centroid of a polytope, now we show that for an arbitrary unbounded polyhedron the vertex centroid can not approximated ... unless P = NP.
On the other hand, *this appears to answer this question for general polyhedra, with some bound on the location of the vertices: it's $NP$ hard to approximately uniformly sample from the vertices of a polyhedra -- provided the vertices are bounded appropriately, so you can guarantee that the averages concentrate rapidly enough. (I not 100 percent sure about this - will have to go and understand their paper.)
