Solution approaches for optimistic bilevel optimization problems by Stephan Dempe

Topic of the talk are (first) approaches to solve bilevel optimization problems which are based on the transformation of the problem using the optimal value function of the lower level problem. Bilevel optimization problems are nonconvex optimization problems for which the feasible set is not explicitly given. The transformed problem has a nonconvex and nondifferentiable constraint implementing that the objective function value in the lower level problem cannot be larger than the optimal value function. There are two main approaches to solve this problem. One is based on an approximation of the feasible set with increasing accuracy, another one uses a penalization approach. Both approaches will be discussed.

If the optimal value function is concave, the approximation of the feasible set rests in replacing the right-hand side of this nondifferentiable constraint by the minimum of a finite set of linear functions. If it is convex, the optimal value function is replaced by the maximum of a finite number of linear constraints. In the penalization approach, violation of this new function is penalized in the objective. This penalization is exact provided a partial calmness assumption is satisfied. In both cases a sequence of Lipschitz continuous functions needs to be solved which can be done using a bundle algorithm.