Random Sampling a linearly constrained region in n-dimensions... - MathOverflow

Random Sampling a linearly constrained region in n-dimensions...

2011-09-24T02:26:21Z

Hi,

So here is my problem:

Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an optimal (local) solution by randomly sampling the feasible region. $c_n$ are just constants.

The issue I am having is indexing the space, since it is not a simple n-dimensional cube but rather a polytope(i believe its convex). Discretizing and enumerating all possible combinations of points to sample is much too hard since N =20. Approximating the polytope with a n-dimensional cube and sampling from the cube, only about 1% of the samples fall within the feasible region...which is inefficient if I'm trying to generate many samples.

I've tried finding the volume of the space analytically, however the complexity of computing the integral gets overwhelming for many dimensions.

I was wondering if anyone has come across this type of problem and has any recommendation as to different methods I could try to sample this space. Essentially, I need a good way to estimate the volume...am I looking at this the correct way?

any help would be greatly appreciated...

Answer by Mike Spivey for Random Sampling a linearly constrained region in n-dimensions...

2011-09-24T03:07:26Z

Your constraints $x_n \geq 0$, $\sum_{n=1}^N x_n = 1$, are those for the standard simplex. You could try uniform sampling from the standard simplex, and then reject any sample that doesn't also satisfy the $x_n \leq c_n$ constraints.

An alternative to the procedure described in the linked paper above for uniform sampling from the standard simplex is to generate $n$ exponential(1) random variables $X_1, X_2, \ldots, X_n$ and let $Y_i = X_i/\sum_{i=1}^n X_i$. Then $(Y_1,Y_2,\ldots,Y_n)$ is uniformly distributed on the standard simplex. This can be thought of as generating a random vector from the symmetric Dirichlet distribution. (Also, generating exponential(1) random variables is easy; if $Z \sim U(0,1)$ then $-\ln(Z)$ has an exponential(1) distribution.) Once again, you would then reject any sample that doesn't also satisfy the $x_n \leq c_n$ constraints.

Answer by Joseph O'Rourke for Random Sampling a linearly constrained region in n-dimensions...

2011-09-24T03:18:33Z

I believe the primary method to generate uniform samples in convex polytopes is via a Markov-chain random walk. For example, the paper by Ravi Kannan and Hariharan Narayanan, "Random walks on polytopes and an affine interior point method for linear programming," STOC 2009, (ACM link) achieves a strongly polynomial mixing time. The basic idea is explained in these older notes by H.E. Romeijn and R.L Smith, "Sampling through Random Walks," (PDF), or, perhaps better, Santosh Vempala's 2008 notes on Algorithmic Convex Geometry (PDF).

The Kannan-Narayanan paper gives a condensed history of algorithms to find (approximately) the volume of a convex polytope, starting from the Dyer, Frieze, and Kannan paper from 1991 whose mixing time was $O(n^{23})$ for a polytope in $\mathbb{R}^n$, through a series of steady improvements reducing the dependency on $n$ down to closer to $n^2$. I am not certain this is the latest word on this topic.

Answer by Igor Rivin for Random Sampling a linearly constrained region in n-dimensions...

2011-09-24T15:30:34Z

If the $c_n$ are sufficiently small (say, all smaller than $1/\sqrt{n}$) or sufficiently large (say, all at least $1$) the polytope is a simplex, so estimating the volume and sampling are both easy as pointed out in @Mike's answer. On the other hand, trying to find a local optimum by uniform sampling is doomed in $20$-dimensional space, since the distance between the samples will be very large for any reasonable number of samples. (for example, if your polytope were a cube of side one, generating $2^{40}$ points will have inter point distances around $1/4.$ Needless to say, generating $2^{40}$ points might take a while.