# Multi-Objective BiLevel Optimization by Bayesian Optimization
## 2 Preliminaries  
BO is a method to optimize expensive-to-evaluate black-box functions. It uses a probabilistic surrogate model, typically a GP [33]\(p(f|\mathcal{D})\) to model the objective function \(f\) based on previously observed data points \(\mathcal{D}=\{(\mathbf{x}_{1},y_{1}),\ldots,(\mathbf{x}_{n},y_{n})\}\). GPs are models that are specified by a mean function \(\mu(\mathbf{x};\{\mathbf{x}_{n},y_{n}\},\theta):\mathbb{R}^{d}\to\mathbb{R}\) and predictive variance function \(\sigma(\mathbf{x};\{\mathbf{x}_{n},y_{n}\},\theta):\mathbb{R}^{d}\times \mathbb{R}^{d}\to\mathbb{R}\). A surrogate model \(p(f|\mathcal{D})\) is assisted by an acquisition function \(\alpha:\mathcal{X}\to\mathbb{R}\). We represent acquisition functions depending on the previous observations as \(\alpha(\mathbf{x};\{\mathbf{x}_{n},y_{n}\},\theta)\), where \(\theta\) is Gaussian parameters such as a kernel for the model. Because the objective function is expensive-to-evaluate and the surrogate-based acquisition function is not, it can be optimized more easily than the true function to yield \(\mathbf{x}_{new}\). The acquisition function selects the point \(\mathbf{x}_{new}\) that maximizes the acquisition function \(\mathbf{x}_{new}=argmax_{\mathbf{x}\in\mathcal{X}}\alpha(\mathbf{x})\). It then evaluates the objective function \(y_{new}=f(\mathbf{x}_{new})\) and updates the data set with new observations \(\mathcal{D}\leftarrow\mathcal{D}\cup(\mathbf{x}_{new},y_{new})\). In the GP, \(\mu(x)\) can be viewed as the prediction of the function value, and \(\sigma(x)\) is a measure of the uncertainty of the prediction. Multi-objective BO tackles the problem of optimizing a vector-valued objective \(\mathbf{f}(\mathbf{x})\): \(\mathbb{R}^{d}\to\mathbb{R}^{d}\) with \(\mathbf{f}(\mathbf{x})=(f_{1}(\mathbf{x}),\ldots,f_{d}(\mathbf{x}))\) for a vector-valued decision variable \(\mathbf{x}\in\mathbb{R}^{d}\). Because of the nature of multi-objective black-box problems, we assume that there is no known analytical expression. Multi-objective optimization problems generally do not have a single best solution, so we must find a solution set instead of a single solution; thus, the set of Pareto-optimal solutions. We say that \(\mathbf{f}(\mathbf{x})\) dominates another solution \(\mathbf{f}(\mathbf{x}^{\prime})\) if \(f^{(i)}(\mathbf{x})\succ f^{(i)}(\mathbf{x}^{\prime})\) for all \(i=1,2,\ldots,M\) and there exists \(i^{\prime}\in\{1,2,\ldots,M\}\) such that \(f^{i}\left(\mathbf{x}\right)\succ f^{i^{\prime}}\left(\mathbf{x}^{\prime}\right)\). So we can express the Pareto-optimal solution set by \(P^{*}=\{\mathbf{f}(\mathbf{x})\text{ s.t. }\
exnex\mathbf{x}^{\prime}\in X:\mathbf{f}( \mathbf{x}^{\prime})\succ\mathbf{f}(\mathbf{x})\}\) and \(X^{*}=\{\mathbf{x}\in X\text{ s.t. }\mathbf{f}(\mathbf{x})\in P^{*}\}\). After obtaining the Pareto solution set, which is called the Pareto-front, the decision maker can make decisions using the trade-off between objectives, or any known preferences. In general, multi-objective optimization algorithms try to find a set of distributed solutions that approximate the Pareto-front. Hypervolume improvement (HVI) is often used as a measure of improvement in multi-objective problems [34]. HVI is the volume that is dominated by the new point in the outcome space. It is generally nonrectangular and it can be computed efficiently by partitioning the non-dominated space into separate hyper-rectangles. This makes it a good candidate for seeking improvement in the outcome search space for the Pareto-optimal front. Figure 1 illustrates the hypervolume improvement in a 2 dimensional setting. The red area in the left graph represents the dominated solutions while the white area represents non-dominated solutions, and the green area in the middle graph represents the hypervolume improvement after the first point selection. The right graph illustrates the HVI in the \(q=2\) setting where \(q\) represents that batch selection in batch Bayesian optimization. Several methods have been proposed.