欢迎来到天天文库
浏览记录
ID:53569173
大小:355.25 KB
页数:12页
时间:2020-04-18
《广义交替近似梯度算法的线性收敛分析-论文.pdf》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、2014年9月运筹学学报第18卷第3期Sept.,2014OperationsResearchTransactionsVl01.18No.3广义交替近似梯度算法的线性收敛分析半万芮1徐姿,摘要针对两个可分凸函数的和在线性约束下的极小化问题,在交替方向法的框架下,提出广义的交替近似梯度算法.在一定的条件下,该算法具有全局及线性收敛性.数值实验表明该算法有好的数值表现.关键词交替方向法,广义交替近似梯度算法,全局收敛,Q。线性收敛中图分类号O2242010数学分类号90C25Onthelinearconvergenceofthege
2、neralalternatingproximalgradientmethodforconvexminimizationWANRuiIXUZiI,十AbstractInthispaper.weproposeageneralalternatingproximalgradientmethodforlinearconstrainedconvexoptimizationproblemswiththeobjectivecontainingtwoseparablefunctions.0llrmethodisbasedontheframewor
3、kofalternatingdirectionmethodofmultipliers.TheglobalandlinearconvergenceoftheproposedmethodiSestablishedundercertainconditions.Numericalexperimentsshowthatthealgorithmhasgoodnumericalperformance.Keywordsalternatingdirectionmethodofmultipliers,generalalternatingproxim
4、algradientmethod;globalconvergence,Q—linearconvergenceChineseLibraryClassification02242010Ma七hematicsSubjectClassification90C250引言考虑在线性约束条件下,两个可分凸函数的和的极小化问题,其数学模型为inf(x)+g(y)∈R,yElPS.t.Ax+By=b,其中A∈,B∈p,b∈..厂:R,g:R都是凸函数收稿日期:2013年10月14日基金项目:国家自然科学基金资助项目(No.11101261)1.上
5、海大学理学院数学系,上海200444,DepartmentofMathematics,CollegeofSciences,ShanghaiUniversity,Shanghai200444,Chinat通讯作者Correspondingauthor,Email:xuziQshu.edu.ca2万芮,徐姿18卷近年来,因为凸优化模型(0.1)在稀疏优化和低秩优化问题中的应用,它已经引起很多研究人员和工程工作者们的关注.这类问题很多来源于压缩感知【]、低秩矩阵填充【2,3】、图像处理[415]和统计f6】等.它们关注的是问题的解具有
6、稀疏或者低秩的结构.[i==对于模型(0.1),一种有效的方法是交替方向法(AlternatingDirectionMethodofMul—mgg嘲m—tipliers,简称ADMM算法).它的迭代格式为一,●l●Jf、●【南),一<斗+,),(0.2)++++一6),I:lj壮一<+其q'L(,Y,A):f(x)+g(y)一AT(Ax+By—b)+lJAx+By一6川;是增广拉格朗日函数.ADMM算法对于图像处理、压缩感知、机器学习、半定规划和统计等方面提出的结构化的凸优化问题都很适用.它的优势在于把求解大规模的原问题转化为求
7、解较低维数的缸子问题,这在实际中提高了计算+效率.ADMM算法的全局收敛性已经得到论证.十一近些年来,有关ADMM算法及其变形算法的收敛速率的结果也有很多.Goldfarb和入BMa[7】证明了当目标函数光滑,且其梯度Lipschitz连续时,利用ADMM的Jacobi等价形,目标函数的下降速率为0({),且可以加速到o(矗).当f(x)和g()中只有一个函数光滑,且其+H梯度Lipschitz连续,利用Gauss.Seidel等价形,Goldfarb等[8]证明了收敛速率为0(丢).HeWNB卜Yuan[9】利用变分不等式原理
8、,在两个子问题至少有一个是可精确求解的前提下,证明了一Douglas—Rachford交替方向算法的收敛速率为O(丢).Goldstein等【l0]在目标函数强凸,其中一6一个函数为二次函数且两个子问题都可精确求解的条件下证明了ADMM变形式的对_L偶目标函数值
此文档下载收益归作者所有