# Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation

arXiv: https://arxiv.org/abs/2410.16893 · HTML: https://mlsanity.com/paper/2410.16893/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 63 references that are in the map.
- First posted on arXiv 22 Oct 2024.

## Builds on (most cited first, 22 of 22)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Maximizing acquisition functions for Bayesian optimization](https://mlsanity.com/paper/1805.10196/) (2018)
- [BOCK : Bayesian Optimization with Cylindrical Kernels](https://mlsanity.com/paper/1806.01619/) (2018)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisation](https://mlsanity.com/paper/1911.12809/) (2019)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Mixed-Variable Bayesian Optimization](https://mlsanity.com/paper/1907.01329/) (2019)
- [Mercer Features for Efficient Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2012.07762/) (2020)
- [Constrained Discrete Black-Box Optimization using Mixed-Integer Programming](https://mlsanity.com/paper/2110.09569/) (2021)
- [Bayesian optimization as a flexible and efficient design framework for sustainable process systems](https://mlsanity.com/paper/2401.16373/) (2024)
- [Global Optimization of Gaussian processes](https://mlsanity.com/paper/2005.10902/) (2020)
- [Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces](https://mlsanity.com/paper/2207.00879/) (2022)
- [The Vizier Gaussian Process Bandit Algorithm](https://mlsanity.com/paper/2408.11527/) (2024)
- [Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles](https://mlsanity.com/paper/2111.03140/) (2021)
- [Global sensitivity analysis for optimization with variable selection](https://mlsanity.com/paper/1811.04646/) (2018)
- [On Local Optimizers of Acquisition Functions in Bayesian Optimization](https://mlsanity.com/paper/1901.08350/) (2019)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)

## Built on by (most cited first, 8 of 8)

- [EARL-BO: Reinforcement Learning for Multi-Step Lookahead, High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2411.00171/) (2024)
- [Deterministic Global Optimization of the Acquisition Function in Bayesian Optimization: To Do or Not To Do?](https://mlsanity.com/paper/2503.03625/) (2025)
- [BARK: A Fully Bayesian Tree Kernel for Black-box Optimization](https://mlsanity.com/paper/2503.05574/) (2025)
- [Global optimization of graph acquisition functions for neural architecture search](https://mlsanity.com/paper/2505.23640/) (2025)
- [An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions](https://mlsanity.com/paper/2605.00855/) (2026)
- [Meta-learning for sample-efficient Bayesian optimisation of fed-batch processes](https://mlsanity.com/paper/2605.05382/) (2026)
- [Transferring Information Across Interventions in Causal Bayesian Optimization](https://mlsanity.com/paper/2606.01457/) (2026)
- [ILP-BO: Integer Linear Programming-Based Black-Box Optimization](https://mlsanity.com/paper/2609.33131/) (2026)

## Abstract (arXiv)

Bayesian optimization relies on iteratively constructing and optimizing an acquisition function. The latter turns out to be a challenging, non-convex optimization problem itself. Despite the relative importance of this step, most algorithms employ sampling- or gradient-based methods, which do not provably converge to global optima. This work investigates mixed-integer programming (MIP) as a paradigm for global acquisition function optimization. Specifically, our Piecewise-linear Kernel Mixed Integer Quadratic Programming (PK-MIQP) formulation introduces a piecewise-linear approximation for Gaussian process kernels and admits a corresponding MIQP representation for acquisition functions. The proposed method is applicable to uncertainty-based acquisition functions for any stationary or dot-product kernel. 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.