下层非光滑双层规划的广义梯度算法  

GENERALIZED GRADIENT-BASED ALGORITHMS FOR BILEVEL OPTIMIZATION WITH NONSMOOTH LOWER LEVEL OBJECTIVES

作　　者：吕凯隆 江如俊 Gao Weiguo Lv Kailong;Jiang Rujun(School of Data Science,Fudan University,Shanghai 200433)

机构地区：[1]复旦大学大数据学院,上海200433 [2]不详

出　　处：《高等学校计算数学学报》2024年第3期265-288,共24页Numerical Mathematics A Journal of Chinese Universities

摘　　要：1引言双层规划(BLO)是一种层次数学问题,其中一个优化问题的可行域受另一个优化问题的解集映射的限制,即第二个优化任务嵌入在第一个优化任务中.外部优化问题通常被称为上层(UL)问题,内部优化问题通常被称为下层(LL)问题.双层规划涉及两类变量,分别称为上层和下层变量.其起源可以追溯到Stackelberg博弈[40].Bilevel optimization(BLO)plays a crucial role in many fields of machine learning.Most existing algorithms for BLO assume that the lower-level problems are twice continuously differentiable.However,in practical scenarios,there are numerous cases where the lower-level functions are nonsmooth.In this study,we present a new algorithm that,for the first time,employs Moreau-Yosida regularization to smooth the lower-level objective.We then employ the concept of generalized differentiability for the hyper-function of the new problem with smoothed lowerlevel objective,which can be regarded as a generalization of hyper-gradients.Our main technique is the implicit function theorem for semismooth functions.Building upon this,we have developed generalized hyper-gradient based algorithms for BLO with composite lower-level objective.Experimental results demonstrate the effectiveness of the proposed algorithms.

关 键 词：STACKELBERG博弈 双层规划 广义梯度算法 非光滑 两类变量 可行域 优化问题 内部优化 

分 类 号：O221.2[理学—运筹学与控制论] O224[理学—数学]