Rejection sampling definitely works if you are able to find a superset $Q$ of the polytope $P$ from which you can sample. If you sample a point from that superset, the probability that it gets accepted is equal to the ratio $frac{text{Vol}(P)}{text{Vol}(Q)}$, so $Q$ should be as small as possible. For instance, it is sample to sample from $Q$ if it is a box or a ball.
In the case where the polytope is specified as a list of inequalities, finding the smallest enclosing ball can be quite hard.
Contrary to what Simon Barthelmé mentions, Boyd and Vandenberghe do not deal with this problem. Actually they deal with the case where the vertices of the polytope are available. Going from the list of inequalities to the set of vertices is also hard (I am actually looking for a MATLAB implementation of that).
One possible approach is to find a small box enclosing the polytope. The box is defined by a set of coordinates $(b_i^{text{min}},b_i^{text{max}}), i=1dots n$, and each coordinate can be found by :
$$ b_i^{text{min}} = arg min_x x_i quad text{subject to } A x leq b $$
$$ b_i^{text{max}}= arg max_x x_i quad text{subject to } A x leq b $$
Those are linear programs for which you can use your favourite solver.
No comments:
Post a Comment