1. 引言
本文考虑如下带变换
罚函数的正则化问题:
(1)
其中
是二次可微函数,
是变换
惩罚函数。
罚函数是解决非线性规划问题的重要手段,如今利用罚函数解决优化问题的文章有很多,目的是将有约束问题转换成无约束问题。变换
惩罚函数(简称TL1罚)是由Nikolova [1] 提出来的,形式如下:
压缩感知 [2] 在数学、统计学、信息科学和其他领域被广泛研究,其中一个基本的问题是在一些远小于信号环境空间尺寸的线性测量(线性约束)下重建一个稀疏信号,最直接的方法是进行
优化,但是优化
范数是NP-hard的,因此已经寻找了许多可行的替代方案。变量选择在高维数据分析中起着非常重要的作用,对于惩罚函数的选择,Fan和Li [3] 提出一个好的惩罚函数应该具有无偏性、稀疏性和连续性,Lipschitz连续函数的一个特殊的单参数族,即变换
函数,满足这三个期望性质 [4] ,该函数的近端算子对参数
的所有值都有封闭形式的解析解,并且通过调整参数
,TL1可以很好地近似于
和
,这些性质让该函数在许多优化问题中得到了广泛应用。
正则化的应用不仅限于机器学习,也广泛用于线性代数理论中,用于处理不适定问题,即那些由条件数很大的方程组定义的问题。在正则化模型的成本函数中加入一个惩罚项,这样可以控制模型的复杂度,防止模型过拟合,降低结构风险,提高模型的泛化能力。对于带变换
罚函数的正则化问题,2014年,Zhang和Xin [5] 研究了在
最优解的精确稳定恢复中TL1惩罚和TL1正则化问题的理论性质,并且利用广义零空间性质和明确的例子,证明了TL1相对于
在线性约束下精确恢复方面的优势;2016年,Zhang和Xin [6] 推导了在参数
的任意正值下最优解的封闭形式。2017年,Ahn,Pang和Xin [7] 研究了TL1正则化问题的最优性条件,并且提出了TL1罚的凸差分解模型;Zhang [8] 将TL1罚扩展到TS1(变换Schatten-1)用于低秩矩阵补全,并与其他几种先进的方法进行了比较。2018年,Guo,Li和Liu [9] 研究了TL1最优化的稀疏重组的性质,并给出了关于从欠采样测量中重建的可恢复性和准确性改进的理论结果。2019年,Ma和Miao等人 [10] 将TL1正则化方法应用于稀疏深度神经网络学习。
图像导数 [11] [12] [13] [14] [15] 是变分分析及其应用中的一类工具,它主要用来刻画集值映射的广义微分性质。图像导数可以用来刻画集值映射的稳定性,如度量正则 [16] ,Lipschitz性 [16] ,二阶增长条件 [11] ,度量次正则 [12] [17] 和强度量次正则 [18] 。次微分映射作为一个集值映射,它的强度量次正则可以看作是二次连续可微函数的Hessian矩阵非奇异条件的一个推广,它作为一种稳健的稳定性条件,在非凸优化一阶下降算法全局收敛性和收敛率分析中起了非常重要的作用,近几年它得到了许多学者的关注和研究。2021年,Chieu [18] 利用次微分图像导数研究了有限维条件下次微分的二阶增长条件与强度量次正则性之间的关系。2022年,Bello-Cruz等人 [11] 研究了
正则优化问题,然后通过计算该模型中后者的次微分图像导数建立了该问题的强二阶增长条件。本文研究的带变换
罚函数的正则化问题在统计学习、信号处理和图像处理等领域有广泛的应用,但到目前为止,该问题的强度量次正则还没有学者进行研究,而强度量次正则在该类非凸问题的一阶下降算法收敛性分析中起着非常重要的作用。本文将借鉴文献 [11] 、文献 [16] 和文献 [18] 中研究强度量次正则 [19] [20] [21] [22] 的方法来研究问题(1)的强度量次正则,分别建立问题(1)的强度量次正则的充分条件和充要条件,为该类问题的非凸算法提供理论分析保障。
本文的结构框架如下:在第二节中主要介绍了邻近次微分和极限次微分的定义 [23] [24] ,以及主要的引理。第三节首先求出了变换
罚函数的邻近次微分和极限次微分表达式,然后利用集值映射的图像导数工具求出变换
罚函数的次微分图像导数表达式,最后利用该表达式建立了正则化问题(1)的强度量次正则的充分条件和充要条件。
2. 预备知识
本文,
表示实数集,
是n维欧式空间,
表示
中的范数,
表示
中的内积。
表
示以0为圆心,
为半径的球。
是二次可微连续函数,
表示该梯度的第j个元素,
表示该Hessian矩阵的第i行,第j列元素。集值映射
,集值映射F的逆映射
定义为:
,F的有效域
,F的图
。
是符号函数。
表示点
到集合
的距离。
定义2.1 [23] 设
,对于函数
和向量
,如果存在
和x的一个邻域V,使得对于任意的
有
则称v是函数g在x处的邻近次梯度。由这样的v构成的集合称为g在x处的邻近次微分,记作
。
定义2.2 [23] 函数
在
处的极限次微分定义如下:
其中
表示
和
。
定义2.3 [16] 设
是
的一个非空子集,
,
称为在
处对于集合
的(Bouligand-Severi)切锥。
定义2.4 [16] 考虑集值映射
,F的有效域为
,并且F的图为
。设
,以及
在
处的切锥为
。那么F在
处的图像导数是集值映射
,定义为
这意味着
。
因此,
当且仅当存在一个序列
,
和
使得对于任意的k有
定义2.5 [16] 映射
,如果
并且存在
以及
的一个邻域U和
的一个邻域V,使得
那么称映射F在
处是强度量次正则的。
引理2.6 [16] 集值映射
在
是局部闭的,F在
是强度量次正则的当且仅当
引理2.7 [16] 对于在x处可微的函数
,一个集值映射
和任意的
,有
3. 带变换
函数正则化问题次微分的强度量次正则
本节首先根据变换
函数的结构和邻近次微分的性质,计算出该函数的邻近次微分,然后根据邻近次微分和极限次微分的关系求得该函数的极限次微分,进而求得变换
罚函数次微分的图像导数表达式,以此为基础,再利用次微分的运算法则和图像导数的计算公式,最后建立了带变换
罚函数的正则化问题的强度量次正则的充分条件和充要条件。
命题3.1 变换
函数的邻近次微分表达式:
证明 因为
是可分离变量的函数。首先设
,由于
在
是可微的,在
处是不可微的。那么当
,求出
的次微分为
。当
时,由定义2.1,存在y属于t的一个邻域V和
,它在
处的邻近次微分计算如下:
当
时,有
令
,要求出其最小值,先求
由此可以得到
,那么
在
内是单调递增的,且
的最小值在
时取得,则有
又因为
,那么
,所以
在
内是单调递增的,则
。故有
。
当
时,有
令
,要求其最大值,首先求得
同理可得,由于
,则有
。
综上所述,
在
处的邻近次微分为
。那么
在
处的邻近次微分为
。且当
时,
的次微分为
。
命题3.2 变换
函数的极限次微分表达式:
证明 由定义2.2以及邻近次微分和极限次微分的关系,容易得到函数
的极限次微分表达式。
为了求
的图像导数表达式,设
,并引出以下记号:
命题3.3 (
的图像导数)
是非空的当且仅当
。且对于所有的
,有
(2)
证明 由命题3.2,对于任意的
,都有:
(3)
取任意的
,则存在序列
和
,使得
下面分类讨论:
情形1.1
,即
。由(3)式有
。若有一个
的子序列使得
则有
。当
,有
。
并且,当
时,求得
当
,有
。
当
时,求得
当
,有
。此外,再由(3)式有
当
,有
。
否则,存在
,对所有的
有
。则
,当
,有
。那么
。再由(3)式有
当
,则有
。
情形1.2
,即
,
。
当
,
时。存在足够大的常数
,当
时,存在
使得
。由 式有
或
。当
时,有
。当
,有
。当
时,对于
,因为
,所以它是有界的。故矛盾。
当
,
时。对于足够大的k,有
那么当
时,
当
,有
。故矛盾。
当
时,有
。那么
,当
,有
。
情形1.3
,即
和
。
如果有一个
的子序列使得
当
时,有
。那么可以得到
。由此求得
那么当
,有
。
当
时,有
。那么有
。由此求得
当
,有
。
那么对于
都有
。
由以上这三种情况的结论,可以得到
,那么(2)式中的“
”证明完成。
为了证明(2)式中的“
”,任取
和
满足对于
,有
,
或
,对于
,有
。那么对于任意的
,就只需要证明
,由此便可证明
。所以对于任意的
,定义集值映射:
和(2)式中的“
”证明一样,考虑j的三种情形。
情形2.1
,即
,
。
当
,有
,
。当k足够大时,有
。
当
,那么有
和
。
当k足够大并且
时,有
当k足够大并且
时,有
由此,当
时,都有
对于上述情况,都可以得到
。
情形2.2
,即
,
和
。
当k足够大时,有
和
。则
,那么有
情形2.3
,即
和
。
当
,那么有
,当k足够大时,有
当
,当
时,有
,那么有
当
时,有
,那么
所以,当
时,都有
。
由上述情况,都可以得到
。
综上所述,这三种情形都有
,因此
。
为了研究正则化问题(1)的强度量次正则,设
在
处是二次连续可微的,引出以下记号:
定理3.4 (
强度量次正则的充分条件)设
在
处是二次连续可微的。定义:
其中
和
都是对角矩阵,并且每个元素都为
。
若下面的两个条件中的一个条件成立:
(i)
。
(ii)
。
那么
在
处是强度量次正则的。
证明 设
,由引理2.7,有
(4)
那么可以得到
即
由命题3.3可知,对于所有的
,有
(5)
(1) 当
且
时,显然有
。由
有
,那么可以得到
。则
,即
。
由于
在
上是非奇异的,那么
。根据引理2.6,可以得到
在
处是强度量次正则的。
(2) 当
时,
。由于
,有
。故有
,那么
。则
,即
。
由于
在
上是非奇异的,那么
。根据引理2.6,可以得到
在
处是强度量次正则的。
为了建立正则化问题的强度量次正则的充要条件,记号I1,M1,J1,K1,
与前面相同,并引入以下记号:
定理3.5 (
强度量次正则的充要条件)设
在
处二次连续可微。则
在
处是强度量次正则的当且仅当
或
证明 先证充分性。
设
,由引理2.7,有
由此可得
再由(5)式,上式等价于:
或
或
那么有
。由引理2.6可以得到
在
处是强度量次正则的。
再证必要性。
若
在
处是强度量次正则的,那么有
。则根据
的图像导数表达式有
或
综上所述,充要条件得证。
4. 结束语
本文主要研究了一类带变换
罚函数的正则化问题的强度量次正则的充分条件和充要条件,丰富了带变换
罚函数的正则化问题和强度量次正则的理论知识,为该类问题的非凸算法提供了理论分析保障,这对于非凸优化一阶下降算法全局收敛性和收敛率分析有着非常重要的作用。在后续的工作中,将继续研究该正则化问题的稳定性,可以研究该问题的二阶增长条件及其与强度量次正则性的等价关系,并且以这些理论为基础探讨该问题相关优化算法的收敛性。
致谢
感谢审稿人和编辑对本文提出的宝贵意见。
基金项目
本文在重庆市自然科学基金(CSTB2022NSCQ-MSX0409, CSTB2022NSCQMSX0406, CQ-NCAM-2021-02)和重庆市教育委员会科技项目(KJZD-M202201303, KJQN202201349)资助下完成。