(234e) Global Convergence Analysis of Data-Driven Spatial Branch-and-Bound Algorithms

Recent advancements in computing resources and processing power have enabled us to computationally simulate complex systems [1]. These high-fidelity simulations help in qualitative analysis and decision making, however, often the objective functions and the constraints are available as black-box solvers [2-5]. Machine learning (ML) surrogate models are often employed to model these high-fidelity simulations and expedite the optimization process. Nevertheless, training these ML surrogates is a challenging task and building these models often requires large amount of data. Convergence of surrogate-based methods relies on the selection of a ML model, while small changes in initialization affects the optimal solution found, there is also no information provided on the quality of the incumbent solution found [2, 6, 7] . Furthermore, these ML model parameterizations are highly subjected to the available data and slight changes in the data leads to a different surrogate model parameterization [8]. To tackle these problems, we recently proposed a data-driven equivalent of the spatial branch-and-bound (DDSBB) algorithm based on the idea of constructing convex underestimators to the data from simulations. Since these underestimators are convex and are used as relaxations and when embedded into the b&b algorithm, the search space is progressively partitioned and pruned by branching and pruning heuristics [5, 8]. More recently, we also presented PyDDSBB – an open-source Python package of the DDSBB algorithm implementation.

So far, even though we have shown that the proposed approach is more consistent than other surrogate-based methods, we have only applied it in fully black-box scenarios and were unable to guarantee convergence to local and/or global optima of the underlying simulation. For these relaxations to be useful for global optimization, they must converge to the underlying black-box problem rapidly as the search space shrinks. Recent contributions in [9] investigate this for black-box functions on integer subsets but assume the convexity of the function on those integer subsets. Similarly, in [5], an analysis was performed for smooth, twice-continuously differentiable functions. Utilizing these ideas, in the current study, we present novel results on the global convergence of our PyDDSBB method, for special classes of low-dimensional simulation-based problems stemming from chemical process design, such optimization with embedded process flowsheets and partial differential equation models. We first study convergence properties of our algorithm for the class of convex black-box problems, with respect to number of samples required and computational cost. We also study the convergence properties of our approach as we vary the upper limit on the rate of change of the objective function (i.e., Lipschitz constant), again as a function of the samples collected. We also present how the use of a multifidelity approach using multiple ensemble surrogate predictions can affect the rate of convergence, sampling, and computational cost of our algorithm.

References

1. McBride, K. and K. Sundmacher, Overview of Surrogate Modeling in Chemical Process Engineering. Chemie Ingenieur Technik, 2019. 91(3): p. 228-239.
2. Boukouvala, F., R. Misener, and C.A. Floudas, Global optimization advances in Mixed-Integer Nonlinear Programming, MINLP, and Constrained Derivative-Free Optimization, CDFO. European Journal of Operational Research, 2016. 252(3): p. 701-727.
3. Rios, L.M. and N.V. Sahinidis, Derivative-free optimization: a review of algorithms and comparison of software implementations. Journal of Global Optimization, 2013. 56(3): p. 1247-1293.
4. Bhosekar, A. and M.G. Ierapetritou, Advances in surrogate based modeling, feasibility analysis, and optimization: A review. Comput. Chem. Eng., 2018. 108: p. 250-267.
5. Song, Y., et al., Bounding convex relaxations of process models from below by tractable black-box sampling. Computers & Chemical Engineering, 2021. 153: p. 107413.
6. Amaran, S., et al., Simulation optimization: a review of algorithms and applications. 4OR, 2014. 12(4): p. 301-333.
7. Hüllen, G., et al., Managing uncertainty in data-driven simulation-based optimization. Computers & Chemical Engineering, 2020. 136: p. 106519.
8. Zhai, J. and F. Boukouvala, Data-driven spatial branch-and-bound algorithms for box-constrained simulation-based optimization. Journal of Global Optimization, 2022. 82(1): p. 21-50.
9. Larson, J., et al., A method for convex black-box integer global optimization. Journal of Global Optimization, 2021. 80(2): p. 439-477.