Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization
This work is incremental, as it formalizes an existing approximation method to improve efficiency in multi-objective optimization for researchers and practitioners.
The paper addresses the computational bottleneck in hypervolume-based Bayesian optimization by providing a detailed mathematical and algorithmic description of an approximation algorithm for box decomposition, which was previously lacking in the literature.
Hypervolume (HV)-based Bayesian optimization (BO) is one of the standard approaches for multi-objective decision-making. However, the computational cost of optimizing the acquisition function remains a significant bottleneck, primarily due to the expense of HV improvement calculations. While HV box-decomposition offers an efficient way to cope with the frequent exact improvement calculations, it suffers from super-polynomial memory complexity $O(MN^{\lfloor \frac{M + 1}{2} \rfloor})$ in the worst case as proposed by Lacour et al. (2017). To tackle this problem, Couckuyt et al. (2012) employed an approximation algorithm. However, a rigorous algorithmic description is currently absent from the literature. This paper bridges this gap by providing comprehensive mathematical and algorithmic details of this approximation algorithm.