ON THE CONVERGENCE OF ALTERNATING MINIMIZATION FOR CONVEX PROGRAMMING WITH APPLICATIONS TO ITERATIVELY REWEIGHTED LEAST SQUARES AND DECOMPOSITION SCHEMES
ON THE CONVERGENCE OF ALTERNATING MINIMIZATION FOR CONVEX PROGRAMMING WITH APPLICATIONS TO ITERATIVELY REWEIGHTED LEAST SQUARES AND DECOMPOSITION SCHEMES
复制标题
DOI：
10.1137/13094829x
复制
发表时间：
2015-01-01
影响因子：
3.1
通讯作者：
Beck, Amir
中科院分区：
文献类型：
--
作者：
Beck, Amir
本文与解决凸最小化问题的交替最小化（AM）方法有关，其中决策变量向量分为两个块。目标函数是可分离的凸函数和可分离的（可能）非平滑扩展实价凸功能的总和，因此可以合并约束。我们分析了该方法的收敛速率，并建立了非反应倍率的收敛速率，其中乘法常数取决于最小的块Lipschitz常数。然后，我们分析迭代重新加权的最小二乘（IRLS）方法，用于解决涉及规范总和的凸问题。基于AM方法得出的结果，我们建立了IRLS方法的非肌电肌收敛速率。此外，我们还显示了渐近收敛速率，其效率估计不取决于问题的数据。最后，我们研究了旨在解决复合凸模型的基于分解方法的收敛性。
This paper is concerned with the alternating minimization (AM) method for solving convex minimization problems where the decision variables vector is split into two blocks. The objective function is a sum of a differentiable convex function and a separable (possibly) nonsmooth extended real-valued convex function, and consequently constraints can be incorporated. We analyze the convergence rate of the method and establish a nonasymptotic sublinear rate of convergence where the multiplicative constant depends on the minimal block Lipschitz constant. We then analyze the iteratively reweighted least squares (IRLS) method for solving convex problems involving sums of norms. Based on the results derived for the AM method, we establish a nonasymptotic sublinear rate of convergence of the IRLS method. In addition, we show an asymptotic rate of convergence whose efficiency estimate does not depend on the data of the problem. Finally, we study the convergence properties of a decomposition-based approach designed to solve a composite convex model.