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.

本文提出一种求解惩罚估计（penalized estimation）问题的方法，该问题的惩罚函数为参数向量（parameter vectors）两两之差的函数。多数情形下，这类惩罚函数无法按参数向量实现可分离性。这一不尽人意的特性往往使得该惩罚函数难以适配大规模估计任务。为实现该估计问题的可分离求解，我们引入一组将每个参数向量与一组辅助变量（auxiliary variables）相绑定的等式约束（equality constraints）。借助这些辅助变量，我们可将原估计问题重构为既可按参数向量、亦可按辅助变量实现可分离的形式。这一可分离特性进一步使得我们可采用迭代格式（iterative scheme）求解该问题，因为每次迭代内的任务均可独立并行执行。仿真结果表明，该迭代格式在计算时间与内存占用（memory usage）方面优于传统同类方法。补充理论分析显示，该迭代格式可令目标函数趋近于最优值，其收敛速率为O(r−1)，其中<i>r</i>为迭代次数。本文的补充材料可在线获取。