# Multi-Objective BiLevel Optimization by Bayesian Optimization
## 3 Methodology
### Noise-Free Setting  
An acquisition function for multi-objective Bayesian optimization (MOBO) is expected hypervolume improvement. Maximizing hypervolume (HV) is a procedure for finding the maximum coverage with Pareto-fronts [35]. We use the q-expected hypervolume improvement acquisition function (qEHVI) for a MOBO procedure at the upper-level. qEHVI computes the exact gradient of the Monte Carlo estimator using auto-differentiation, allowing it to employ efficient and effective gradient-based optimization methods. More details about the qEHVI can be found in [17]. Another acquisition optimizer we use is an extended version of a hybrid algorithm with on-line landscape approximation for expensive multi-objective optimization problems (ParEGO) [15]. It is extended to the constrained setting by weighting the expected improvement by the probability of feasibility, which is called qParEGO [36]. qParEGO uses a Monte Carlo-based expected improvement acquisition function, where the objectives are modelled independently and the augmented Chebyshev scalarization [15] is applied to the posterior samples as a composite objective. More details can be found in [17]. The proposed algorithm for a noise-free setting is a hybrid method for solving multi-objective bilevel optimization problems. Briefly, it works as follows: a population of the size of \(N_{u}\) initial decisions, \(\mathbf{x}_{\mathbf{u}}\), is randomly selected from upper-level decision set \(\mathbb{X}_{u}\). We used Sobol sampling for the initial random selection. For each upper-level decision, the lower-level problem is optimized using a non-dominating sorting genetic algorithm with population size \(N_{l}\). For a given \(\mathbf{x}_{u}\), a Pareto-optimal solution set is obtained by the NSGA-II algorithm. Lower-level decision values are selected randomly from the Pareto-front obtained by the NSGA-II algorithm. We decided to use the random selection from the Pareto-optimal solution set following the work [37]. The solution set obtained after lower-level optimization iteration \((\mathbf{x}_{u},\mathbf{x}_{l}^{*})\) is used to find upper-level fitnesses \(F_{i}(\mathbf{x}_{u},\mathbf{x}_{l}^{*})\) for \(i=1,2,\ldots,M_{u}\). We train the GP model with the data set \((\mathbf{x}_{u},y_{i})\) where \(y_{i}=F_{i}(\mathbf{x}_{u},\mathbf{x}_{l}^{*})\). We use batch Bayesian optimization to choose the next candidates with the n-batch, which declares the number of the batch. In each Bayesian optimization iteration, the qEHVI and qParEGO acquisition optimizers suggest n-batch (q) candidates. The lower-level optimization process is repeated for each candidate of the upper-level batch decision candidate \(\mathbf{x}_{u}\). It is important to note that dealing with constraints is the most challenging aspect of bilevel problems. There are various approaches developed over the years, such as optimistic and pessimistic approaches regarding lower-level decision-making strategies; please see [38] for more details. While in the optimistic approach, the lower-level decision maker deals with the constraints and makes decisions considering the most favourable decision for the upper-level decision maker, the pessimistic approach assumes the least favourable decision for the upper-level. In this work, we considered the optimistic multi-objective bilevel problems and dealt with the constraints regarding the best interest of the leader. To avoid upper-level constraint violation, we made the random selection from lower-level Pareto-front considering the upper-level constraints. The algorithm runsfor 50 iterations for the whole multi-objective bilevel optimization process. The details of the algorithm can be found in Algorithm 1.