Stochastic mixed-integer nonlinear programming (MINLP) is a very challenging class of problems. In particular, engineering design problems can be posed using this mathematical programming paradigm. Although there have been recent advances in developing decomposition algorithms to solve stochastic MINLPs [1-4], none of the existing algorithms can address stochastic nonconvex MINLPs with continuous distributions. 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 [5]. 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. However, the theoretical sample size estimate is too conservative in practice. Therefore, 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.
References
[1] Li, X., Tomasgard, A., Barton, P.I.: Nonconvex generalized benders decom-position for stochastic separable mixed-integer nonlinear programs. Journal of Optimization Theory and Applications151(3), 425 (2011)
[2] Cao, Y., Zavala, V.M.: A scalable global optimization algorithm for stochastic nonlinear programs. Journal of Global Optimization75(2), 393–416(2019)
[3] Kannan, R.: Algorithms, analysis and software for the global optimization of two-stage stochastic programs. Ph.D. thesis, Massachusetts Institute of Technology (2018)
[4] Li, C., Grossmann, I.E.: A generalized benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables. Journal of Global Optimization pp. 1–26 (2019)
[5] Wei, J., Realff, M.J.: Sample average approximation methods for stochastic MINLPs. Computers & Chemical Engineering 28(3), 333–346 (2004)
