# Multi-Objective BiLevel Optimization by Bayesian Optimization
## 3 Methodology
### Noisy Setting  
We consider a case that is crucial in practice, in which the leader must make decisions under uncertainty based on noisy observations \(F_{i}=\mathbf{f}(\mathbf{x}_{u_{i}},\mathbf{x}_{i_{i}})+\xi_{i}\), where \(\xi_{i}\sim\mathcal{N}(0,\Sigma_{i})\) and \(\Sigma_{i}\) is the noise covariance and \(\mathbf{x}_{u},\mathbf{x}_{i}\) are upper and lower decision variables, respectively. We reformulate the leader's objective with noisy observations as  
\[\underset{\mathbf{x}_{u},\mathbf{x}_{i}}{\text{minimize}}\{F_{1}(\mathbf{x}_ {u},\mathbf{x}_{i})+\xi_{1},...,F_{i}(\mathbf{x}_{u},\mathbf{x}_{l})+\xi_{i}\} \tag{3}\]  
where \(\xi_{i}\sim\mathcal{N}(0,\Sigma_{i})\). Figure 2 represents the Pareto-front of noisy upper-level objective. We can observe that it is important to obtain a true Pareto-front with the uncertainty at upper level. The hypervolume indicator measures the volume of space between the non-dominated front and a reference point, which we assume is known by the upper-level decision-maker. The selection of reference points is tricky. In this work, it is chosen to be an extreme point of the Pareto-front, because reference points should be dominated by all Pareto-optimal solutions. Figure 2: Decision making under upper-level uncertainty. Hypervolume improvement of a set of points \(\mathcal{P}^{\prime}\) is defined as \(HVI(\mathcal{P}^{\prime}|\mathcal{P},\mathbf{r})=HV(\mathcal{P}\cup\mathcal{P}^{ \prime}|\mathbf{r})-HV(\mathcal{P}|\mathbf{r})\), where \(\mathcal{P}\) represents the Pareto-front and \(\mathbf{r}\) the reference point. Given observations of the upper-level decision-making process, the GP surrogate model provides us with a posterior distribution over the upper-level function values for each observation. These values can be used to compute the expected hypervolume improvement acquisition function defined by  
\[\alpha_{\textit{e}tri}(\mathbf{x}_{u}|\mathcal{P})=\mathbb{E}[HVI(\mathbf{F}_ {u}|\mathcal{P})]. \tag{4}\]  
So the expected hypervolume improvement iterates over the posterior distribution, an approach that worked well in [39]. After \(n\) observations of the leader's decisions and the follower's response, the posterior distribution can be defined by the conditional probability \(p(\mathbf{F}(\mathbf{x}_{u_{n}},\mathbf{x}_{u_{n}})|\mathcal{D}_{n})\) of the leader's objective values given decision variables \((\mathbf{x}_{u_{n}},\mathbf{x}_{l_{n}})\) based on noisy observations \(\mathcal{D}_{n}=\mathbf{x}_{u_{i}},\mathbf{F}_{i}(\mathbf{x}_{u_{i}},\mathbf{ x}_{l_{i}}),\left(\Sigma_{i}\right)_{i=1}^{n}\). NEHVI is defined as  
\[\alpha_{\textit{NEHVI}}(\mathbf{x}_{u})=\int\alpha_{\textit{e}tri}(\mathbf{x }_{u}|P_{n})p(\mathbf{F}|\mathcal{D}_{n})d\mathbf{F} \tag{5}\]  
where \(P_{n}\) denotes the Pareto-optimal front optimal decision set over the leader's objectives \(\mathbf{F}_{n}\). The aim is to improve the efficiency of the optimization, and the handling of noise in the leader's objective, by using the approach above and reformulating the bilevel multi-objective optimization problem. The algorithm details can be found in Algorithm 2.