On Learning for Ambiguous Chance Constrained Problems

We study chance constrained optimization problems ${\min }_{x}f(x)$ s.t. $P(\{\theta :g(x,\theta )\le 0\})\ge 1-\epsilon$ where $\epsilon \in (0,1)$ is the violation probability, when the distribution $P$ is not known to the decision maker (DM). When the DM has access to a set of distributions $\mathcal{U}$ such that $P$ is contained in $\mathcal{U}$, then the problem is known as the ambiguous chance-constrained problem \cite{erdougan2006ambiguous}. We study ambiguous chance-constrained problem for the case when $\mathcal{U}$ is of the form $\{\mu :\frac{\mu (y)}{\nu (y)}\le C,\mathrm{\forall }y\in \mathrm{\Theta },\mu (y)\ge 0\}$, where $\nu$ is a reference distribution.'' We show that in this case the original problem can be well-approximated’’ by a sampled problem in which $N$ i.i.d. samples of $\theta$ are drawn from $\nu$, and the original constraint is replaced with $g(x,{\theta }_i)\le 0,i=1,2,\dots ,N$. We also derive the sample complexity associated with this approximation, i.e., for $\epsilon ,\delta >0$ the number of samples which must be drawn from $\nu$ so that with a probability greater than $1-\delta$ (over the randomness of $\nu$), the solution obtained by solving the sampled program yields an $\epsilon$-feasible solution for the original chance constrained problem.