Sample average approximation for stochastic nonconvex mixed integer nonlinear programming via outer-approximation
- PDF / 1,709,886 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 55 Downloads / 218 Views
Sample average approximation for stochastic nonconvex mixed integer nonlinear programming via outer‑approximation Can Li1 · David E. Bernal1 · Kevin C. Furman2 · Marco A. Duran · Ignacio E. Grossmann1 Received: 5 February 2020 / Revised: 7 September 2020 / Accepted: 7 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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. Keywords Stochastic programming · Sample average approximation · Mixed-integer nonlinear programming · Outer-approximation Marco A. Duran Deceased in 2018. Pioneer of outer-approximation algorithm for MINLP optimization. * Ignacio E. Grossmann [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
C. Li et al.
1 Introduction Mixed-integer nonlinear programming (MINLP) is a framework to model optimization problems that involve discrete and continuous variables and nonlinear constraints. Many applications can be modeled with MINLP, such as the pooling problem (Misener et al. 2011), batch plant design (Li and Grossmann 2018), and water network synthesis (Karuppiah and Grossmann 2008). Although there have been significant advances to solve deterministic MINLPs (Kronqvist et al. 2019), fewer works have been proposed to solve MINLP problems under uncertainty. Two-stage stochastic programming (SP) is a framework to model decisionmaking problems under uncertainty (Shapiro et al. 2009). Specifically, stage 1 decisions are made ‘here and now’ and are then followed by the resolution of uncertaint
Data Loading...
