What is the typical method for sampling uniformly in a convex polytope

Question

The polytope in my case is the intersection of the k-plane $Ax=b$ and $\{x>0\}$ where $A$ is the constraint matrix and $b$ is some solution. I'd like to find a method that is fast and efficient for large dimensions of $x$, is there such a method?

The method I have now is basically a random walk, starting from an original solution $x_0$, jumping in a random direction, and checking if any of the constraints are violated, if so, reflecting over the boundary. This method works great for small dimensions in $x$, but if the dimensions get up to the 1000s with multiple constraints, it bogs down and takes days.

Answer 1

I think you will find that the problem of computing the volume of a convex polytope leads to sampling uniformly. Computing the volume is NP-hard, but there are approximation algorithms:

M. Dyer, A. Frieze, R. Kannan, "A random polynomial-time algorithm for approximating the volume of convex bodies," J. ACM 1991.

R. Kannan, L. Lovász, M. Simonovits, "Random walks and an $O^*(n^5)$ volume algorithm for convex bodies," Random structures and algorithms, 1997.

I think the $n^5$ time has since been reduced to $n^4$. As you can tell from the title of the Kannan paper, the main method is to perform a random walk.