How do I (efficiently) sample from the interior of a convex polytope?

I wish to sample a "typical" point in the interior of a convex polytope. The volume is defined by vectors $\vec{G}_k$ and values $v_k$ such that $\forall k,(\vec{X} \cdot \vec{G}_k) > v_k$. However, I also have an additional point $\vec{X}_j$ which is guaranteed to be on the boundary of the convex polytope normal to the vector $\vec{G}_j$ .

I could use the Metropolis-Hastings algorithm, which would start with $\vec{X}_j$ and perturb it with a normal distribution, accepting the new point if it stays in the interior of the convex shape, until it "looks right"? But I don't know how many samples I would need to process until that occurs, nor the hyperparameters to use?

I could also try perturbing $\vec{X}_j$ in the direction of $\vec{G}_j$, which would push the point away from the boundary of the shape?

(This is also in a very high dimensional space, of about 100,000 - but the exact number isn't too important)

is a duplicate

This question has been asked before and has already been answered. It should be marked as a duplicate.

Please enter the URL of the proposed duplicate in the details field below.

not constructive

This question cannot be answered in a way that is helpful to anyone. It's not possible to learn something from possible answers, except for the solution for the specific problem of the asker.

Communities

How do I (efficiently) sample from the interior of a convex polytope?

3 comment threads

0 answers