  


Sample Average Approximation for Stochastic Nonconvex Mixed Integer Nonlinear Programming via Outer Approximation
Can Li (canl1cmu.edu) Abstract: Stochastic mixedinteger nonlinear programming (MINLP) is a very challenging type of problem. Although there have been recent advances in developing decomposition algorithms to solve stochastic MINLPs, none of the existing algorithms can address stochastic MINLPs with continuous distributions. We propose a sample average approximationbased outer approximation algorithm (SAAOA) that can address nonconvex twostage stochastic programs (SP) with any continuous or discrete probability distributions. The SAAOA algorithm does internal sampling within a nonconvex outer approximation algorithm where we iterate between a mixedinteger 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. Keywords: Stochastic programming, Sample Average Approximation, Mixedinteger Nonlinear Programming, Outer Approximation Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Stochastic Programming Citation: Download: [PDF] Entry Submitted: 12/09/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  