Solution algorithms for bilevel optimization problems
Final Report Abstract
We considered the optimistic bilevel programming problem and investigated its optimal value reformulation. This was the most suitable approach in our case since it does not presuppose any convexity, differentiability or uniqueness of the lower level solution. Furthermore, it is both locally and globally equivalent to the bilevel programming problem under not too restrictive assumptions. As a constraint qualification, we used the concept of partial calmness. We developed three different solution algorithms for certain bilevel programming problems. The first one is the bundle trust algorithm for Lipschitz continuous, nonconvex optimization problems where the given data is allowed to be inexact in a certain range. Here, a piecewise linear lower approximation of the objective function is created, evaluated and improved iteratively. Furthermore, we introduced two algorithms that work with different outer approximation concepts of the feasible set. These outer approximations are gradually improved until a solution of the original problem is found. One of these algorithms can be applied to problems where the lower level problem is fully convex, which results in a convex lower level optimal value function. In order to use the second algorithm, the lower level constraints are supposed to not depend on the upper level variable and to be polyhedral. Additionally, the lower level objective function has to be the scalar product of upper and lower variable. Then, it is possible to use a relaxation of the lower level optimal value function which is again refined iteratively in order to solve the original problem. Convergence analysis for all algorithms is provided; the first and the third algorithm have also been implemented.
Publications
- (2018) Optimality conditions for the simple convex bilevel programming problem in Banach spaces. Optimization 67 (2) 237–268
Franke, Susanne; Mehlitz, Patrick; Pilecka, Maria
(See online at https://doi.org/10.1080/02331934.2017.1394296) - Solution Algorithm for an Optimistic Linear Stackelberg Problem, Computers & Operations Research 41(2014), 277-281
S. Dempe, S. Franke
(See online at https://doi.org/10.1016/j.cor.2012.09.002) - The bilevel road pricing problem, International Journal of Computing and Optimization 2(2015)2, 71-92
S. Dempe, S. Franke
(See online at https://dx.doi.org/10.12988/ijco.2015.5415) - On the solution of convex bilevel optimization problems, Computational Optimization and Applications 63(2016), 685-703
S. Dempe, S. Franke
(See online at https://doi.org/10.1007/s10589-015-9795-8) - (2019) Solution of bilevel optimization problems using the KKT approach. In: Optimization 68 (8) 1471–1489
S. Dempe, S. Franke
(See online at https://doi.org/10.1080/02331934.2019.1581192) - (2022) Pessimistic Bilevel Linear Optimization. In: J. Nep. Math. Soc. 1 (1) 1–10
S. Dempe, G. Luo, S. Franke
(See online at https://doi.org/10.3126/jnms.v1i1.42165)
