Bilevel optimization - from hardness to efficient algorithms

par Le Quoc-Tung (TSE)

mardi 7 janv. 2025, 11:15 → 12:15 Europe/Paris

Salle K. Johnson (1R3, 1er étage)

Bilevel optimization is an important mathematical tool to model phenomena in many domains, such as economic game theory, decision science and machine learning, to name but a few. Despite its importance, efficient and scalable algorithms for bilevel optimization are mostly developed for the (strong) convexity of the lower-level problem case, which is unrealistic for many practical tasks. In the quest to understand more general bilevel problems, we relax the lower level strong convexity and consider polynomial bilevel optimization, i.e., polynomial objective functions and constraints. Certain results in this presentation are relevant for more general classes of functions, e.g., semi-algebraic and definable functions.

 

In particular, we propose two types of analysis: on the one hand, we focus on the worst-case analysis of this class of bilevel optimization, from both geometric and computational viewpoints. More specifically, we demonstrate that solving polynomial bilevel optimization is equivalent to optimizing general semi-algebraic functions. In addition, we show the $\Sigma_2^p$-hardness of polynomial bilevel optimization. These two results characterize polynomial bilevel problems as vastly more challenging than the NP-complete problems which are usually encountered in continuous optimization. On the other hand, under a special structure of lower-level problem, termed as parametric Morse, we show a positive result: under this assumption, bilevel optimization is equivalent to a mixed-integer programming problem and optimization algorithms based on automatic differentiation and first-order methods can efficiently find $\epsilon$-critical points.