On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling
We consider a multistage stochastic discrete program in which constraints on any stage might involve expectations that cannot be computed easily and are approximated by simulation. We study a sample average approximation (SAA) approach that uses nested sampling, in which at each stage, a number of s...
Saved in:
Main Authors: | , , , |
---|---|
Format: | Bài trích |
Language: | eng |
Published: |
Mathematical Programming
2021
|
Subjects: | |
Online Access: | https://link.springer.com/article/10.1007/s10107-020-01518-w https://dlib.phenikaa-uni.edu.vn/handle/PNK/2857 https://doi.org/10.1007/s10107-020-01518-w |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
id |
oai:localhost:PNK-2857 |
---|---|
record_format |
dspace |
spelling |
oai:localhost:PNK-28572022-08-17T05:54:48Z On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling Thuy Anh Ta Tien Mai Fabian Bastin Pierre L’Ecuyer Sample average approximation Multistage stochastic program Expected value constraints We consider a multistage stochastic discrete program in which constraints on any stage might involve expectations that cannot be computed easily and are approximated by simulation. We study a sample average approximation (SAA) approach that uses nested sampling, in which at each stage, a number of scenarios are examined and a number of simulation replications are performed for each scenario to estimate the next-stage constraints. This approach provides an approximate solution to the multistage problem. To establish the consistency of the SAA approach, we first consider a two-stage problem and show that in the second-stage problem, given a scenario, the optimal values and solutions of the SAA converge to those of the true problem with probability one when the sample sizes go to infinity. These convergence results do not hold uniformly over all possible scenarios for the second stage problem. We are nevertheless able to prove that the optimal values and solutions of the SAA converge to the true ones with probability one when the sample sizes at both stages increase to infinity. We also prove exponential convergence of the probability of a large deviation for the optimal value of the SAA, the true value of an optimal solution of the SAA, and the probability that any optimal solution to the SAA is an optimal solution of the true problem. All of these results can be extended to a multistage setting and we explain how to do it. 2021-09-14T07:14:54Z 2021-09-14T07:14:54Z 2021 Bài trích https://link.springer.com/article/10.1007/s10107-020-01518-w https://dlib.phenikaa-uni.edu.vn/handle/PNK/2857 https://doi.org/10.1007/s10107-020-01518-w eng Mathematical Programming |
institution |
Digital Phenikaa |
collection |
Digital Phenikaa |
language |
eng |
topic |
Sample average approximation Multistage stochastic program Expected value constraints |
spellingShingle |
Sample average approximation Multistage stochastic program Expected value constraints Thuy Anh Ta Tien Mai Fabian Bastin Pierre L’Ecuyer On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling |
description |
We consider a multistage stochastic discrete program in which constraints on any stage might involve expectations that cannot be computed easily and are approximated by simulation. We study a sample average approximation (SAA) approach that uses nested sampling, in which at each stage, a number of scenarios are examined and a number of simulation replications are performed for each scenario to estimate the next-stage constraints. This approach provides an approximate solution to the multistage problem. To establish the consistency of the SAA approach, we first consider a two-stage problem and show that in the second-stage problem, given a scenario, the optimal values and solutions of the SAA converge to those of the true problem with probability one when the sample sizes go to infinity. These convergence results do not hold uniformly over all possible scenarios for the second stage problem. We are nevertheless able to prove that the optimal values and solutions of the SAA converge to the true ones with probability one when the sample sizes at both stages increase to infinity. We also prove exponential convergence of the probability of a large deviation for the optimal value of the SAA, the true value of an optimal solution of the SAA, and the probability that any optimal solution to the SAA is an optimal solution of the true problem. All of these results can be extended to a multistage setting and we explain how to do it. |
format |
Bài trích |
author |
Thuy Anh Ta Tien Mai Fabian Bastin Pierre L’Ecuyer |
author_facet |
Thuy Anh Ta Tien Mai Fabian Bastin Pierre L’Ecuyer |
author_sort |
Thuy Anh Ta |
title |
On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling |
title_short |
On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling |
title_full |
On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling |
title_fullStr |
On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling |
title_full_unstemmed |
On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling |
title_sort |
on a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling |
publisher |
Mathematical Programming |
publishDate |
2021 |
url |
https://link.springer.com/article/10.1007/s10107-020-01518-w https://dlib.phenikaa-uni.edu.vn/handle/PNK/2857 https://doi.org/10.1007/s10107-020-01518-w |
_version_ |
1751856266295115776 |
score |
8.891145 |