第36卷第3期
哈尔滨师范大学自然科学学报Vol.36,No.32020 NATURAL SCIENCES JOURNAL OF HARBIN NORMAL UNIVERSITY
求解elastic-net正则化的软阈值迭代算法
李海龙，丁亮”
(东北林业大学)
【摘要】构造了一种新的迭代算法来求解线性不适定方程的elastic-net正则化问题，该算法利用广义条件梯度算法，将其推广到带有a||力||(|+|-||x||^罚
项的elastic-net正则化方程中，构造出一种适用于elastic-net正则化的软阈值迭
代算法，该算法结构简单，易于实现•此外，给出了该算法收敛性的证明.
【关键词】线性；稀疏正则化;elastic-net正则化；广义条件梯度算法；软阈值
迭代算法
中图分类号:0175文献标识码：A文章编号：1000-5617(2020)03-0006-04
0引言
该文研究线性不适定算子方程
Kx=y(1)
的求解问题.其中k：—丫为线性有界算子，丫为Hilbert空间.在实际应用中，由于存在误差，精确数据y不能预先得到，而观测数据护会因一些干扰因素而带扰动或噪声，且满足||y-/||yW 其中6为误差水平.若问题(1)的解是稀疏的或在一组基底下稀疏的，则通常采用稀疏正则化来求解线性不适定问题.
2004年，Daubechies,Defrie和De Mol首次提出了线性不适定问题的lp(\WpW2)稀疏正则化并建立了迭代软阈值算法的收敛性⑴.受文献［1］的启发，不适定问题的稀疏正则化的正则化性质和迭代算法迅速发展并趋于成熟，可见综述性论文［2-3］及其中的参考文献.然而经典的稀疏正则化方法对于条件数较大的不适定问题稳定性较差，例如图像去模糊等问题.因此，一些学者提出了elastic-net正则化⑷.作为多参数Tik-honov［5-61正则化中的一种，该正则化方法是在稀疏正则化的基础上添加了一个匚光滑项，使得新的目标泛函为
爭驭爲(x)=寺II Kx-y s||2+a||x\\；|+
f II x||?2⑵
其中a,0>O为正则化参数.从其形式中可看出elastic-net正则化同时具有光滑的Tikhonov正则化和稀疏正则化的优点•从统计学的角度看，相比于稀疏正则化，该正则化方法具有更好的稳定性
泛函丿爲最初用于统计,2005年，Hui Zou和Trevor Hastie首次在统计学上提出了elastic-net 正则化"•2009年，De Mol等给出了elastic-net 正则化在统计学习理论框架下的统计性质及迭代阈值算法⑷.2009年，Jin,Lorenz和Schffler提HiT elastic-net正则化，分析了正则解的稳定性和收敛性，还给出了两种Active-set算法⑷.
收稿日期:2020-04-12 *通讯作者
第3期求解elastic-net正则化的软阈值迭代算法7
2010年,UmanitdV和Villa S推导了求解elastic -net正则化的强收敛算法，并对正则化解的渐近性质进行了严格的研究⑼.2012年,Li和Chen 等人将elastic-net正则化推广到更一般的矩阵恢复(矩阵完成)设置，并给出了 Matrix elastic net(MEN)正则化算法问.2016年，Feng和Lv 等人提出了核化elastic net正则化，与经典的elastic net正则化相比，核化可以提高稀疏恢复能力［11］.2017年，Chen等人系统的对比了elastic-net正则化和经典的稀疏正则化.前者的稳定性更强，且当解为拟稀疏时，其反演结果更好⑴). 201
9年,Jing Wang等人提出了具有人-范数和12-范数凸组合项的elastic-net正则化方法求解非线性且严重不适定的EIT的图像重建问题2.
目前求解elastic-net正则化的数值算法主要是基于Active set的两种算法，该文主要目的是将广义条件梯度算法I"「切应用于elastic-net 正则化⑷中，推导出一种新的软阈值迭代算法.作为求解稀疏正则化的一种数值算法，软阈值迭代算法被很多学者证明是一种结构简单，容易实现的算法.该文借鉴文献［14］中广义条件梯度法对l p稀疏正则化方程的处理技巧，将(3)式中的•C改写为
丿爲(%)=F&)+©(%)
其中F(%)=j-\\Kx-y s||2-<9(x),0(x)= a II x||h+号||x||：+©(«)和®(%)=
||% ||?2.通过构造新的F(x)和⑦仏)满足广义条件梯度算法的条件，从而设计出一种新的软阈值迭代算法，并证明了此算法的收敛性.
该文结构如下：
(1)介绍广义条件梯度算法的内容.
(2)将广义条件梯度算法应用于elastic-net 正则化中.
(3)给出新算法中下降方向的求解方法.
1广义条件梯度算法
该文求解的elastic-net正则化的软阈值迭代算法是基于文献［14］中作者介绍的广义条件梯度算法，用于求解形式为
minF(%)+©(兀)(3)
x e H
的最小化问题.其中，H是Hilbert空间，F(%)在H上是连续Fr6chet可微的，④：77—>［-8,+8］不可微但是适定的、凸的、下半连续的和强制的.
定理1〔⑷令①是适定的、凸的、下半连续的和强制的，且对于Vt eR,E t=(u eH：0(u)}是紧集•令F是连续Fr6chet可微的，且在有界集上有界•假设F+©强制的，即如果||x||h-8，则F(%)+0(x)—>00.令u0wH，使得0(M o)< 8，令山”丨是由广义条件梯度算法生成的序列，则i U”!有一个收敛的子列，并且每一个收敛的子列都收敛到F+O的稳定点.
2广义条件梯度法在elastic-net 正则化中的应用
为了将广义条件梯度算法应用于问题(2)，将问题(2)中定义的化改写为如下形式
•/爲仏)=F(x)+O&)(4)在这里，令
F&)=*||心一护\\2-0(x),
0(x)=a||x||h+^-||x||i+®(%)
其中=导||切I：,a>O,0MO">O.因此，问题(2)可以表示为
minj爲(兀)(兀)+①(％)(5)
xet2
由于2|山和II II/2是适定的，凸的，下半连续的，强制的，显然①仏)在<2上是适定的，凸的，下半连续的和强制的，即0(%)是适定的，凸的，下半连续的，强制的.又因为||%II：是连续Fr6chet可微的，所以F(%)也是连续Fr6chet可微的.
算法1
(1)选择x o eH满足0(x o)<oo，令n=0.
(2)计算下降方向z”
min<X*(-/)-(A-/3)x…,z>+
zel2
8哈尔滨师范大学自然科学学报2020年第36卷
f hll^+ahll/,
(3)确定步长S"，即求解极值问题
min F(x…+s(z”-x J)+0(x…+s(z”-
se[0,l]正则化其实是破坏最优化
X”))
(4)令x n+i=Z n且71=71+1，返回步骤(2).
接下来讨论算法1的收敛性.首先回顾文献[14]中证明的四个结果.
引理1令F：HfR是Gateaux可微的，并且假设0满足条件1，则(5)的一阶优化条件为<F'(%),z-%>MO(%)-O(z),\/x,zwX
此条件等价于
<F'(x),x>+<P(x)=min<F'(x),z>+
ze//
叫)・
引理2令。满足条件1，且假设F是连续Fr6chet可微的，则
0(%)：=vF'(兀)，兀〉+。(兀)一
min(<F'(兀)，z>+①(z))(6) zeH
是下半连续的.
引理3假设x…eZ2不满足一阶优化条件，则有
F(j)+O(x”+i)WF(%”)+<p(x n).
引理4令是由算法1生成的序列，则lim)=0.
n
定理2令｛%”｝是由算法1生成的序列，则｛x n I有一个收敛的子列，并且每一个收敛的子列都收敛到J；p=F+O的稳定点.
证明由引理4可知lim0(%”)=0.利用引
n—><»
理1和引理2可知，因为lim^(x…)=0，所以有
n—>oo
lim•/爲(x…)=in卩爲(％).(7)
n x^l2
因为｛II X…II J是有界的，存在一个常数/和一个收敛子列lx…|，使得
因为是弱下半连续的，所以有
lim inf/爲(如)).(8) n
由(7)(8)可知in优,0(%)丸3)，所以
xe/2
inf•/爲(％)=•/爲(％*)•(9)
xel2
由(8)(9)可知limj^(x…)=丿爲(/)即
limy\\Kx n-y s||2+ft Q.,(x…)=~\\Kx--/112
其中陥(九)=小||z,+f||x||；2.又因为
y II怠”-y'f和心eg)是弱下半连续的，所以有
\mR a^x n)=R atP(x*)
因为心/(%)是有Radon-Riesz性质的，所以有务宀由引理2可知意味着lim inf0(£)M
n—h»
0(«
*)，则由引理4有0(x-)=0.
3确定算法1的下降方向Zn
由于F(x)是连续Fr6chet可微的，则F(x)的Fr6chet导数为F(x)=K'(Kx-y s)-(A-0)x，利用引理1可知，用于确定问题(5)的下降方向z”的一阶优化条件为
min<K
*(&”_y‘)-(入-0)%”，z>
+今l|z||；2+a||z||“(10)式(11)可以用逐点计算，则分量z，满足
z：+于sign(zj=((1-即x-十K*(Kx-/)).(ID 则式(12)的解可以表示为软阈值函数S于和S*.
引理5优化问题(5)的下降方向为
z”=5-2-.,((1
-*K气心”_犷))证明首先问题(10)等价于
™ny(II z II；2-2<(1-号)九-
j-K^Kx n-y s),z>+((1_¥)%-
*K(K x”-
/))2)+a2I Vz,®>I
i
即通过以上展开，可以将问题(10)等价地转化为
min工享1Vz,
zeH i2<(1
f)
>X n-
4
-^-K
*(Xx…-y s),<p;>I2+a(<z,<p,>I(12)现在应用凸分析的一个引理，对于每个适定的凸函数g-R—R,V>0都有
(1+r)dg)_1(x)=arg min\~—\a)-x\2
+
第3期
求解elastic - net 正则化的软阈值迭代算法
9
g(s) I
其中dg 表示g 的次微分.将这个结果应用于 (12)中求和的每个分量，令g(z) = I vz,® > I ,
Vie/V，则
(/ + fdg )_' ( • ) = arg min | -y I z - ( ( 1 -
X n --^-K * (Kx n -/) ) I 2 +al <z,(Pi > I !因此问题(10)的唯一极小值z 为
z ” =弓[(/ + ^dg )7((1 -号)%” -
则上式恰好形成了软阈值函数，即
(/ + -y-ag) ■'(X )=s “(％)
人
A
因此，z ” =*
」((1 •*¥)%” -(Kx n -y 5) )•
4结论
该文给出了求解elastic - net 正则化
人,0(%)=y II Kx-y\\2 +a || % || /, +
f K II
最小解的数值算法.对于上式的求解，难点在于 它的罚项为人和<2两项，而且人项不可微.因此 将广义条件梯度算法应用到elastic - net 正则化 问题中，构造出的F 和0满足广义条件梯度算
法的条件，从而得到了求解elastic - net 正则化 的软阈值迭代算法，该算法结构简单，易于实现，
并且证明了此算法的收敛性.
参 考文献
[1 ] Daubechies I , Defrise M , De Mol C. An iterative
thresholding algorithm for linear inverse problems with a
sparsity constraint [ J]. Communications on Pure and Applied Mathematics, 2004, 57(11)： 1413 - 1457.
[2 ] Daubechies I , Defrise M , De Mol C . Sparsity - enforcing
regularisation and ISTA revisited] J] . Inverse Problems , 2016, 32：104001.
[3] Jin B, Maass P, Scherzer 0. Sparsity regularization in
inverse problemsf J]. Inverse Problems , 2017, 33:[4]
Jin B , Lorenz D A , Schffler S. Elastic - Net Regulaization : Error estimates and Active Set Methods]J]. Inverse Problems, 2009, 25(11) ： 115022.
[5] Lu S, Wang W, Mao H, et al. Multi - parameter Tikhonov
regularization with the sparsity constraint [ J]. Inverse Problems, 2013, 29(6) : 065018.
[6]
Ito K, Jin B , Takeuchi T. Multi - Parameter Tikhonov Regularization] J]. Methods& Applications of Analysis,2011, 18(1)： 31 -46.
[7 ] Zou H , Hastie T. Regularization and variable selection via
the elastic net[J]. Journal of the Royal Statistical Society : Series B( Statistical Methodology) , 2005 , 67 (2) : 301 -
320.
[8] De Mol C , De Vito E, Rosasco L. Elastic - net regularization in learning theory [J]. Journal of
Complexity, 2009, 25(2) : 201 -230.
[9] Umanitd V, Villa S. Elastic - net regularization : iterative algorithms and asymptotic behavior of solutions[ J].
Numerical Functional Analysis and Optimization , 2010, 31(12)： 1406 - 1432.
[10] Li Hong, Chen Na, Li Luoqing. Error analysis for matrix
elastic - net regularization algorithms [ J ]. IEEE
Transactions on Neural Networks and Learning Systems ,2012, 23(5) : 737 -748.
[11] Feng Y L, Lv S G , Hang H Y, et al. Kernelized Elastic Net
Regularization :
Generalization Bounds, and Sparse
Recover[ J ]. Neural Computation, 2016, 28(3) : 525 - 562.
[12] Chen D , Hofmann B , Zou J. Elastic - net regularization
versus Z( 1 ) — regularization for linear inverse problems with quasi - sparse solutions [ J ]. Inverse Problems, 2017 ,
33(1) ： 015004.
[13] Jing Wang, Bo Han , Wei Wang. Elastic - net regularization
for nonlinear electrical impedance tomography with a splitting approach[ J]. Applicable Analysis, 2019,
98(12): 2201 -2217.
[14] Bredies K , Lorenz D A , Maass P. A generalized conditional
gradient method and its connection to an iterative shrinkage
method [ J ]. Computational Optimization and Applications ,
2009, 42(2) : 173 - 193.
[15] Bonesky T, Bredies K, Lorenz D A, et al. A generalized
conditional gradient method for nonlinear operator
equations with sparsity constraints] J]. Inverse Problems , 2007, 23(5) : 2041 _ 205&
[16] Rockafellar R T, Wets R J B. Variational Analysis[ M ].
Berlin ： Springer, 1998.
060301.
（下转第67页
）
第3期基于灰分析法下黄山市入境旅游服务贸易发展情况预测及影响因素研究67
Research on the Development of Inbound Tourism Service Trade in Huangshan City Based on Grey Analysis
Method and its Influencing Factors
Zhang Cheng,Xu Yunhua,Luo Mengyu
(Anhui University of Finance and Economics)
Abstract:By using the grey analysis method,the development of inbound tourism service trade in Huangshan city is predicted and its influencing factors is explored,and the reference basis for policy makers and other relevant personnel is provided.Firstly,taking the tourism foreign exchange income of
Huangshan from2012to2018as the original data,the grey forecasting model GM(1,1)is established to predict the change of the tourism foreign exchange income of Huangshan from2020to2023.Then from the economic development factors,infrastructure construction,resource factors,tourism demand factors and other four aspects,indicators are selected to build the evaluation system for grey correlation prediction analysis. Finally,a quantitative analysis of the data based on the grey theory is made,and relevant and effective suggestions for the development of Huangshan based on the impact of the international outbreak on the inbound tourism service trade in2020are put forward.
Keywords:Inbound tourism service trade；Grey prediction model；Grey relational prediction；Grey theory
(责任编辑：于达)
(上接第9页)
Iterative Soft Thresholding Algorithm
for Elastic-net Regularization
Li Hailong,Ding Liang
(Northeast Forestry University)
Abstract:In this paper,it is shown that a new iterative algorithm is constructed to solve elastic一net regularization problem for linear ill一posed equations.The new algorithm is based on the generalized conditional gradient algorithm,the generalized conditional gradient algorithm to elastic-net regularization
equation with the a||%||4||x||l2penalty is extended.A iterative soft threshold algorithm for elastic一net regularization is proposed.The algorithm has a simple structure and is easy to implement.In addition, the convergence property of the algorithm is proved.
Keywords:Linear；Sparse regularization；Elastic-net regularization；Generalized conditional gradient algorithm；Soft threshold algorithm
（责任编辑：于达）
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论