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…
Best Answer
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.