Newton-type methods for bilevel optimization

双层优化问题是具有一个领导者（上层参与者）和一个追随者（下层参与者）的分层结构的优化问题。这个问题在建模涉及两层决策的现实问题时非常有吸引力。经济学、工程学、卫生、环境科学和其他数学领域的问题已经成功地利用双层范式建立了模型。在数学上，问题结构的主要问题是上层问题的部分可行集是由下层问题的解映射定义的。因此，标准的优化理论和相应的数值方法并不适用。例如，在标准非线性优化中的牛顿方法的构造过程中，需要约束条件来保证该方法是定义良好的。标准约束条件在两级优化问题中系统性地失效。牛顿法是求解非线性方程组最有效的方法之一。多年来，它已成功地推广到各种类型的优化和密切相关的问题。该方法是大量商业和开源优化软件的基础，对于解决诸如增广拉格朗日法和内点法等流行算法中的子问题至关重要。考虑到在其他优化领域的成功，我们将提出尖端技术，一旦与牛顿方案结合，将导致有效的算法来解决双层优化问题。准确地说，我们将分别开发一种半光滑高斯-牛顿方法和半光滑牛顿型方法来计算弱平稳点和强平稳点。我们还将基于这两种方法构造一个通用求解器。在此过程中，将填补文献中关于双层优化的重要空白，包括允许满足约束条件的二阶充分条件和近似格式的发展。在构造半光滑牛顿型方法的过程中，将在低阶值函数逼近的背景下引入和研究Hessian一致性，这将使连续优化社区受益。Hessian一致性性质对于构造（一般）非光滑优化牛顿型方法至关重要，这方面的工作尚处于起步阶段。高斯-牛顿型方法的发展将为优化和数值分析界提供求解非平方非光滑方程组的新途径。

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.