Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Sample average approximation for stochastic nonconvex mixed integer nonlinear programming via outer-approximation
We propose a sample average approximation-based outer-approximation algorithm (SAAOA) that can address nonconvex two-stage stochastic programs (SP) with any continuous or discrete probability distributions. Previous work has considered this approach for convex two-stage SP (Wei and Realff in Comput Chem Eng 28(3):333–346, 2004). The SAAOA algorithm does internal sampling within a nonconvex outer-approximation algorithm where we iterate between a mixed-integer linear programming (MILP) master problem and a nonconvex nonlinear programming (NLP) subproblem. We prove that the optimal solutions and optimal value obtained by the SAAOA algorithm converge to the optimal solutions and the optimal value of the true SP problem as the sample size goes to infinity. The convergence rate is also given to estimate the sample size. Since the theoretical sample size estimate is too conservative in practice, we propose an SAAOA algorithm with confidence intervals for the upper bound and the lower bound at each iteration of the SAAOA algorithm. Two policies are proposed to update the sample sizes dynamically within the SAAOA algorithm with confidence intervals. The proposed algorithm works well for the special case of pure binary first stage variables and continuous stage two variables since in this case the nonconvex NLPs can be solved for each scenario independently. The proposed algorithm is tested with a stochastic pooling problem and is shown to outperform the external sampling approach where large scale MINLPs need to be solved.
Sample average approximation for stochastic nonconvex mixed integer nonlinear programming via outer-approximation
We propose a sample average approximation-based outer-approximation algorithm (SAAOA) that can address nonconvex two-stage stochastic programs (SP) with any continuous or discrete probability distributions. Previous work has considered this approach for convex two-stage SP (Wei and Realff in Comput Chem Eng 28(3):333–346, 2004). The SAAOA algorithm does internal sampling within a nonconvex outer-approximation algorithm where we iterate between a mixed-integer linear programming (MILP) master problem and a nonconvex nonlinear programming (NLP) subproblem. We prove that the optimal solutions and optimal value obtained by the SAAOA algorithm converge to the optimal solutions and the optimal value of the true SP problem as the sample size goes to infinity. The convergence rate is also given to estimate the sample size. Since the theoretical sample size estimate is too conservative in practice, we propose an SAAOA algorithm with confidence intervals for the upper bound and the lower bound at each iteration of the SAAOA algorithm. Two policies are proposed to update the sample sizes dynamically within the SAAOA algorithm with confidence intervals. The proposed algorithm works well for the special case of pure binary first stage variables and continuous stage two variables since in this case the nonconvex NLPs can be solved for each scenario independently. The proposed algorithm is tested with a stochastic pooling problem and is shown to outperform the external sampling approach where large scale MINLPs need to be solved.
Sample average approximation for stochastic nonconvex mixed integer nonlinear programming via outer-approximation
Optim Eng
Li, Can (Autor:in) / Bernal, David E. (Autor:in) / Furman, Kevin C. (Autor:in) / Duran, Marco A. (Autor:in) / Grossmann, Ignacio E. (Autor:in)
Optimization and Engineering ; 22 ; 1245-1273
01.09.2021
29 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Stochastic programming , Sample average approximation , Mixed-integer nonlinear programming , Outer-approximation Mathematics , Optimization , Engineering, general , Systems Theory, Control , Environmental Management , Operations Research/Decision Theory , Financial Engineering , Mathematics and Statistics
A mixed-integer approximation of robust optimization problems with mixed-integer adjustments
| Springer Verlag | 2024
Mixed-integer nonlinear programming 2018
| Online Contents | 2019
A mixed-integer approximation of robust optimization problems with mixed-integer adjustments
| Springer Verlag | 2024
Strong approximation for nonconvex set-valued maps
| British Library Online Contents | 2008