Bilevel Optimization¶
Bilevel optimization is a field of mathematical optimization in which two optimization problems are intertwined: the upper-level and the lower-level problem. The upper-level problem minimizes a given objective function taking into account the solution to the lower-level problem, which is parameterized by the upper-level’s decision. Such problems have many applications in, e.g., economics where it is used to model non-cooperative games.
A classic model for a bilevel problem is as follows.
in which \(S(x)\) denotes the solution set of the lower-level problem, which is parameterized by the upper-level decision \(x\). The lower-level problem is defined as
Note that the quotes around the \(\min\) operator in (1) is here to highlight that the problem is ill-defined in its current form. Indeed, in case multiple solutions to the lower-level problem exist, the upper-level problem has to somehow “choose” one of them. To circumvent this, we typically consider the optimistic setting, where the lower-level is assumed to pick the solution in favor of the upper-level problem, in order to break ties.
Optimistic bilevel problems can be modeled as:
Note that there exists other notions such as pessimistic bilevel problems. There, the lower-level problem is assumed to pick the worst solution for the upper-level problem. This can be modeled as follows.
Pessimisitc bilevel problems are less studied in the literature.