Groupe d’études et de recherche en analyse des décisions


Global Stochastic Optimization with Low-Dispersion Point Sets

, et

This study concerns a generic model-free stochastic optimization problem requiring the minimization of a risk function defined on a given bounded domain in a Euclidean space. Smoothness assumptions regarding the risk function are hypothesized and members of the underlying space of probabilities are presumed subject to a large deviation principle; however, the risk function may well be non-convex and multimodal. A general approach to finding the risk minimizer on the basis of decision/observation pairs is proposed. It consists of repeatedly observing pairs over a collection of design points. Principles are derived for choosing the number of these design points on the basis of an observation budget, and for allocating the observations between these points both in pre-scheduled and adaptive settings. On the basis of these principles, large-deviation type bounds of the minimizer in terms of sample size are established.

, 24 pages