广义交替近似梯度算法的线性收敛分析-论文.pdf

《广义交替近似梯度算法的线性收敛分析-论文.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偶目标函数值