Efficient random sampling of constrained n-dimensional space

Question

I'm about to optimize a problem that is defined by n (n>=1, typically n=4) non-negative variables. This is not a n-dimensional problem since the sum of all the variables needs to be 1.

The most straightforward approach would be for each x_i to scan the entire range 0<=x_i<1, and then normalizing all the values to the sum of all the x's. However, this approach introduces redundancy, which is a problem for many optimization algorithms that rely on stochastic sampling of the solution space (genetic algorithm, taboo search and others). Is there any alternative algorithm that can perform this task?

What do I mean by redundancy?

Take two dimensional case as an example. Without the constrains, this would be a two-dimensional problem which would require optimizing two variables. However, due to the requirement that X1 + X2 == 0, one only needs to optimize one variable, since X2 is determined by X1 and vice versa. Had one decided to scan X1 and X2 independently and normalizing them to the sum of 1, then many solution candidates would have been identical vis-a-vis the problem. For example (X1==0.1, X2==0.1) is identical to (X1==0.5, X2==0.5).

Answer 1

If you are dealing with real valued variables then arriving with 2 samples that become identical is quite unlikely. However you do have the problem that your samples would not be uniform. You are much more likely to choose (0.5, 0.5) than (1.0, 0). Oneway of fixing this is subsampling. Basically what you do is that when you are shrinking space along a certain point, you shrink the probability of choosing it.

So basically what you are doing is mapping all the points that are inside the unit cube that satisfy that are in the same direction, map to a single points. These points in the same direction form a line. The longer the line, the larger the probability that you will choose the projected point. Hence you want to bias the probability of choosing a point by the inverse of the length of that line.

Here is the code that can do it(Assuming you are looking for x_is to sum up to 1):

while(true) {
      maximum = 0;
      norm = 0;
      sum = 0;
      for (i = 0; i < N; i++) {
         x[i] = random(0,1);
         maximum = max(x[i], max);
         sum += x[i];
         norm += x[i] * x[i];
      }
      norm = sqrt(norm);
      length_of_line = norm/maximum;
      sample_probability = 1/length_of_line;

      if (sum == 0 || random(0,1) > sample_probability) {
        continue;
      } else {
      for (i = 0; i < N; i++) {
         x[i] = x[i] /sum;
      } 
      return x;
    }