Bilevel Optimization: Applications, Properties and Algorithms

Prof. Stephan Dempe

June 22, 2017, 11:45 a.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 optimization problem. We consider this problem in finite dimensions only and under suffcient 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 find the best composition of chemical substances and the optimal pressure and temperature such that the chemical equilibrium 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, nondifferentiable 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 complementarity constraints MPCC) is not fully equivalent to the bilevel problem. It is a differentiable, 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 equilibrium constraints, Optimization 52 (2003), 333-359.
[3] S. Dempe, V. Kalashnikov, G. A. Pérez-Valdés, and N. Kalashnykova, Bilevel programming problems - theory, algorithms and applications to energy networks, Springer Verlag, 2015.