Random Points on Convex Sets (Superellipsoids)

• Aug 7th 2009, 09:08 AM
Zarathustra
Random Points on Convex Sets (Superellipsoids)
Hi.

I am trying to find a way to draw random points from convex sets in arbitrary dimensions. In particular, the sets are described by a continuous, differentiable, and quasiconvex function $g(x):\mathbb{R}_+^n \rightarrow \mathbb{R}$ such that the sets are given by $S = \{x \in \mathbb{R}_+^n: g(x) = 0\}$. So the problem is finding a random point in $S$ uniformly distributed on $S$, i.e. each point in $S$ is drawn with the same probability.

I reckon that the above problem is too general to admit an easy solution. But for my purposes, it would already be sufficient to find a way to randomly draw a point from sets given by $\{x \in \mathbb{R}_+^n: \sum_{i=1}^n a_i x_i^r = w\}$, with $r \geq 2$ (apparently, these sets are the boundaries of so called "superellipsoids").

Now, I do know how to draw random points uniformly distributed on spheres. I also know how to use that knowledge to draw random points uniformly distributed on ellipsoids, using a (rather inefficient) acception-rejection algorithm. But I am clueless about how to tackle the more general (second) problem described above.

Any help would be appreciated.

Cheers.