# 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 currently have a few ideas:

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)

## 3 comment threads