Newton-Type Methods for Bilevel Optimization

Alain Zemkoho, University of Southampton
Computing Abstraction

A bilevel optimization problem is a special class of optimization problem partly constrained by another optimization problem. The problem can be traced back to the habilitation thesis of German economist Heinrich von Stackelberg, which was completed in 1934. Hence, the problem is referred to by economists and game theorists as a Stackelberg game. The bilevel optimization problem, which clearly has a hierarchical structure with two levels of decision-making, respectively controlled by a leader and a follower, represents a powerful tool for modelling the interactions between various engineering, economic, and human systems. The problem was introduced in the field of optimization in the early 1970s and interest in the subject has grown exponentially since then, driven largely by the wide range of applications. Initial works on the optimization side were significantly influenced by developments in the closely related area of mathematical programs with equilibrium or complementarity constraints. Recently though, the more natural transformation known as value function reformulation has also been at the center of attentions and will represent the starting point of our analysis. Considering the current influence of machine learning in the field of optimization, we will kick off the discussion in this talk with a few applications of bilevel optimization in machine learning. We will subsequently shift our attention to some recent attempts to design Newton-type methods for bilevel optimization. We will discuss the theoretical framework for the method and relevant challenges. We will conclude the talk with some promising numerical results.

Zoom Link: