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

Yasmine Beck (), Daniel Bienstock (), Martin Schmidt () and Johannes Thürauf ()
Additional contact information
Yasmine Beck: Trier University
Daniel Bienstock: Columbia University
Martin Schmidt: Trier University
Johannes Thürauf: Trier University

Journal of Optimization Theory and Applications, 2023, vol. 198, issue 1, No 16, 428-447

Abstract: Abstract 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.

Keywords: Bilevel optimization; Nonconvex lower levels; Approximate feasibility; Global optimization; 90-XX; 90C26; 90C31 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-023-02238-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:198:y:2023:i:1:d:10.1007_s10957-023-02238-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-023-02238-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().