ON THE CONVERGENCE OF BLOCK COORDINATE DESCENT TYPE METHODS
ON THE CONVERGENCE OF BLOCK COORDINATE DESCENT TYPE METHODS
复制标题
DOI：
10.1137/120887679
复制
发表时间：
2013-01-01
影响因子：
3.1
通讯作者：
Tetruashvili, Luba
中科院分区：
文献类型：
--
作者：
Beck, Amir;Tetruashvili, Luba
本文研究了决策变量向量被分成若干个变量块的光滑凸规划问题。我们分析了块坐标梯度投影方法，其中每个迭代包括执行梯度投影步骤相对于在循环顺序采取的某个块。建立了该方法的全局次线性收敛速度，并证明了当问题无约束时，该方法可以加速收敛。在无约束的设置，我们还证明了所谓的交替最小化方法的块的数量是两个时的次线性收敛速度的结果。当目标函数也是强凸时，得到了线性收敛速度。
In this paper we study smooth convex programming problems where the decision variables vector is split into several blocks of variables. We analyze the block coordinate gradient projection method in which each iteration consists of performing a gradient projection step with respect to a certain block taken in a cyclic order. Global sublinear rate of convergence of this method is established and it is shown that it can be accelerated when the problem is unconstrained. In the unconstrained setting we also prove a sublinear rate of convergence result for the so-called alternating minimization method when the number of blocks is two. When the objective function is also assumed to be strongly convex, linear rate of convergence is established.