On sample average approximation for two-stage stochastic programs without relatively complete recourse
On sample average approximation for two-stage stochastic programs without relatively complete recourse
复制标题
无相对完全追索权的两阶段随机规划的样本平均近似
DOI：
--
复制
发表时间：
2019
影响因子：
2.7
通讯作者：
James R. Luedtke
中科院分区：
文献类型：
--
作者：
Rui Chen;James R. Luedtke
We investigate sample average approximation (SAA) for two-stage stochastic programs without relatively complete recourse, i.e., for problems in which there are first-stage feasible solutions that are not guaranteed to have a feasible recourse action. As a feasibility measure of the SAA solution, we consider the “recourse likelihood”, which is the probability that the solution has a feasible recourse action. For ϵ∈(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon \in (0,1)$$\end{document}, we demonstrate that the probability that a SAA solution has recourse likelihood below 1-ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-\epsilon $$\end{document} converges to zero exponentially fast with the sample size. Next, we analyze the rate of convergence of optimal solutions of the SAA to optimal solutions of the true problem for problems with a finite feasible region, such as bounded integer programming problems. For problems with non-finite feasible region, we propose modified “padded” SAA problems and demonstrate in two cases that such problems can yield, with high confidence, solutions that are certain to have a feasible recourse decision. Finally, we conduct a numerical study on a two-stage resource planning problem that illustrates the results, and also suggests there may be room for improvement in some of the theoretical analysis.
We investigate sample average approximation (SAA) for two-stage stochastic programs without relatively complete recourse, i.e., for problems in which there are first-stage feasible solutions that are not guaranteed to have a feasible recourse action. As a feasibility measure of the SAA solution, we consider the “recourse likelihood”, which is the probability that the solution has a feasible recourse action. For ϵ∈(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon \in (0,1)$$\end{document}, we demonstrate that the probability that a SAA solution has recourse likelihood below 1-ϵ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-\epsilon $$\end{document} converges to zero exponentially fast with the sample size. Next, we analyze the rate of convergence of optimal solutions of the SAA to optimal solutions of the true problem for problems with a finite feasible region, such as bounded integer programming problems. For problems with non-finite feasible region, we propose modified “padded” SAA problems and demonstrate in two cases that such problems can yield, with high confidence, solutions that are certain to have a feasible recourse decision. Finally, we conduct a numerical study on a two-stage resource planning problem that illustrates the results, and also suggests there may be room for improvement in some of the theoretical analysis.