Optimization Online


A Scalable Global Optimization Algorithm for Stochastic Nonlinear Programs

Yankai Cao(cao27***at***wisc.edu)
Victor Zavala(victor.zavala***at***wisc.edu)

Abstract: We propose a global optimization algorithm for stochastic nonlinear programs that uses a specialized spatial branch and bound (BB) strategy to exploit the nearly decomposable structure of the problem. In particular, at each node in the BB scheme, a lower bound is constructed by relaxing the so-called non-anticipativity constraints and an upper bound is constructed by fixing the first-stage variables to the current candidate solution. A key advantage of this approach is that both lower and upper bounds can be computed by solving individual scenario subproblems. Another key property of this approach is that we only need to perform branching on the first-stage variables to guarantee convergence (branching on the second-stage variables is performed implicitly during the computation of lower and upper bounds). The algorithm is implemented in SNGO in Julia and is interfaced to the modeling languages JuMP and Plasmo. Our implementation contains typical algorithmic features of global optimization solvers such as convexification, outer approximation, feasibility-based bound tightening, optimality-based bound tightening, and local search. Numerical experiments are performed using a stochastic optimization formulation for controller tuning, a parameter estimation formulation for microbial growth models, and a stochastic test set from GLOBALlib. We compare the computational results against SCIP and demonstrate that the new approach achieves significant speedups.

Keywords: Stochastic NLP Global Optimization Scalable

Category 1: Global Optimization

Category 2: Stochastic Programming

Citation: unpublished, submitted to Journal of Global Optimization. Department of Chemical and Biological Engineering, University of Wisconsin-Madison, 1415 Engineering Dr, Madison, WI 53706, USA, August 2017.

Download: [PDF]

Entry Submitted: 08/13/2017
Entry Accepted: 08/14/2017
Entry Last Modified: 08/13/2017

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