Semismooth Newton-type method for bilevel optimization: global convergence and extensive numerical experiments
Semismooth Newton-type method for bilevel optimization: global convergence and extensive numerical experiments
复制标题
DOI：
10.1080/10556788.2021.1977810
复制
发表时间：
2019-12
影响因子：
2.2
通讯作者：
A. Fischer;A. Zemkoho;Shenglong Zhou
中科院分区：
文献类型：
--
作者：
A. Fischer;A. Zemkoho;Shenglong Zhou
我们考虑了标准的乐观双层优化问题，特别是上层约束和下层约束可以耦合。通过下层值函数，将问题转化为带有值函数约束惩罚的单层优化问题。对于后一个问题，我们发展了一个框架，它不依赖于下级值函数或其导数的直接计算。对于每个惩罚参数，该框架都会导致一个半光滑的方程组。这使得我们可以将半光滑牛顿法推广到双层优化问题。除了方法的全局收敛性质外，我们还重点研究了半光滑系统解的局部超线性收敛问题。为此，我们提出了一个适当的CD-正则性假设，并导出了满足它的充分条件。此外，我们还给出了半光滑系统的解是双层优化问题的局部解的条件。对文献中的124个非线性双层优化问题的大量数值实验表明，该方法具有显著的性能，只需考虑较少的惩罚参数。
We consider the standard optimistic bilevel optimization problem, in particular upper- and lower-level constraints can be coupled. By means of the lower-level value function, the problem is transformed into a single-level optimization problem with a penalization of the value function constraint. For treating the latter problem, we develop a framework that does not rely on the direct computation of the lower-level value function or its derivatives. For each penalty parameter, the framework leads to a semismooth system of equations. This allows us to extend the semismooth Newton method to bilevel optimization. Besides global convergence properties of the method, we focus on achieving local superlinear convergence to a solution of the semismooth system. To this end, we formulate an appropriate CD-regularity assumption and derive sufficient conditions so that it is fulfilled. Moreover, we develop conditions to guarantee that a solution of the semismooth system is a local solution of the bilevel optimization problem. Extensive numerical experiments on 124 examples of nonlinear bilevel optimization problems from the literature show that this approach exhibits a remarkable performance, where only a few penalty parameters need to be considered.