Random Sampling a linearly constrained region in n-dimensions... - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T03:53:00Z http://mathoverflow.net/feeds/question/76255 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76255/random-sampling-a-linearly-constrained-region-in-n-dimensions Random Sampling a linearly constrained region in n-dimensions... user1 2011-09-24T02:26:21Z 2011-10-10T14:55:38Z <p>Hi,</p> <p>So here is my problem:</p> <p>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.</p> <p>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.</p> <p>I've tried finding the volume of the space analytically, however the complexity of computing the integral gets overwhelming for many dimensions. </p> <p>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?</p> <p>any help would be greatly appreciated...</p> http://mathoverflow.net/questions/76255/random-sampling-a-linearly-constrained-region-in-n-dimensions/76258#76258 Answer by Mike Spivey for Random Sampling a linearly constrained region in n-dimensions... Mike Spivey 2011-09-24T03:07:26Z 2011-09-24T03:19:53Z <p>Your constraints $x_n \geq 0$, $\sum_{n=1}^N x_n = 1$, are those for the <a href="http://en.wikipedia.org/wiki/Simplex#The_standard_simplex" rel="nofollow">standard simplex</a>. You could try <a href="http://www.cs.cmu.edu/~nasmith/papers/smith+tromble.tr04.pdf" rel="nofollow">uniform sampling from the standard simplex</a>, and then reject any sample that doesn't also satisfy the $x_n \leq c_n$ constraints.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Dirichlet_distribution#Random_number_generation" rel="nofollow">generating a random vector</a> from the symmetric <a href="http://en.wikipedia.org/wiki/Dirichlet_distribution" rel="nofollow">Dirichlet distribution</a>. (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.</p> http://mathoverflow.net/questions/76255/random-sampling-a-linearly-constrained-region-in-n-dimensions/76259#76259 Answer by Joseph O'Rourke for Random Sampling a linearly constrained region in n-dimensions... Joseph O'Rourke 2011-09-24T03:18:33Z 2011-09-25T01:26:21Z <p>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, (<a href="http://dl.acm.org/citation.cfm?id=1536491&amp;dl=ACM&amp;coll=DL&amp;CFID=45908046&amp;CFTOKEN=33917313" rel="nofollow">ACM link</a>) 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," (<a href="http://ioe.engin.umich.edu/techrprt/pdf/TR90-02.pdf" rel="nofollow">PDF</a>), or, perhaps better, Santosh Vempala's 2008 notes on <em>Algorithmic Convex Geometry</em> (<a href="http://www.cc.gatech.edu/~vempala/acg/notes.pdf" rel="nofollow">PDF</a>).</p> <p>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. </p> http://mathoverflow.net/questions/76255/random-sampling-a-linearly-constrained-region-in-n-dimensions/76275#76275 Answer by Igor Rivin for Random Sampling a linearly constrained region in n-dimensions... Igor Rivin 2011-09-24T15:30:34Z 2011-09-24T15:30:34Z <p>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.</p>