On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level

Understand

It is well known that bilevel optimization problems are hard to solve both in theory and practice.

• In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels.
• Even if the lower-level problem is solved to $\varepsilon$-feasibility regarding its nonlinear constraints for an arbitrarily small but positive $\varepsilon$, the obtained bilevel solution as well as its objective value may be arbitrarily far away from the actual bilevel solution and its actual objective value.
• This result even holds for bilevel problems for which the nonconvex lower level is uniquely solvable, for which the strict complementarity condition holds, for which the feasible set is convex, and for which Slater's constraint qualification is satisfied for all feasible upper-level decisions.