非凸两分块优化问题的一类惯性对称正则化交替方向乘子法.pdf
《非凸两分块优化问题的一类惯性对称正则化交替方向乘子法.pdf》由会员分享,可在线阅读,更多相关《非凸两分块优化问题的一类惯性对称正则化交替方向乘子法.pdf(16页珍藏版)》请在咨信网上搜索。
1、Vol.27No.3OperationsResearchTransactionsSep.,20232023年9 月第2 7 卷第3 期运筹学学报DOI:10.15960/ki.issn.1007-6093.2023.03.003非凸两分块优化问题的一类惯性对称正则化交替方向乘子法*彭建文1,t雷宏旺1摘要交替方向乘子法(ADMM)是一个求解可分离凸优化问题的的有效方法,然而,当目标函数存在非凸函数时,ADMM或许不收敛。本文提出一类带线性等式约束的非凸两分块优化问题的惯性对称正则化交替方向乘子法。在适当的假设条件下,建立了算法的全局收敛性。其次,在效益函数满足Kurdyka-Lojasiewi
2、cz(KL)性质时,建立了算法的强收敛性。最后,对算法进行了数值实验,结果说明算法是一种有效的方法。关键词交替方向乘子法,非凸优化问题,Kurdyka-Lojasiewicz(KL)性质,收敛性中图分类号0 2 2 1.62010数学分类号9 0 C25,9 0 C 30,49 M 37A class of inertial symmetric regularization alternatingdirection method of multipliers for nonconvextwo-block optimization*PENG Jianwenl,tLEI HongwanglAbst
3、ract The alternating direction method of multipliers(ADMM)is an validmethod for solving separable convex optimization problems,nevertheless,when the ob-jective function has a nonconvex function,ADMM may not converge.This paper pro-poses an inertial symmetric regularization alternating direction meth
4、od of multipliers fornonconvex two-block optimization problem with linear equality constraints.Under theappropriate hypothesis conditions,the global convergence of the algorithm is established.Secondly,When the benefit function satisfies the Kurdyka-Lojasiewicz(KL)property,thestrong convergence of t
5、he algorithm is established.Finally,numerical experiments areperformed on the algorithm,and the results show that the algorithm is an effectivemethod.Keywords the alternating direction method of multipliers,nonconvex optimizationproblem,Kurdyka-Lojasiewicz property,convergenceChinese Library Classif
6、ication O221.62010 Mathematics Subject Classification 90C25,90C30,49M37收稿日期:2 0 2 1-0 4-2 1*基金项目:国家自然科学基金重大项目(No.11991024),国家自然科学基金面上项目(12 2 7 10 7 1),重庆英才创新创业领军人才创新创业示范团队项目(No.CQYC20210309536),重庆市高校创新研究群体项目(No.CxQT20014),重庆市自然科学基金(No.cstc2021jcyj-msxmX0300)1.重庆师范大学数学科学学院,重庆40 1331;College of Mathem
7、atical Sciences,Ch o n g q i n g No r ma lUniversity,Chongqing 401331,China+通信作者E-mail:口3827卷彭建文,雷宏旺本文考虑如下带线性等式约束的两分块可分非凸优化问题:min f(c)+g(y)(1)s.t.Ac+By=b,其中f:RnRU+oo是正常下半连续函数,g:RmR是光滑的,A Rlxn,B RIm,bER。问题(1)的增广拉格朗日函数为:Cp(a,y,):=f()+g(y)-(入,Ac+By-b)+I/Ac+By-bll2,这里入ER为拉格朗日乘子,是一个惩罚参数。交替方向乘子法(ADMM)是根据D
8、ouglas-Rachford(DR)分裂思想1 建立起来的求解可分优化问题的一种分裂算法,其求解问题(1)的经典迭代格式如下:mk+1Eargmin(Cp(a,yh,Ah)c E R),yh+1 E arg min(Cp(ah+1,)a e Rm),(2)yh+1=入-(Arh+1+Byh+1 b),当f和g是凸函数时,ADMM的相关理论和应用已研究得较为完善与成熟,见文献2-7 。除了交替方向乘子法,19 7 9 年,Lions等人8 提出的一种Peaceman-Rachford分裂法同样可求解凸优化问题,迭代格式如下:(ak+1 E arg min(Cp(a,yh,*)la E R),k
9、+=-(Aak+1+Byk-b),y*+arg min(p(ah+1,.+)/E R),.(3)k+1=k+-(Aark+1+Byh+1=b),算法(3)与经典ADMM的不同之处是在迭代格式中多了一步乘子迭代更新项入+,这个思想最早来源于Peaceman和Rachford的分裂思想9 (又称PR分裂),因此,算法(3)可以看作ADMM的一种变形。近些年,有关非凸两分块的ADMM及收敛性分析研究不断涌现,见文献10-17 。Wang等人12 对经典ADMM的两个子问题都附以Bregman距离函数,在要求Bregman距离函数强凸的情况下,建立了BADMM的收敛性结果。Jian等人14 针对一类特
10、殊两分块优化问题提出了一种正则化ADMM,即对经典ADMM的第一个子问题正则化,在不要求正则项强凸的情况下,他们建立了RADMM的收敛性。Wu16等人针对问题(1)提出了一种对称的交替方向乘子法,迭代格式如下:ah+1 E arg min(Cp(a,y*,A*)la E R),*+=h-Q(Aak+1+Byk=b),yh+1 arg min(Cp(ak+1,*+2)/e E R),(4)+1=*+-(Ark+1+Byk+1 b),以看出,算法在乘子迭代更新项入+中附带了一个松弛系数E(-1,1),此系数有利加速算法收敛,在一些实际问题中可做恰当的选取,以求达到最佳数值效果。Jian等其393期
11、非凸两分块优化问题的一类惯性对称正则化交替方向乘子法人18 考虑如下非凸多分块优化问题:mmin f(a):=Z fi(ci),=1mS.t.Aici=b,=1中前m一1个函数为正常下半连续,fm光滑,Am为单位矩阵。他们提出了一种部分对称E则化交替方向乘子法(PSRADMM):k+1Eargmin(Cp(ai,rh,.,am,A1-,心1E argmin(p(at+1,2,at,.,cm,).k)+/2-2/,k+1心2k+1E arg min(Cp(at+1,am-1,cm-2,am-1,chk+1+llam-1-am-1llFm-12m-1(5)k+=入-rB(ZAkk+11+2%m-b
12、),1ch+l arg min(Cp(er+1,k+1,am-1,Cm,1k+2)mm-1k+1=入a+-s(ZAiak+1-b),=1其中F;E Rnixni(i=1,m1)为对称正定矩阵。在增广拉格朗日函数满足KL性质时,他们建立了算法(5)的强收敛性,并且保证了算法(5)的线性和次线性收敛率。最近,许多学者研究了带惯性的分裂算法19-2 3,,惯性技术最早是由Alvarez24提出,用来求解动力系统问题,它不只是利用当前迭代信息产生新的迭代点,而是利用当前迭代信息与上一步迭代信息产生新的迭代点,从而更好更快地找到最优解,其形式为:Zk=k+Qk(uk-uk-1),如今惯性技术广泛应用于求
13、解各类优化问题,但惯性技术在非凸优化问题的ADMM算法中却较少研究。综合上述分析,基于问题(1),考虑矩阵B列满秩时,问题(1)中线性等式约束两边同乘(BTB)-1BT,使得最后的矩阵可变为单位矩阵,在一些实际应用中也大量存在B为单位矩阵这一情况,如压缩感知2 5,2 6 ,非凸经济调度问题2 7 等。于是,为了方便构造算法和建立其收敛性,在问题中设B为阶单位矩阵。因此,本文考虑求解问题(1)的一类带惯性项的对称正则化交替方向乘子法:算法ISRADMM初始点选取,y,,并且,p0,Vk1,0Pp。按如下选代更新点列(wk:=(ch,yh,入h):ak+1 e arg min(Cp(r,yh,x
14、*)+ll-alle),(6a)h+=入-(Aak+1+gh-b),(6b)yk+1 E arg min(Cp(ak+1,y,*+)+Pk(y,yh-1-yh),(6c)a+1=+-(Aak+1+yh+1 b),(6d)4027卷彭建文,雷宏旺其中GERnxn为对称正定矩阵。注1(1)当Vk1,Pk=0,G=0 且只令算法ISRADMM最后一步中的松弛系数=1时,算法ISRADMM可退化至算法(4);若pk=0,G=0且松弛系数=1时,算法ISRADMM可退化为算法(3);算法ISRADMM与算法PSRADMM(退化至两块形式)不同的是在(6 c)式上附以惯性项pk(y,yk-1-l),且算法
15、PSRADMM中的松弛因子选取不同,因此,在数值实验中可与ISRADMM取同一值。(2)算法ISRADMM中,对子问题加上一个正则项,实际上对子问题进行线性化处理,从而简化了子问题的求解,使得子问题更易获取最优解。即令G=uI-ATA(u0),则式(6 a)中关于c子问题可简化为E arg min(a)+l-d),k+1其中dk=ak+AT(k-(Aak+yk-b)为一已知量。(3)算法ISRADMM中,我们称pk(y,yk-1-y*)为惯性项,这可使y子问题能利用上一步迭代信息和当前迭代信息产生新的迭代点。实际上,通过给y子问题附以惯性项,可以使得迭代点有一个yk一yk-1方向的加速下降趋势
16、,从而对算法有一个加速的效果。1预备知识本文用Rn表示n维欧式空间,lll表示欧式范数。对任意c,yERn,规定它们的内积为(c,)=Ty,的G范数al=VaTGa,这里G为对称半正定矩阵。G()0 说明G为对称半正定(正定)矩阵,入min(G)与入max(G)分别说明对称矩阵G的最小特征值以及最大特征值,有入min(G)lal la/入max(G)lal2,Va E R。对任意集合SRn,任意点aER到S的距离定义如下:inflly-all,S+,d(,S):=yES+8,S=O。定义函数f:RnRU+的有效域为:domf:=E Rn:f()+),若domf,则称f为正常函数。定义 12 8
17、 若函数f:Rn RU(+)在ao处满足f(co)l i mi n f f(),则表示函数f在co处是下半连续的,假设f在其有效域内的每一点处都满足下半连续性,则称f为下半连续函数。定义2 2 8 设函数f:Rn RU(+8 正常下半连续,(1)函数f在aEdomf处的Frechet次微分,定义为所有满足下面条件的*的集合,记作f()f(y)-f()-(c*,y-c)lim _infyta,yaIly-all若 domf,令af():=。(2)函数f在Edomf处的极限次微分,记为af(),定义如下:8f(a):=C*ERn:3TT+f(a),an eaf(an),cn a*)413期非凸两分
18、块优化问题的一类惯性对称正则化交替方向乘子法注2 从上述定义,我们可以得到如下次微分的性质:(1)VRn,f(a)af(),其中f()为闭凸集,而af(c)仅为闭集。(2)设a E of(ak)且,lim(ak,)=(c,*),则a*Of(r)。k一(3)若ERn为f的极小点,则0 f(a)。若0 f(),则称a为f的稳定点(或临界点),函数稳定点的集合记为critf。(4)若函数f:Rn RU +o o)为正常下半连续函数,g:RnR连续可微,则对于任意 E domf,有a(f+g)()=of()+Vg(c)。定义3若w*:=(a*,y*,入*)为问题(1)的增广拉格朗日函数C(c,y,入)
19、的稳定点,即oEOL(w*),当且仅当AT)*E of(*),Vg(y*)=入*,Ac*+y*-b=0。定义 42 9(Kurdyka-Lojasiewicz性质)函数f:Rn RU【+o o 为正常下半连续函数,令-m2+0,记mfn2:=(R:nf(a)0;(4)V E Unf(*)f 0,0,pEm,使得对任意E及任意属于如下交集(E Rn:d(,2)e)nf(a)f O,使得对任意a,yERn,都有:lb(y)-(a)-(V(c),y-a)/2收敛性分析在建立算法ISRADMM的收敛性之前需做如下假设。(8)4227卷彭建文,雷宏旺假设1(1)目标函数f:Rn RU【+)是正常下半连续
20、函数,函数g:Rm R是连续可微的,并且Vg利普希茨连续(利普希茨常数为L),即V,yE Rp,有Vg()-Vg(y)Lc-yl。G ERn x n 为对称正定矩阵;(2)E(4/5,1),Vk 1,0 pkp;-102+18-8(4)记:=min81,02,其中01:=1 mn(G)-280,mx(AT A)0,02:=(-52+9-4)8-(74g2m-8D)-4L-82 2B0。基于算法ISRADMM中每个子问题的最优性必要条件,有(0EOf(ah+1)-ATh+AT(Aak+11+yh b)+G(ak+1(7a)h+1/2=入-(Aak+1+yh=b),(7b)0=Vg(yh+1)-h
21、+1/2+(Aa+1+yh+1-b)+pk(yk-1-yh),(7c)入h+1=h+1/2=(Arh+1,k+1-b)。(7d)且始终假设迭代序列wk=(k,yk,)有界,令:(wk=(ah,gk,Ah,gk-1,y,(w=(c,y,y,y)。算法ISRADMM的收敛性分析需要基于如下效益函数:C(a,y,入,9,g)=Lp(ac,y,a)+8p?+pB2p22YB下面的引理3表明序列 C(wk)单调下降。为了方便分析,令:=(c,y)。引理3若假设1成立,则有C(k+1)C(k)-0llzk+1-zl2证明首先,由最优性条件的(7 b)式和(7 d)式,有uk+1,入k+1)=Cg(akk+
22、1k+11,k+1/2)+/Aak+1+k+1C(ak+1与Lp(ak+1,入+1/Aak+1+ykbll(9)另一方面,由增广拉格朗日函数的定义和最优性条件的(7 c)式,有,k+1k+1Lp(ak+1k+1/2-,yKg(yk+1)-g(gh)(+1/2 (Aah+1+yh+1 b),yhk+1ak+12Bg(yk+1)-g(y+1yhll-(Vg(gk+1)+pikk+1。(10)又由g的利普希茨连续性及引理2,有-g(yh)-(Vg(gk+1)+pk(yhl/2-(p:(gk-1,+1(11)433期非凸两分块优化问题的一类惯性对称正则化交替方向乘子法将(11)式代入(10)式,有1,
23、+1,+1/2)Lp(ck+1,h,*+1/2)CB(k+1一luh+1-y/ll-(pk(gk-1-yh),yh+1-yh(12)又因为ck+1为子问题(6 a)的最优解,则有(ah+1,uh,)-Cp(a,h,t)-2+1-2hlkk+1112ain(G)(13)2因此,将(8),(9),(12)和(13)式相加,有Cg(ak+1,yyh+1,h+1)-Lp(ch,yh,h)a(G)/h+1-a*l+l/Aah+1+yh-llTk+121229一yh+1-yh)+BllAah+1,k+12一1(14)一一又由(6 b)式和(6 d)式,有1Aak+1+ykk入k+1)k+1(15)22十1
24、k+111k+1(16)A922另一方面,由(6 d)式和(7 c)式,可得k+1=)(Ack+1+yk+1 b),结合Vg的利普希茨连续性,有1入+1入*(L+(1-)lgh+1-gl+(1-)/A(a+1-a)l+pill/yk-1l Ppk-1 lk-1,k-2(17)进而,对(17)式利用柯西不等式,有4(L+(1-)lgk+1,*+432(1-)1/(ak+1-)12+4pll/k-yh-1+4p元-1lk-2112uk-1(18)于是,结合(15),(16)和(18)式,有l/Aah+1+yh-ll+/Aak+1+k+11Bk+1u2P22 2+4(L+(1-),k+12(1Ama
25、x(ATA)llak+1-ahll2B2p2p(19)4427卷彭建文,雷宏旺将(19)式带入(14)式,有yh+1,h+1)-Lp(ah,gh,h)k+12(1-)(G)+入max(ATA)k+1minY2(52-9+4)2+(p+8L-7L)+4L24p2+k+12B2B等价为下式:8p2+pB2.k+12p2-yk-1l2-Cp(ah,h,h)2,k+1Cp(ck+1,1k+12By8p2+pB2p2nin(G)_ 28(1-)2,(ATA)max2B1-2*1 (-52+9-4)2+(7L1=20m-8L)-4L2-8p2 k+1k+12B因此,有L(k+1)C(ok)-ilaC(h)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 两分 优化 问题 一类 惯性 对称 正则 交替 方向 乘子法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。