# Efficient Computation of Expected Hypervolume Improvement Using Box Decomposition Algorithms

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2019.

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

- [Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement](https://mlsanity.com/paper/2105.08195/) (2021)
- [Joint Entropy Search for Multi-objective Bayesian Optimization](https://mlsanity.com/paper/2210.02905/) (2022)
- [Multi-Objective Hyperparameter Optimization in Machine Learning -- An Overview](https://mlsanity.com/paper/2206.07438/) (2022)
- [Gradient-Based Multi-Objective Deep Learning: Algorithms, Theories, Applications, and Beyond](https://mlsanity.com/paper/2501.10945/) (2025)
- [BOtied: Multi-objective Bayesian optimization with tied multivariate ranks](https://mlsanity.com/paper/2306.00344/) (2023)
- [TR2-D2: Tree Search Guided Trajectory-Aware Fine-Tuning for Discrete Diffusion](https://mlsanity.com/paper/2509.25171/) (2025)
- [qPOTS: Efficient batch multiobjective Bayesian optimization via Pareto optimal Thompson sampling](https://mlsanity.com/paper/2310.15788/) (2023)
- [A Robust Multi-Objective Bayesian Optimization Framework Considering Input Uncertainty](https://mlsanity.com/paper/2202.12848/) (2022)
- [Constrained Multi-objective Bayesian Optimization through Optimistic Constraints Estimation](https://mlsanity.com/paper/2411.03641/) (2024)
- [PF2ES: Parallel Feasible Pareto Frontier Entropy Search for Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2204.05411/) (2022)
- [A penalisation method for batch multi-objective Bayesian optimisation with application in heat exchanger design](https://mlsanity.com/paper/2206.13326/) (2022)
- [Probability Distribution of Hypervolume Improvement in Bi-objective Bayesian Optimization](https://mlsanity.com/paper/2205.05505/) (2022)
- [A Parallel Technique for Multi-objective Bayesian Global Optimization: Using a Batch Selection of Probability of Improvement](https://mlsanity.com/paper/2208.03685/) (2022)
- [On the development of a practical Bayesian optimisation algorithm for expensive experiments and simulations with changing environmental conditions](https://mlsanity.com/paper/2402.03006/) (2024)
- [Do We Really Need to Approach the Entire Pareto Front in Many-Objective Bayesian Optimisation?](https://mlsanity.com/paper/2604.09417/) (2026)
- [Amortized Active Generation of Pareto Sets](https://mlsanity.com/paper/2510.21052/) (2025)
- [What Makes an Effective Scalarising Function for Multi-Objective Bayesian Optimisation?](https://mlsanity.com/paper/2104.04790/) (2021)
- [Multi-objective robust optimization using adaptive surrogate models for problems with mixed continuous-categorical parameters](https://mlsanity.com/paper/2203.01996/) (2022)
- [Swine Diet Design using Multi-objective Regionalized Bayesian Optimization](https://mlsanity.com/paper/2409.12919/) (2024)
- [MMD-Newton Method for Multi-objective Optimization](https://mlsanity.com/paper/2505.14610/) (2025)
- [Risk-Averse Best Arm Set Identification with Fixed Budget and Fixed Confidence](https://mlsanity.com/paper/2506.22253/) (2025)
- [Multi-Objective Coverage via Constraint Active Search](https://mlsanity.com/paper/2602.15595/) (2026)
- [Converge Then Diversify: Decoupling Convergence and Diversity in Multi-Objective Bayesian Optimisation](https://mlsanity.com/paper/2609.13396/) (2026)
- [Learning What to Evaluate: Correlation-Aware Decoupling for Multiobjective Bayesian Optimization](https://mlsanity.com/paper/2609.32632/) (2026)

## Abstract (arXiv)

In the field of multi-objective optimization algorithms, multi-objective Bayesian Global Optimization (MOBGO) is an important branch, in addition to evolutionary multi-objective optimization algorithms (EMOAs). MOBGO utilizes Gaussian Process models learned from previous objective function evaluations to decide the next evaluation site by maximizing or minimizing an infill criterion. A common criterion in MOBGO is the Expected Hypervolume Improvement (EHVI), which shows a good performance on a wide range of problems, with respect to exploration and exploitation. However, so far it has been a challenge to calculate exact EHVI values efficiently. In this paper, an efficient algorithm for the computation of the exact EHVI for a generic case is proposed. This efficient algorithm is based on partitioning the integration volume into a set of axis-parallel slices. Theoretically, the upper bound time complexities are improved from previously O (n2) and O(n3), for two- and three-objective problems respectively, to Theta(nlog n), which is asymptotically optimal. This article generalizes the scheme in higher dimensional case by utilizing a new hyperbox decomposition technique, which was proposed by D"achert et al, EJOR, 2017. It also utilizes a generalization of the multilayered integration scheme that scales linearly in the number of hyperboxes of the decomposition. The speed comparison shows that the proposed algorithm in this paper significantly reduces computation time. Finally, this decomposition technique is applied in the calculation of the Probability of Improvement (PoI).