Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.00547 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917586779766784 |
|---|---|
| author | Madhusudanarao, A Ch Singh, Rahul |
| author_facet | Madhusudanarao, A Ch Singh, Rahul |
| contents | We study chance constrained optimization problems $\min_x f(x)$ s.t. $P(\left\{ θ: g(x,θ)\le 0 \right\})\ge 1-ε$ where $ε\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 $\left\{μ:\frac{μ(y)}{ν(y)}\leq C, \forall y\inΘ, μ(y)\ge 0\right\}$, where $ν$ 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 $θ$ are drawn from $ν$, and the original constraint is replaced with $g(x,θ_i)\le 0,~i=1,2,\ldots,N$. We also derive the sample complexity associated with this approximation, i.e., for $ε,δ>0$ the number of samples which must be drawn from $ν$ so that with a probability greater than $1-δ$ (over the randomness of $ν$), the solution obtained by solving the sampled program yields an $ε$-feasible solution for the original chance constrained problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_00547 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On Learning for Ambiguous Chance Constrained Problems Madhusudanarao, A Ch Singh, Rahul Machine Learning Optimization and Control We study chance constrained optimization problems $\min_x f(x)$ s.t. $P(\left\{ θ: g(x,θ)\le 0 \right\})\ge 1-ε$ where $ε\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 $\left\{μ:\frac{μ(y)}{ν(y)}\leq C, \forall y\inΘ, μ(y)\ge 0\right\}$, where $ν$ 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 $θ$ are drawn from $ν$, and the original constraint is replaced with $g(x,θ_i)\le 0,~i=1,2,\ldots,N$. We also derive the sample complexity associated with this approximation, i.e., for $ε,δ>0$ the number of samples which must be drawn from $ν$ so that with a probability greater than $1-δ$ (over the randomness of $ν$), the solution obtained by solving the sampled program yields an $ε$-feasible solution for the original chance constrained problem. |
| title | On Learning for Ambiguous Chance Constrained Problems |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2401.00547 |