  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. Since the consideration of
$\varepsilon$-feasibility cannot be avoided when solving nonconvex problems to
global optimality, our result shows that computational bilevel optimization
with continuous and nonconvex lower levels needs to be done with great care.
Finally, we illustrate that the nonlinearities in the lower level are the key
reason for the observed bad behavior by showing that linear bilevel problems
behave much better at least on the level of feasible solutions.
