Bilevel optimization

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.

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 can not 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.

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.[1]

Toll setting problem

In the field of transportation, bilevel optimization commonly appears in the toll-setting problem. Consider a network of highways that is operated by the government. The government wants to maximize its revenues by choosing the optimal toll setting for the highways. However, the government can maximize its revenues only by taking the highway users' problem into account. For any given tax structure the highway users solve their own optimization problem, where they minimize their traveling costs by deciding between utilizing the highways or an alternative route. Under these circumstances, the government's problem needs to be formulated as a bilevel optimization problem. The upper level consists of the governments objectives and constraints, and the lower level consists of the highway users' objectives and constraints for a given tax structure. It is noteworthy that the government will be able to identify the revenue generated by a particular tax structure only by solving the lower level problem that determines to what extent the highways are used.

Structural optimization

Structural optimization problems consist of two levels of optimization task and are commonly referred as mathematical programming problems with equilibrium constraints (MPEC). The upper level objective in such problems may involve cost minimization or weight minimization subject to bounds on displacements, stresses and contact forces. The decision variables at the upper level usually are shape of the structure, choice of materials, amount of material etc. However, for any given set of upper level variables, the state variables (displacement, stresses and contact forces) can only be figured out by solving the potential energy minimization problem that appears as an equilibrium satisfaction constraint or lower level minimization task to the upper level problem.

Defense applications

Bilevel optimization has a number of applications in defense, like strategic offensive and defensive force structure design, strategic bomber force structure, and allocation of tactical aircraft to missions. The offensive entity in this case may be considered a leader and the defensive entity in this case may be considered a follower. If the leader wants to maximize the damage caused to the opponent, then it can only be achieved if the leader takes the reactions of the follower into account. A rational follower will always react optimally to the leaders offensive. Therefore, the leader's problem appears as an upper level optimization task, and the optimal response of the follower to the leader's actions is determined by solving the lower level optimization task.

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.

Evolutionary bilevel optimization

For complex bilevel problems, classical methods fail due to difficulties like non-linearity, discreteness, non-differentiability, non-convexity etc. In such situations, evolutionary methods, though computationally demanding, could be an alternative tool to offset some of these difficulties and lead to an approximate optimal solution.

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

1. "Scope: Evolutionary Bilevel Optimization". www.bilevel.org. Retrieved 6 October 2013.

External links

• Metaheuristics for Bilevel Optimization
• Evolutionary Bilevel Optimization
• Mathematical Programming Glossary