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

Description

It is well known that bilevel optimization problems are hard to solve—both in theory and practice. In this talk, we highlight a further computational difficulty when it comes to solving bilevel problems with a continuous but nonconvex lower level. Even if the lower-level problem is solved to epsilon-feasibility regarding its nonlinear constraints for an arbitrarily small but positive epsilon, 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, strict complementarity holds, and for which its convex constraint set satisfies Slater's constraint qualification for all feasible upper-level decisions. As the consideration of epsilon-feasibility cannot be avoided for nonconvex problems, our results show that computational bilevel optimization with continuous and nonconvex lower levels needs to be done with great care.

Period	27 Jan 2026
Event title	EURO Online Seminar Series on Operational Research and Machine Learning
Event type	Seminar
Degree of Recognition	International