Optimization Online


Sample Average Approximation for Stochastic Nonconvex Mixed Integer Nonlinear Programming via Outer Approximation

Can Li (canl1***at***cmu.edu)
David Bernal (bernalde***at***cmu.edu)
Kevin Furman (kevin.c.furman***at***exxonmobil.com)
Ignacio Grossmann (grossmann***at***cmu.edu)

Abstract: Stochastic mixed-integer 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 approximation-based outer approximation algorithm (SAAOA) that can address nonconvex two-stage 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 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.

Keywords: Stochastic programming, Sample Average Approximation, Mixed-integer Nonlinear Programming, Outer Approximation

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 12/09/2019
Entry Accepted: 12/10/2019
Entry Last Modified: 12/11/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society