# Uniform Sampling over Convex Polytope (not full-dimensional)

I want to simulate a uniform distribution on a convex polytope that is not full-dimensional for optimization purposes (to generate random points on the set I want to minimize over). The polytope is defined as follows:

$L_{83}:=\{(x_1,\cdots,x_{83})\in\mathbb{R}^{83}: 0 \leq x_i \leq o_i \ \forall i=1..83, \sum_{i=1}^{83} a_ix_i = C_1, \sum_{i=1}^{83} b_ix_i = C_2\} \neq \emptyset$ whereas $o_i$, $C_i$, $a_i$ and $b_i$ are given (non-zero) constants.

Does anyone have an idea how I can do this?

Thanks in advance!

• I have a wild guess (hence not an answer): 1) generate a random point in the hypercube. 2) project onto the equality constraints. 3) discard if the projection falls outside of the hypercube. (By "project", BTW, I do mean a true projection: the nearest point in Euclidean distance satisfying the equality constraints.) – Michael Grant Nov 17 '14 at 15:28
• There are some related questions on math overflow. Answers suggest doing a random walk, which seems simple to implement in your case, but bounding the mixing time seems complicated. – p.s. Nov 18 '14 at 4:14