Newton-type methods for bilevel optimization

双层优化问题是具有领导者(上级玩家)和跟随者(下级玩家)的分层结构的优化问题。该问题在对涉及两层决策的真实世界问题进行建模时非常有吸引力。经济学、工程学、卫生、环境科学和其他数学领域的问题已经成功地使用两层范式进行了建模。从数学上讲，问题结构的主要问题是上层问题的部分可行集是由下层问题的解图定义的。因此，标准的优化理论和相应的数值方法是不适用的。例如，在构造标准非线性优化中的牛顿方法的过程中，需要约束限定以确保该方法是定义良好的。对于双层优化问题，标准的约束资格系统地失效。牛顿法是求解非线性方程组最强大的技术之一。多年来，它已成功地推广到各类优化问题和密切相关的问题。该方法是大量商业和开源优化软件的基础，在求解增广拉格朗日算法和内点法等流行算法中的子问题时起着至关重要的作用。考虑到这种在其他优化领域的成功，我们将提出尖端技术，一旦与牛顿方案相结合，将产生求解双层优化问题的高效算法。准确地说，我们将开发半光滑高斯-牛顿法和半光滑牛顿型方法来分别计算弱驻点和强驻点。我们还将基于这两种方法构造一个通用求解器。在这一过程中，将填补两层优化文献中的重要空白，包括开发二阶充分条件和允许满足约束限定的近似方案。在构造半光滑牛顿型方法的过程中，将在低级值函数的近似的背景下引入和研究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.