(206a) Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation

Bayesian optimization (BO) is an increasingly popular for design of experiments and black-box optimization in chemical engineering applications [Paulson and Tsay, 2024, Wang and Dowling, 2022]. Most BO algorithms rely on iteratively constructing and optimizing an acquisition function [Frazier, 2018]. The latter turns out to be a challenging, non-convex optimization problem itself [Wilson et al., 2018, Kim and Choi, 2021]. Gaussian processes (GP) are widely chosen as the surrogate model whose posterior information is used to formulate an acquisition function. Both the theoretical convergence analysis in classic GP-based BO (e.g., GP-UCB [Srinivas et al., 2010]) and the optimization quality rely on computing the global optima of such acquisition function. Despite the relative importance of this step, most algorithms employ sampling- or gradient-based methods, which do not provably converge to global optima.

An alternative class of deterministic methods is mixed-integer programming (MIP) [Belotti et al., 2013], where established algorithms can globally optimize an objective function subject to various constraints. Conditions of a given problem are expressed as linear, quadratic, nonlinear and/or integral constraints and are passed to modern solvers that utilize branch-and-bound (B&B) algorithms. This work investigates MIP as a paradigm for global acquisition function optimization, which can be formulated as a general nonlinear MIP [Georgiou et al., 2025, Schweidtmann et al., 2021]. We propose Piecewise-linear Kernel Mixed Integer Quadratic Programming (PK-MIQP), a global optimization framework for GP acquisition functions [Xie et al., 2025]. Specifically, we introduce a piecewise linear approximation of the GP kernel function that enables a mixed-integer quadratic programming (MIQP) formulation of the acquisition function. We then use a B&B solver to globally optimize the approximated acquisition function. While gradient-based methods can return sub-optimal solutions without further indication or fail due to lack of derivative information [Ament et al., 2024], our method approximates the global optimum within a bounded neighborhood.

We analyze the theoretical regret bounds of the proposed approximation, and empirically demonstrate the framework on synthetic functions, constrained benchmarks, and a hyperparameter tuning task. The results show that PK-MIQP outperforms other state-of-the-art solvers in terms of optimization performance and adaptability to constraints as an acquisition function optimizer in a BO setting.

References:

S. Ament, S. Daulton, D. Eriksson, M. Balandat, and E. Bakshy. Unexpected improvements to expected improvement for Bayesian optimization. In NeurIPS, 2024.

P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan. Mixed-integer nonlinear optimization. Acta Numerica, 22:1–131, 2013.

P. I. Frazier. A tutorial on Bayesian optimization. arXiv preprint arXiv:1807.02811, 2018.

A. Georgiou, D. Jungen, L. Kaven, V. Hunstig, C. Frangakis, I. Kevrekidis, A. Mitsos. Deterministic Global Optimization of the Acquisition Function in Bayesian Optimization: To Do or Not To Do?. arXiv preprint arXiv:2503.03625, 2025.

J. Kim and S. Choi. On local optimizers of acquisition functions in Bayesian optimization. In Machine Learning and Knowledge Discovery in Databases, 2021.

J. A. Paulson and C. Tsay. Bayesian optimization as a flexible and efficient design framework for sustainable process systems. Current Opinion in Green and Sustainable Chemistry, 100983, 2025.

A. M. Schweidtmann, D. Bongartz, D. Grothe, T. Kerkenhoff, X. Lin, J. Najman, and A. Mitsos. Deterministic global optimization with Gaussian processes embedded. Mathematical Programming Computation, 13(3):553-81, 2021.

N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: no regret and experimental design. In ICML, 2010.

Y. Xie, S. Zhang, J. Paulson, and C. Tsay. Global optimization of Gaussian process acquisition functions using a piecewise-linear kernel approximation. AISTATS 2025 (accepted), 2025.
arXiv preprint arXiv:2410.16893

K. Wang and A. W. Dowling. Bayesian optimization for chemical products and functional materials. Current Opinion in Chemical Engineering, 36:100728, 2022.

J. Wilson, F. Hutter, and M. Deisenroth. Maximizing acquisition functions for Bayesian optimization. In NeurIPS, 2018.