On the complexity of randomized approximations of nonconvex sets

We consider a nonconvex set X ∈ ℝⁿ endowed with a probability measure P, and assume that random samples taken according to this measure are available. For ε ∈ (0; 1), we say that the set A ∈ ℝⁿ is an ε-probabilistic approximation of X if the probability of a point to belong to X and not to A is less than ε. In this paper, we show that a simple randomized algorithm returning with high probability convex ε-approximations of X can be easily devised. In particular, we consider different possible shapes for the set A, namely ellipsoids, hyperrectangles, and parallelotopes, and show how specific approximations based on such shapes can be constructed. Moreover, we derive explicit bounds on the complexity of such approximations, in terms of the number of samples needed in the different cases. It turns out that, while the complexity of ellipsoidal and parallelotopic approximations grow quadratically with respect to the dimension n, in the case of orthotopes one obtains linear dependence. The second part of the paper is devoted to the study of tighter approximations, based on recent results on the connection between chanceconstrained problems and scenario problems with discarded constraints. There are numerous applications of this result in systems and control theory; a specific motivation for the research conducted in this paper is the characterization of the reachable sets of nonlinear systems, and the related problem of nonlinear filtering.