Solved – Generating random vectors with constraints

random-generation

I need to create random vectors of real numbers a_i satisfying the following constraints:

abs(a_i) < c_i;      
sum(a_i)< A;        # sum of elements smaller than A
sum(b_i * a_i) < B; # weighted sum is smaller than B 
aT*A*a < D          # quadratic multiplication with A smaller than D

where c_i, b_i, A, B, D are constants.

What would be the typical algorithm to generate efficiently this kind of vector?

Best Answer

If I understand you correctly, only points in some small volume of n-dimensional space meet your constraints.

Your first constraint constrains it to the interior of a hypersphere, which reminds me of the comp.graphics.algorithms FAQ "Uniform random points on sphere" and How to generate uniformly distributed points in the 3-d unit ball? The second constraint slices a bit out of the hypersphere, and the other constraints further whittle away at the volume that meets your constraints.

I think the simplest thing to do is one of the approaches suggested by the FAQ:

  • choose some arbitrary Axis-aligned bounding box that we are sure contains the entire volume. In this case, -c < a_1 < c, -c < a_2 < c, ... -c < a_n < c contains the entire constrained volume, since it contains the hypersphere described by the first constraint, and the other constraints keep whittling away at that volume.
  • The algorithm uniformly picks points throughout that bounding box. In this case, the algorithm independently sets each coordinate of a candidate vector to some independent uniformly distributed random number from -c to +c. (I am assuming you want points distributed with equal density throughout this volume. I suppose you could make the algorithm select some or all coordinates with a Poisson distribution or some other non-uniform distribution, if you had some reason to do that).
  • Once you have a candidate vector, check each constraint. If it fails any of them, go back and pick another point.
  • Once you have a candidate vector, store it somewhere for later use.
  • If you don't have enough stored vectors, go back and try to generate another one.

With sufficiently high-quality random number generator, this gives you a set of stored coordinates that meet your criteria with (expected) uniform density.

Alas, if your have a relatively high dimensionality n (i.e., if you construct each vectors out of a relatively long list of coordinates), the inscribed sphere (much less your whittled-down volume) has a surprisingly small part of the total volume of the total bounding box, so it might need to execute many iterations, most of them generating rejected points outside your constrained area, before finding a point inside your constrained area. Since computers these days are pretty fast, will that be fast enough?

Related Question