(104h) Surrogate-Based Optimization for Box-Constrained Black-Box Systems Via k-Means Clustering

In a bid to remain competitive during the current era of smart manufacturing, optimization of various industrial process objectives has been becoming increasingly necessary. While high-fidelity digital twins and commercial simulators allow accurate modeling and simulation of intricate process operations, such models are often black-box providing negligible idea of the underlying variable relationships and gradient information. Clearly, global optimization of such black-box systems is extremely challenging. Derivative-free optimization techniques such as meta-heuristics and geometric partitioning techniques have been used extensively for such systems, however they cannot guarantee a global solution. Moreover, they typically require many model runs or evaluations, which may be extremely computationally prohibitive for optimizing complex systems. Data-driven surrogate models offer a computationally cheaper alternative to their high-fidelity counterparts by approximating the functional relationships between the system inputs and outputs by means of response surfaces. This has prompted numerous works, including review articles (Boukouvala and Ierapetritou, 2013; Garud et al., 2019; Regis and Shoemaker, 2007; Rios and Sahinidis, 2013) on surrogate-based optimization (SBO) techniques to assist global optimization of black-box systems at limited computational expense. A recent work (Garud et al., 2019) from our group had proposed an SBO framework for global optimization of box-constrained black-box systems. The framework iteratively optimizes a surrogate using a gradient-based optimization solver, while refining and improving the surrogate via an adaptive sampling technique in each iteration. The adaptive sampling process partitions the input domain using delaunay triangulations, and adds a new sample point in a favorable triangulation by balancing exploration and exploitation. While exploration aims to globally explore the design space uniformly, exploitation aims to locally focus near the nonlinear regions which can possibly host some optima. The primary limitation of the framework was the large computational expense of constructing delaunay triangulations, especially in higher-order (>5) dimensional space with many sample points. Also, the framework uses a fixed, periodic sequence of weights to balance exploration and exploitation in successive iterations. Such a heuristic might not necessarily work well for all scenarios. Thus, multiple SBO runs with different set of periodic weights may be required, which may increase the computational expense.

In order to reduce the computational burden of the framework, this work proposes a simple, yet effective SBO strategy for box-constrained black-box systems. Starting with an initial data set, a surrogate model is first constructed, and then updated subsequently by adding new data points iteratively. At any iteration, k-means clustering technique creates a few data clusters in the design space. Then, two sample points are added to account for exploration and exploitation, separately. The first point is simply added by Monte-Carlo technique in pursuit of filling the design space iteratively, while the second point is identified as a convex combination of all points of the cluster which hosts the current optima (exploitation). This iterative process continues until a stopping criterion of maximum sample points is met. Our algorithm does not entail partitioning of the input space by delaunay triangulations, and can be applied on large dimensional systems. The performance of our algorithm was evaluated on various data sets generated from a suite of complex, multimodal test functions with dimensions ranging from 2 to 6. A metric ‘Compute Effort’ (β) quantified the computational burden of the algorithm in obtaining the global optima for a given data set. We considered Hammersley, Halton, and Sobol sampling techniques for initial design of experiments (DoE), and Radial Basis Function (RBF) surrogates with Bi-Harmonic, Multi-Quadratic, Inverse Multi-Quadratic, Thin Plate Spline, Gaussian, and Cubic basis functions. Analyzing the performance of various surrogate-DoE combinations over 29 test functions, we observed that an RBF surrogate with Bi-Harmonic basis function was the worst in obtaining the global optima (β=100%) for all test functions irrespective of the initial sampling technique, owing to the piecewise linear profile of the response surface. Other surrogate-DoE combinations showed varying performance, with no combination outperforming others. Our algorithm identified the global optima precisely for 22/29 test functions for at least one DoE-surrogate pair, at low computational expense. For 7/29 test functions, it either got stuck at some local optima, or could not precisely reach the global solution before termination. On the 22 successful test functions, our algorithm had lower β as compared to six commercially available global optimization algorithms, including pattern-search-based and evolutionary algorithms. Our future work includes modifying the exploration process so that our proposed algorithm can escape the local optima better, and show improved performance.

References:

Boukouvala, F., Ierapetritou, M.G., 2013. Surrogate-Based Optimization of Expensive Flowsheet Modeling for Continuous Pharmaceutical Manufacturing. J Pharm Innov 8, 131–145. https://doi.org/10.1007/s12247-013-9154-1

Garud, S.S., Mariappan, N., Karimi, I.A., 2019. Surrogate-based black-box optimisation via domain exploration and smart placement. Computers & Chemical Engineering 130, 106567. https://doi.org/10.1016/j.compchemeng.2019.106567

Regis, R.G., Shoemaker, C.A., 2007. A Stochastic Radial Basis Function Method for the Global Optimization of Expensive Functions. INFORMS Journal on Computing 19, 497–509. https://doi.org/10.1287/ijoc.1060.0182

Rios, L.M., Sahinidis, N.V., 2013. Derivative-free optimization: a review of algorithms and comparison of software implementations. J Glob Optim 56, 1247–1293. https://doi.org/10.1007/s10898-012-9951-y