Bilevel Optimization: Applications, Properties and Algorithms

Prof. Stephan Dempe

June 22, 2017, 1:45 p.m. BA 9907

Bilevel optimization problems are problems of minimizing some objective function
subject to the graph of the solution set mapping of a second, parametric optimiza-
tion problem. We consider this problem in nite dimensions only and under su-
cient smoothness assumptions on the functions describing it. Bilevel optimization
problems have many applications e.g. in economics, engineering, transportation,
defense. The problem has been considered e.g. in [1, 2, 3].
One application in chemistry is to nd the best composition of chemical sub-
stances and the optimal pressure and temperature such that the chemical equilib-
rium arising in a reactor contains a maximum amount of a desired product.
To investigate this problem, the inner problem needs to be replaced equivalently.
If the optimal value function of this problem is used, a nonconvex, nondi erentiable
and irregular problem arises. Generalized derivatives in the sense of Clarke or
variational analysis can be used to derive necessary optimality conditions. Solution
algorithms use e.g. upper approximations of the optimal value function.
The use of necessary optimality conditions for the inner problem is only possible
if this problem is a convex optimization problem. Even in that case, the resulting
problem (which is called a mathematical program with equilibrium or complemen-
tarity constraints MPCC) is not fully equivalent to the bilevel problem. It is a
di erentiable, nonconvex and irregular problem. To derive optimality conditions,
variational analysis can be used again. A suitable approximation of the constraints
of the MPCC results in a solution algorithm.

References
[1] S. Dempe, Foundations of bilevel programming, Kluwer Academic Publishers, Dordrecht, 2002.
[2] , Annotated bibliography on bilevel programming and mathematical programs with equi-
librium constraints, Optimization 52 (2003), 333{359.
[3] S. Dempe, V. Kalashnikov, G. A. Perez-Valdes, and N. Kalashnykova, Bilevel programming
problems - theory, algorithms and applications to energy networks, Springer Verlag, 2015.