(598d) Spatial Branch-and-Bound Optimization Using Surrogate Approximations

Zhai, J., Georgia Institute of Technology
Boukouvala, F., Georgia Institute of Technology
Data-driven modeling and optimization using surrogate approximations has drawn growing attention for the optimization of complex, multiscale chemical process systems [1]. Specifically, the involvement of multidisciplinary design objectives, computationally expensive simulations and costly physical experiments often hinder the attempts to find an accurate analytical model for these systems, which can be used for traditional derivative-based optimization. In these cases, surrogate modeling or metamodeling is often used to create analytical and cheap-to-evaluate models for design space exploration, model approximation, and global optimization [2-4]. Despite the widely available surrogate techniques and surrogate-based optimization algorithms, many methodologies do not guarantee optimality and are prone to the inconsistency caused by the selection of different surrogate models. Specifically, the challenge of data-driven DFO is to develop approaches that are capable to provide consistent convergence to good solutions, despite the lack of abundant data, and the uncertainty of not knowing the best approximation model for the underlying phenomena.

Common approahces in data-driven optimization iteratively update and optimize the surrogate models with adaptive sampling strategies aiming to speed up the search for better solutions. In this work, we propose new ideas for data-driven optimization, which aim to utilize the uncertainty and variability that unavoidably exists, to search the space efficiently. Specifically, several approaches are proposed that take advantage of statistical information from commonly used sampling strategies (i.e., space filling designs and sparse grids) and best performing surrogate models (i.e., support vector regression, kriging, and orthogonal polynomials), to derive over and under estimators that are used within a custom-based spatial branch-and-bound framework. Three specific ideas are explored and compared in this work. First, a purely machine-learning based approach, utilizes soft margin loss of support vector regression to approximate the over and under estimators and gradually tighten the search space until convergence. The second approach is based on the concept of quantifying the uncertainty of the fitted surrogate models to derive the upper/lower bounds using robust optimization. Finally, the third approach uses sparse grids, orthogonal polynomials and approximation error bounds to bound the surrogate predictions. Using the above three ideas, we develop a branch-and-bound algorithm, and heuristics that are based on data-driven analysis. Finally, we compare this spatial branch-and-bound framework with existing data-driven methods and provide results on the computational efficiency, sampling reuqirments and convergence on a general class of benchmark problems.


  • Chiang, L., B. Lu, and I. Castillo, Big Data Analytics in Chemical Engineering. Annual Review of Chemical and Biomolecular Engineering, 2017. 8(1): p. 63-85.
  • Wang, G.G. and S. Shan, Review of Metamodeling Techniques in Support of Engineering Design Optimization. Journal of Mechanical Design, 2006. 129(4): p. 370-380.
  • Bhosekar, A. and M. Ierapetritou, Advances in surrogate based modeling, feasibility analysis, and optimization: A review. Computers & Chemical Engineering, 2018. 108: p. 250-267.
  • Forrester, A.I.J. and A.J. Keane, Recent advances in surrogate-based optimization. Progress in Aerospace Sciences, 2009. 45(1): p. 50-79.
  • Bertsimas, D., V. Gupta, and N. Kallus, Data-driven robust optimization. Mathematical Programming, 2018. 167(2): p. 235-292.
  • Bungartz, H.-J. and M. Griebel, Sparse grids. Acta Numerica, 2004. 13: p. 147-269.