RATE OF CONVERGENCE ANALYSIS OF DECOMPOSITION METHODS BASED ON THE PROXIMAL METHOD OF MULTIPLIERS FOR CONVEX MINIMIZATION
RATE OF CONVERGENCE ANALYSIS OF DECOMPOSITION METHODS BASED ON THE PROXIMAL METHOD OF MULTIPLIERS FOR CONVEX MINIMIZATION
复制标题
DOI：
10.1137/130910774
复制
发表时间：
2014-01-01
影响因子：
3.1
通讯作者：
Teboulle, Marc
中科院分区：
文献类型：
--
作者：
Shefi, Ron;Teboulle, Marc
本文介绍了两类基于乘子近端方法（PMM）的分解算法，该方法是由罗卡费勒在20世纪70年代中期针对凸极小化问题提出的。我们首先表明，PMM框架是文献中许多过去和近期提出的分解方案的根源，通过一个统一的方案能够对这些方法进行基本分析。然后，我们针对这两类基于PMM的分解算法，在函数值和约束违反方面证明了各种次线性全局收敛速率结果。此外，在对问题数据的一个温和假设下，我们针对这两类算法都推导出了关于原始原始函数值的收敛速率结果。作为我们分析的一个副产品，我们还得到了这两类算法所产生的序列收敛到最优原始 - 对偶解。
This paper presents two classes of decomposition algorithms based on the proximal method of multipliers (PMM) introduced in the mid-1970s by Rockafellar for convex minimization. We first show that the PMM framework is at the root of many past and recent decomposition schemes suggested in the literature allowing for an elementary analysis of these methods through a unified scheme. We then prove various sublinear global convergence rate results for the two classes of PMM based decomposition algorithms for function values and constraints violation. Furthermore, under a mild assumption on the problem's data we derive rate of convergence results in terms of the original primal function values for both classes. As a by-product of our analysis we also obtain convergence of the sequences produced by the two algorithm classes to optimal primal-dual solutions.