Bilevel optimization

Short description: Quadratic fractional programming problem

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:

[math]\displaystyle{ \min\limits_{x \in X, y \in Y}\;\; F(x,y) }[/math]

subject to:

[math]\displaystyle{ G_i(x,y) \leq 0 }[/math], for [math]\displaystyle{ i \in \{ 1,2,\ldots ,I \} }[/math]

[math]\displaystyle{ y \in \arg \min \limits_{z \in Y} \{ f(x,z) : g_{j}(x,z) \leq 0, j \in \{ 1,2,\ldots,J \} \} }[/math]

where

[math]\displaystyle{ F,f: R^{n_x} \times R^{n_y} \to R }[/math]

[math]\displaystyle{ G_i,g_j: R^{n_x} \times R^{n_y} \to R }[/math]

[math]\displaystyle{ X \subseteq R^{n_x} }[/math]

[math]\displaystyle{ Y \subseteq R^{n_y}. }[/math]

In the above formulation, [math]\displaystyle{ F }[/math] represents the upper-level objective function and [math]\displaystyle{ f }[/math] represents the lower-level objective function. Similarly [math]\displaystyle{ x }[/math] represents the upper-level decision vector and [math]\displaystyle{ y }[/math] represents the lower-level decision vector. [math]\displaystyle{ G_i }[/math] and [math]\displaystyle{ g_j }[/math] 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, [math]\displaystyle{ h(x)=0 }[/math] can be translated as [math]\displaystyle{ \{h(x)\leq 0,\ -h(x)\leq 0\} }[/math]. 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.

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 government’s 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.

Workforce and Human Resources applications

Bilevel optimization can serve as a decision support tool for firms in real-life settings to improve workforce and human resources decisions. The first level reflects the company’s goal to maximize profitability. The second level reflects employees goal to minimize the gap between desired salary and a preferred work plan. The bilevel model provides an exact solution based on a mixed integer formulation and present a computational analysis based on changing employees behaviors in response to the firm’s strategy, thus demonstrate how the problem’s parameters influence the decision policy.

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.

KKT reformulation

Certain bilevel programs, notably those having a convex lower level and satisfying a regularity condition (e.g. Slater's condition), can be reformulated to single level by replacing the lower-level problem by its Karush-Kuhn-Tucker conditions. This yields a single-level mathematical program with complementarity constraints, i.e., MPECs. If the lower level problem is not convex, with this approach the feasible set of the bilevel optimization problem is enlarged by local optimal solutions and stationary points of the lower level, which means that the single-level problem obtained is a relaxation of the original bilevel problem.

Optimal value reformulation

Denoting by

[math]\displaystyle{ \phi (x) = \min\limits_{z \in Y} \{ f(x,z) : g_{j}(x,z) \leq 0, j \in \{ 1,2,\ldots,J \} \} }[/math]

the so-called optimal value function, a possible single-level reformulation of the bilevel problem is

[math]\displaystyle{ \min\limits_{x \in X, y \in Y}\;\; F(x,y) }[/math]

subject to:

[math]\displaystyle{ G_i(x,y) \leq 0 }[/math], for [math]\displaystyle{ i \in \{ 1,2,\ldots ,I \} }[/math]

[math]\displaystyle{ g_{j}(x,y) \leq 0, j \in \{ 1,2,\ldots,J \} }[/math]

[math]\displaystyle{ f(x,y) \leq \phi (x). }[/math]

This is a nonsmooth optimization problem since the optimal value function is in general not differentiable, even if all the constraint functions and the objective function in the lower level problem are smooth.

Heuristic methods

For complex bilevel problems, classical methods may fail due to difficulties like non-linearity, discreteness, non-differentiability, non-convexity etc. In such situations, heuristic methods may be used. Among them, evolutionary methods, though computationally demanding, often constitute an alternative tool to offset some of these difficulties encountered by exact methods, albeit without offering any optimality guarantee on the solutions they produce.

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:

[math]\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) ) }[/math] In the Stackelberg games: Leader problem

subject to:

[math]\displaystyle{ G_i(x,y) \leq 0 }[/math], for [math]\displaystyle{ i \in \{ 1,2,\ldots,I \} }[/math];

[math]\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 \} \} }[/math] In the Stackelberg games: Follower problem

where

[math]\displaystyle{ F: R^{n_x} \times R^{n_y} \to R^{p} }[/math]

[math]\displaystyle{ f: R^{n_x} \times R^{n_y} \to R^{q} }[/math]

[math]\displaystyle{ G_i,g_j: R^{n_x} \times R^{n_y} \to R }[/math]

[math]\displaystyle{ X \subseteq R^{n_x} }[/math]

[math]\displaystyle{ Y \subseteq R^{n_y}. }[/math]

In the above formulation, [math]\displaystyle{ F }[/math] represents the upper-level objective vector with [math]\displaystyle{ p }[/math] objectives and [math]\displaystyle{ f }[/math] represents the lower-level objective vector with [math]\displaystyle{ q }[/math] objectives. Similarly, [math]\displaystyle{ x }[/math] represents the upper-level decision vector and [math]\displaystyle{ y }[/math] represents the lower-level decision vector. [math]\displaystyle{ G_i }[/math] and [math]\displaystyle{ g_j }[/math] 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.

External links

• Mathematical Programming Glossary