Newton-type methods for bilevel optimization

A bilevel optimization problem is an optimization problem with a hierarchical structure featuring a leader (upper-level player) and a follower (lower-level player). The problem is very attractive in modeling real-world problems involving two levels of decision-making. Problems in economics, engineering, health, environmental sciences and other areas of mathematics have been successfully modeled using the bilevel paradigm. Mathematically, the main issue with the structure of the problem is that part of the feasible set of the upper-level problem is defined by the solution map of the lower-level problem. Because of this, the standard optimization theory and the corresponding numerical methods are not applicable. For instance, in the process of constructing a Newton method in standard nonlinear optimization, constraint qualifications are needed to ensure that the method is well-defined. Standard constraint qualifications systematically fail for bilevel optimization problems. The Newton method is one of the most powerful techniques to solve nonlinear system of equations. Over the years, it has been successfully extended to various classes of optimization and closely related problems. The method is the base of a large number of commercial and open source optimization software, and is crucial in solving subproblems in popular algorithms such as augmented Lagrangian and interior point methods. Considering this success in other areas of optimization, we will be proposing cutting-edge techniques, which once combined with the Newton scheme, will lead to efficient algorithms for the bilevel optimization problem. Precisely, we will develop a semismooth Gauss-Newton method and a semismooth Newton-type method to compute the weak and strong stationary points, respectively. We will also construct a general purpose solver based on these two methods. In the process, important gaps in the literature on bilevel optimization will be filled, including the development of second order sufficient conditions and approximation schemes allowing constraint qualifications to be fulfilled. The continuous optimization community will benefit from the Hessian consistency property that will be introduced and studied in the context of the approximation of the lower-level value function, in the process of constructing the semismooth Newton-type method. The Hessian consistency property will be crucial for the construction of (general) nonsmooth optimization Newton-type methods, for which work is still at an early stage. The development of the Gauss-Newton-type method will provide the optimization and numerical analysis communities with new paths for solving non-square nonsmooth systems of equations.