Duality Approach to Bilevel Programs with a Convex Lower Level

Bilevel programs with a convex lower level are often reformulated as a single-level program, where the lower level problem is replaced by an optimality condition such as the KKT conditions or upper-bounding the objective of the lower level problem by its value function. This paper considers the optimality condition of upper-bounding the objective of the lower level problem by a new dual function, which we construct to be differentiable (unlike the usual Lagrangian dual function) under mild assumptions. This new dual is used to define a duality-based reformulation of the bilevel program, and this reformulation includes elements of regularization. We study questions of existence of solutions, relationship between local solutions of the bilevel program and its reformulation, constraint qualification, and convergence of stationary points as the regularization is decreased. In particular, we show such convergence occurs when there is appropriate regularity (that we partially characterize by a sufficient condition) of the solution mapping of the lower level problem. Stability and continuity of solutions to the bilevel program is also studied. Taken together, our results show approximate (in both the objective and constraints) bilevel programs and their duality-based reformulations do not share the same pathologies that occur for bilevel programs or their reformulations. We use this to argue that, from a modeling perspective, approximate bilevel programs may be a more useful or appropriate model for many applications. Lastly, two numerical examples demonstrate how our duality-based approach can be used to solve a diverse variety of bilevel programs with a convex lower level.