A UNIFIED CONVERGENCE ANALYSIS OF BLOCK SUCCESSIVE MINIMIZATION METHODS FOR NONSMOOTH OPTIMIZATION
A UNIFIED CONVERGENCE ANALYSIS OF BLOCK SUCCESSIVE MINIMIZATION METHODS FOR NONSMOOTH OPTIMIZATION
复制标题
DOI：
10.1137/120891009
复制
发表时间：
2013-01-01
影响因子：
3.1
通讯作者：
Luo, Zhi-Quan
中科院分区：
文献类型：
--
作者：
Razaviyayn, Meisam;Hong, Mingyi;Luo, Zhi-Quan
块坐标下降法（BCD）被广泛用于求解多个块变量的连续函数f的极小化问题。在该方法的每次迭代中，优化单个变量块，而其余变量保持固定。为了保证BCD方法的收敛性，每个块变量的子问题需要求解到其唯一的全局最优解。不幸的是，这个要求对于许多实际场景来说往往限制太多。在本文中，我们研究了另一种不精确的BCD方法，它通过连续最小化f的一系列近似来更新可变块，这些近似要么是f的局部紧上界，要么是f的严格凸局部近似。这项工作的主要贡献包括相当广泛的一类这样的方法的收敛条件的特征，特别是对于目标函数是不可微或非凸的情况下。我们的结果统一和扩展了许多经典算法，如BCD方法，凸函数（DC）方法的差异，期望最大化（EM）算法，以及块向前向后分裂算法，所有这些都是流行的大规模优化问题，涉及大数据的现有收敛结果。
The block coordinate descent (BCD) method is widely used for minimizing a continuous function f of several block variables. At each iteration of this method, a single block of variables is optimized, while the remaining variables are held fixed. To ensure the convergence of the BCD method, the subproblem of each block variable needs to be solved to its unique global optimal. Unfortunately, this requirement is often too restrictive for many practical scenarios. In this paper, we study an alternative inexact BCD approach which updates the variable blocks by successively minimizing a sequence of approximations of f which are either locally tight upper bounds of f or strictly convex local approximations of f. The main contributions of this work include the characterizations of the convergence conditions for a fairly wide class of such methods, especially for the cases where the objective functions are either nondifferentiable or nonconvex. Our results unify and extend the existing convergence results for many classical algorithms such as the BCD method, the difference of convex functions (DC) method, the expectation maximization (EM) algorithm, as well as the block forward-backward splitting algorithm, all of which are popular for large scale optimization problems involving big data.