A sample approximation approach for optimization with probabilistic constraints. (English) Zbl 1177.90301

Consider the optimisation problem with probabilistic constraints (P\(_\varepsilon\)) \[ z_\varepsilon^*=\min\{f(x):\;x\in X_\varepsilon\} \;, \] where \[ X_\varepsilon =\big\{ x\in X:\;P\{G(x,\xi)\leq 0\}\geq 1-\varepsilon\big\} \;, \] \(X\in\mathbb{R}^n\) is a deterministic feasible region, \(f: \mathbb{R}^n\to \mathbb{R}\), \(\xi\) is a random \(d\)-dimensional vector, and \(G: \mathbb{R}^n\times\mathbb{R}^d\to\mathbb{R}^m\). Motivated by the difficulty to compute \(P\{G(x,\xi)\geq 0\}\), problem (P\(_\varepsilon\)) is approximated by problem (P\(_\alpha^N\)) defined as \[ \hat z_\alpha^N=\min\{f(x):\;x\in X_\alpha^N\} \;, \] where \[ X_\alpha^N =\Big\{ x\in X:\;\frac{1}{N}\sum_{i=1}^N {\mathbf 1}_{\{G(x,\xi^i\leq 0\}}\geq 1-\alpha\Big\} \;, \] and \(\xi^1,\dots,\xi^N\) is a simulated sample of \(\xi\). When \(\alpha>\varepsilon\), \[ P\{\hat z_\alpha^N \leq z_\varepsilon^*\}\geq 1-\exp\{-2N(\alpha-\varepsilon)^2\} \;, \] thus a lower bound of the original true optimal value is obtained with a probability approaching 1 exponentially fast as the sample size increases. \(N\) can be easily computed to obtain the lower bound with a specified probability. On the other hand, if \(X\) is a finite set and \(\alpha<\varepsilon\), then \[ P\{X_\alpha^N \subseteq X_\varepsilon\}\geq 1-|X-X_\varepsilon| \exp\{-2N(\varepsilon-\alpha)^2\} \;, \] with \(|\cdot|\) denoting cardinality, so that the probability that every feasible solution to (P\(_\alpha^N\)) be a feasible solution of (P\(_\varepsilon\)) also approaches exponentially to 1 as \(N\) increases. A similar result can be obtained when \(X\) is not finite if \(G(x,\xi)=\xi-g(x)\) or \(G\) is Lipschitz in the first variable, uniformly in the second.
Numerical experiments have been conducted on probabilistically constrained versions of the Set Covering Problem and the Transportation Problem, and are presented in detail.
One remarkable contribution of this paper is the survey of previous related results contained in the introduction. The case and the novelties of the paper are clearly related to previous work.


90C15 Stochastic programming


SUTIL; OR-Library
Full Text: DOI Link