(575e) Data-Driven Branch-and-Bound Algorithms for Optimization of Noisy Multi-Fidelity Simulation-Based Problems

As a result of the rapid development in modeling and computational capabilities, we are able to obtain high fidelity information from simulations of chemical processes that involve expensive function evaluations. Optimization of such complex systems often relies on the input-and-output data rather than traditional deterministic optimization techniques that require the algebraic equations and derivative information. One of the common data-driven optimization techniques is surrogate-based optimization¹. Surrogate-based optimization is typically an iterative process of updating and optimizing surrogate models with adaptive sampling strategies, aiming for better approximations and efficient exploration of the search space. There are two main challenges in surrogate-based optimization. Firstly, the surrogate models may vary when different samples or different surrogate models are used, which leads to different optimization results. Many efforts have been devoted towards finding the best surrogate modeling and sampling technique^1,2; however, the best surrogate model and sampling strategy is often a problem-dependent choice³. Secondly, unlike deterministic global optimization techniques, for data-driven optimization, global convergence can only be guaranteed when approaching the limit of infinite samples.

To address the two challenges discussed above, we have developed a novel data-driven spatial branch-and-bound algorithm (DDSBB) for box-constrained continuous black-box optimization problems⁴. Our algorithm takes a different approach to existing frameworks: instead of selecting and training the best surrogate model, imperfect surrogate models are fitted, bounded and utilized to search the space within a custom-based branch-and-bound framework. In previous work we have shown that error bounds and margins of the surrogate models, such as support vector regression and kriging, can be derived and the structure of traditional deterministic branch-and-bound algorithms can be adopted to develop a convergent algorithm.

In this work, we present recent methodological and algorithmic developments of our framework. We first explore various branching heuristics to accelerate the search, using ideas from gradient boosting algorithms. We also extend our framework to handle noisy or multi-fidelity data and constraints. Specifically, we show that we can use a feature selection technique to expedite the search by branching on the most critical variable⁵. Secondly, for expensive high-fidelity simulations, an overall surrogate model is trained as a low fidelity alternative for fast sampling and high-fidelity points are collected at local minima. Finally, constraints are handled by identifying the feasible region using different surrogate models. The improved DDSBB framework is tested on a variety of different scenarios (i.e., data-rich to data-poor, deterministic to stochastic problems) on a large set of benchmark problems and compared to current existing data-driven optimization solvers.

References：

1. McBride K, Sundmacher K. Overview of Surrogate Modeling in Chemical Process Engineering. Chemie Ingenieur Technik. 2019;91(3):228-239.
2. Bhosekar A, Ierapetritou M. Advances in surrogate based modeling, feasibility analysis, and optimization: A review. Computers & Chemical Engineering. 2018;108:250-267.
3. Rios LM, Sahinidis NV. Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization. 2013;56(3):1247-1293.
4. Zhai J, Boukouvala F. Data-driven Spatial Branch-and-bound Algorithms for Black-box Optimization. Proceedings of the 9th International Conference on Foundations of Computer-Aided Process Design. 2019.
5. Zhai J, Boukouvala F. Nonlinear Variable Selection Algorithms for Surrogate Modeling. AIChE Journal.0(ja):e16601.