Sample points inside a bounded convex polytope

75 Views Asked by At

I'm trying to uniformly sample points inside a bounded convex polytope of the form:

$Ax = b$

$0 \leq x \leq 1$

where $A = m \times n$ matrix ($n > m$).

I found a hit-and-run solution posted here. The first step suggests to start with a point inside the polytope. I wasn't sure how to do this, so my first thought was to use optimization and set the cost function to 0 to find an initial random solution inside the polytope. This got me thinking, why can't I run an optimization with a cost function set to 0 iteratively using a random initial guess each time to randomly (and presumably uniformly) sample points within this constrained problem? Well, I tried doing that in Python for a simple 2D example ($x_1 - x_2 = 0$) (using method='trust-constr' in scipy.optimize). And, I found that the random solutions were not uniformly sampled across the line but concentrated towards the middle. So I guess I had 2 questions:

  1. Why is it that the optimization solutions did not uniformly distribute across the constrained problem even though the cost function was set to 0?
  2. Asides from optimization, are there any other methods to find a single random solution inside the bounded convex polytope?

EDIT: I think I figured out an answer for question #2. I was able to figure out that an underdetermined system can be written as an augmented matrix, calculate the row reduced echelon form, get the null space basis vectors, and identifying a general solution from which you could substitute values for the free variables to get a particular solution. Feel free to correct me if I'm incorrect.

Apologize if these questions are too basic, I know some basic linear algebra but I kind of learn as I go and require to solve problems.