Bilevel optimization is a vital field of active research. Depending on its formulation
it is part of nonsmooth or nondifferentiable optimization, conic programming,
optimization with constraints formulated as generalized equations, or set-valued
optimization. The investigation of many practical problems as decision making in
hierarchical structures, or situations where the reaction of nature on selected actions
needs to be respected, initiated modeling them as bilevel optimization problems. In
this way, new theories have been developed with new results obtained.
A first attempt was the use of the Karush-Kuhn-Tucker conditions in situations
when they are necessary and sufficient optimality conditions for the lower level
problem, or dual problems in case strong duality holds to model the bilevel optimization
problem. The result is a special case of the mathematical program with
equilibrium constraints (MPEC), or complementarity constraints (MPCC). The
latter has motivated the investigation of optimality conditions and the development
of algorithms solving such problems. Unfortunately, it has been shown very
recently that stationary points of an MPEC need not be related to stationary solutions
of the bilevel optimization problem. Because of that, the solution algorithms
must select the Lagrange multipliers associated with the lower level problem very
carefully. Another option is to avoid the explicit use of Lagrange multipliers
resulting in the so-called primal KKT transformation, which is an optimization
problem with a generalized equation as the constraint. Violation of the constraint
qualifications, often used to verify the optimality conditions and convergence of the
solution algorithms, at every feasible point are other challenges for research.
The idea of using the optimal value function of the lower level problem to model
the bilevel optimization problem is perhaps self-explanatory. The result yet is a
nondifferentiable equality constraint. One promising approach here is based on
variational analysis, which is also exploited to verify the optimality conditions for
the MPCC. So, bilevel optimization initiated some advances in variational analysis,
too.
Applications often force the use of integer variables in the respective models.
Besides suitable formulations, mixed-integer bilevel optimization problems renew
the question of existence of an optimal solution, leading to the notion of a weak
v
solution. Surprisingly, adding some constraints that are inactive at a global optimum
of the continuous bilevel problem, as well as replacing a discrete bilevel
problem with its continuous relaxation can destroy the global optimality of a feasible
point.
These and other questions are the topic of the first part of the monograph. In the
second part, certain applications are carefully investigated, especially a natural gas
cash-out problem, an equilibrium problem in a mixed oligopoly, and a toll
assignment problem. For these problems, besides the formulation of solution
algorithms, results of the first numerical experiments with them are also reported.
Bilevel optimization is a quickly developing field of research with challenging
and promising contributions from different topics of mathematics like optimization,
as well as from other sciences like economics, engineering, or chemistry. It was not
a possible aim of the authors to provide an overview of all the results available in
this area. Rather than that, we intended to show some interactions with other topics
of research, and to formulate our opinion about some directions for explorations in
the future.
Stephan Dempe
Vyacheslav Kalashnikov
Gerardo A. Pérez-Valdés
Nataliya Kalashnykova