8706

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Доклад

Название: 

On the Complexity of Randomized Approximations of Nonconvex Sets

ISBN/ISSN: 

978-1-4244-5354-2

Наименование конференции: 

  • 4th IEEE Multi-conference on Systems and Control (MSC 2010, Yokohama, Japan)

Наименование источника: 

  • Proceedings of the 4th IEEE Multi-Conference on Systems and Control (Yokohama, 2010)

Город: 

  • Yokohama

Издательство: 

  • IEEE International Symposium on

Год издания: 

2010

Страницы: 

1564-1569
Аннотация
We consider a nonconvex set X 2 Rn endowed with a probability measure P, and assume that random samples taken according to this measure are available. For " 2 (0 1), we say that the set A 2 Rn 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 hyperrectangles 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 chance-constrained 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.

Библиографическая ссылка: 

Dabbene F., Lagoa C. M., Щербаков П.С. On the Complexity of Randomized Approximations of Nonconvex Sets / Proceedings of the 4th IEEE Multi-Conference on Systems and Control (Yokohama, 2010). Yokohama: IEEE International Symposium on, 2010. С. 1564-1569.