Bilevel optimization is a special kind of optimization where one problem is embedded (nested) within another. The outer optimization task is commonly referred to as the upper-level optimization task, and the inner optimization task is commonly referred to as the lower-level optimization task. These problems involve two kinds of variables, referred to as the upper-level variables and the lower-level variables.^[1][2][3]

Mathematical formulation of the problem

A general formulation of the bilevel optimization problem can be written as follows:

${\displaystyle \min \limits _{x\in X,y\in Y}\;\;F(x,y)}$

subject to:

${\displaystyle G_{i}(x,y)\leq 0}$, for ${\displaystyle i\in \{1,2,\ldots ,I\}}$

${\displaystyle y\in \arg \min \limits _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}}$

where

${\displaystyle F,f:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle X\subseteq R^{n_{x}}}$

${\displaystyle Y\subseteq R^{n_{y}}.}$

In the above formulation, ${\displaystyle F}$ represents the upper-level objective function and ${\displaystyle f}$ represents the lower-level objective function. Similarly ${\displaystyle x}$ represents the upper-level decision vector and ${\displaystyle y}$ represents the lower-level decision vector. ${\displaystyle G_{i}}$ and ${\displaystyle g_{j}}$ represent the inequality constraint functions at the upper and lower levels respectively. If some objective function is to be maximized, it is equivalent to minimize its negative. The formulation above is also capable of representing equality constraints, as these can be easily rewritten in terms of inequality constraints: for instance, ${\displaystyle h(x)=0}$ can be translated as ${\displaystyle \{h(x)\leq 0,\ -h(x)\leq 0\}}$. However, it is usually worthwhile to treat equality constraints separately, to deal with them more efficiently in a dedicated way; in the representation above, they have been omitted for brevity.

Stackelberg competition

Bilevel optimization was first realized in the field of game theory by a German economist Heinrich Freiherr von Stackelberg who published Market Structure and Equilibrium (Marktform und Gleichgewicht) in 1934 that described this hierarchical problem. The strategic game described in his book came to be known as Stackelberg game that consists of a leader and a follower. The leader is commonly referred as a Stackelberg leader and the follower is commonly referred as a Stackelberg follower. In a Stackelberg game, the players of the game compete with each other, such that the leader makes the first move, and then the follower reacts optimally to the leader's action. This kind of a hierarchical game is asymmetric in nature, where the leader and the follower cannot be interchanged. The leader knows ex ante that the follower observes its actions before responding in an optimal manner. Therefore, if the leader wants to optimize its objective, then it needs to anticipate the optimal response of the follower. In this setting, the leader's optimization problem contains a nested optimization task that corresponds to the follower's optimization problem. In the Stackelberg games, the upper level optimization problem is commonly referred as the leader's problem and the lower level optimization problem is commonly referred as the follower's problem.

If the follower has more than one optimal response to a certain selection of the leader, there are two possible options: either the best or the worst follower's solution with respect to the leader's objective function is assumed, i.e. the follower is assumed to act either in a cooperative way or in an aggressive way. The resulting bilevel problem is called optimistic bilevel programming problem or pessimistic bilevel programming problem respectively.

Applications

Bilevel optimization problems are commonly found in a number of real-world problems. This includes problems in the domain of transportation, economics, decision science, business, engineering, environmental economics etc. Some of the practical bilevel problems studied in the literature are briefly discussed.^[4]

Solution methodologies

Bilevel optimization problems are hard to solve. One solution method is to reformulate bilevel optimization problems to optimization problems for which robust solution algorithms are available. Extended Mathematical Programming (EMP) is an extension to mathematical programming languages that provides several keywords for bilevel optimization problems. These annotations facilitate the automatic reformulation to Mathematical Programs with Equilibrium Constraints (MPECs) for which mature solver technology exists. EMP is available within GAMS.

Multi-objective bilevel optimization

A bilevel optimization problem can be generalized to a multi-objective bilevel optimization problem with multiple objectives at one or both levels. A general multi-objective bilevel optimization problem can be formulated as follows:

${\displaystyle \min \limits _{x\in X,y\in Y}\;\;F(x,y)=(F_{1}(x,y),F_{2}(x,y),\ldots ,F_{p}(x,y))}$ In the Stackelberg games: Leader problem

subject to:

${\displaystyle G_{i}(x,y)\leq 0}$, for ${\displaystyle i\in \{1,2,\ldots ,I\}}$;

${\displaystyle y\in \arg \min \limits _{z\in Y}\{f(x,z)=(f_{1}(x,z),f_{2}(x,z),\ldots ,f_{q}(x,z)):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}}$ In the Stackelberg games: Follower problem

where

${\displaystyle F:R^{n_{x}}\times R^{n_{y}}\to R^{p}}$

${\displaystyle f:R^{n_{x}}\times R^{n_{y}}\to R^{q}}$

${\displaystyle G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle X\subseteq R^{n_{x}}}$

${\displaystyle Y\subseteq R^{n_{y}}.}$

In the above formulation, ${\displaystyle F}$ represents the upper-level objective vector with ${\displaystyle p}$ objectives and ${\displaystyle f}$ represents the lower-level objective vector with ${\displaystyle q}$ objectives. Similarly, ${\displaystyle x}$ represents the upper-level decision vector and ${\displaystyle y}$ represents the lower-level decision vector. ${\displaystyle G_{i}}$ and ${\displaystyle g_{j}}$ represent the inequality constraint functions at the upper and lower levels respectively. Equality constraints may also be present in a bilevel program, but they have been omitted for brevity.

References

External links

• Mathematical Programming Glossary