0
$\begingroup$

As far as I know, the most popular way to sample from a polytope (in H-representation) \begin{equation} \mathcal{P} := \{z \in \mathbb{R}^n | (Az)_j \le b_j\; \forall j=1,2,\ldots,m\} \end{equation} is to do rejection-sampling using it's bounding box $\mathcal{B}(\mathcal{P}) = \prod_{1 \le i \le n}[\alpha_i, \beta_i]$, i.e smallest axes-aligned box containing the polytope. The $\alpha_i$'s and $\beta_i$'s can be obtained by solving linear programs (see for example this answer to a similar question). However, my intuition is that, as the number of constraints $m$ goes to infinity, the polytope $\mathcal{P}$ "thins out" (i.e it's mass gets sharply concentrated along only a few number of dimensions) and the ratio of the volume $\mathcal{P}$ to the volume of $\mathcal{B}(\mathcal{P})$ "probably" goes to $0$. So, in this limiting case, rejection-sampling using $\mathcal{B}$, is very ineffective (almost all drawn points will be rejected).

Alternatively, one can try to enclose $\mathcal{P}$ in an ellipsoid, as this should have a "tighter grip", but then we must solve a quadratic program to find this conic (prohibitive).

Therefore, my question is: are there alternative efficient ways to sample from a polytope, which don't suffer the problems sketched above for large $m$ ?

$\endgroup$
3
  • $\begingroup$ @DavidEppstein: This is no duplicate. The question you're pointing to was properly referenced in my question. Did you even read it ? $\endgroup$
    – dohmatob
    Nov 12, 2015 at 8:25
  • $\begingroup$ And the answer to your question is already given in that one: use random walks. $\endgroup$ Nov 12, 2015 at 8:26
  • $\begingroup$ Thanks for the pointers. It seems these random-walk-based methods make calls to sub-oracles for enclosing and sampling from ellipsoids, etc (see for example arxiv.org/pdf/1312.2873v2.pdf), in which case don't qualify for what I'm looking for (read question above...). But I may be wrong. Maybe this sampling problem is just intricately difficult, but before I give up, I want to convince my self that we can't do better than rely on oracles based on bounding boxes and ellipsoids. Also, any pointers to state-of-the-art algorithms using the RW method are welcome. $\endgroup$
    – dohmatob
    Nov 12, 2015 at 8:42

0