This paper considers a bilevel program, which has many applications in practice. To develop effective numerical algorithms, it is generally necessary to transform the bilevel program into a single-level optimization problem. The most popular approach is to replace the lower-level program by its KKT conditions and then the bilevel program can be transformed into a mathematical program with equilibrium constraints (MPEC for short). However, the MPEC does not satisfy the Mangasarian-Fromovitz constraint qualification at any feasible point so that the well-developed nonlinear programming theory may not be applied to MPECs directly. In this paper, we apply the Wolfe duality to show that, under very mild conditions, the bilevel program is equivalent to a new single-level reformulation (WDP for short) in the globally or locally optimal sense. We give an example to show that WDP may satisfy the Mangasarian-Fromovitz constraint qualification at its feasible points and hence WDP is no longer an MPEC. We give some properties of the WDP reformulation and the relations between the WDP and MPEC reformulations. Furthermore, we propose a relaxation method for solving WDP and investigate its limiting behavior. Comprehensive numerical experiments indicate that, although solving WDP directly did not perform very well in our tests, the relaxation method based on the WDP reformulation was quite efficient.
Citation
February 16, 2021