(598d) Spatial Branch-and-Bound Optimization Using Surrogate Approximations
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.