# 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, nondierentiable

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

dierentiable, 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.