Solving Fused Penalty Estimation Problems via Block Splitting Algorithms

We propose a method for solving a penalized estimation problem in which the penalty function is a function of differences between pairs of parameter vectors. In most cases such a penalty function is not separable in terms of the parameter vectors. This undesirable property often makes large scale estimation difficult with the penalty function. To solve the estimation problem in a separable way, we introduce a set of equality constraints that connect each parameter vector to a group of auxiliary variables. These auxiliary variables allow us to reformulate the estimation problem that is separable either in terms of the parameter vectors or in terms of the auxiliary variables. This separable property further facilitates us to solve the problem with an iterative scheme in that tasks within each iteration can be carried out separately in parallel. Our simulation results show that the iterative scheme has advantages over its traditional counterpart in terms of computational time and memory usage. Additional theoretical analysis shows that the iterative scheme can make the objective function approach to the optimal value with a convergence rate O(r−1), where <i>r</i> is the iteration number. Supplementary materials for this article are available online.

本文提出一种求解惩罚估计问题的方法，该问题中的惩罚函数以参数向量对之间的差值为自变量。多数情况下，这类惩罚函数无法基于参数向量实现分离，这一缺陷往往使得该惩罚函数难以应用于大规模估计任务。为实现该估计问题的可分离求解，我们引入一组等式约束，将每个参数向量与一组辅助变量相关联。借助这些辅助变量，我们可将原估计问题重构为可基于参数向量或辅助变量实现分离的形式。该可分离特性进一步使得我们可通过迭代格式求解该问题，因为每次迭代中的各项任务均可独立并行执行。仿真结果表明，相较于传统迭代方法，本文提出的迭代格式在计算耗时与内存占用上均具备优势。额外的理论分析表明，该迭代格式可使目标函数以O(r⁻¹)的收敛速率趋近于最优值，其中r为迭代次数。本文的补充材料可在线获取。