FaRSA for ℓ1-regularized convex optimization: local convergence and numerical experience
FaRSA for ℓ1-regularized convex optimization: local convergence and numerical experience
复制标题
用于ℓ1-正则化凸优化的 FaRSA：局部收敛和数值经验
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Daniel P. Robinson
中科院分区：
文献类型：
--
作者：
Tianyi Chen;Frank E. Curtis;Daniel P. Robinson
FaRSA是一种求可微凸函数与正则化函数之和最小的新方法。该方法的主要特征包括：(I)对应于在解的预测为非零的变量的一组演变的指数；(Ii)只需要在简化的空间中求解以减少每次迭代的计算代价的子问题；(Iii)确定每个子问题必须以多高的精度求解的条件，其允许采用共轭梯度或坐标下降技术；(Iv)在计算上实用的条件，指示何时应该更新当前子问题探索的子空间；以及(V)当决定应该扩展保存非零变量的指标集时，确保目标函数充分减小的减小的近端梯度步长。我们证明了该方法的全局收敛性，并在一组模型预测问题上用MatLab实现了它的性能。在这里，我们引入了一个增强子问题的终止条件，它允许我们证明迭代以超线性速度局部收敛。此外，我们还给出了公开可用的C语言实现的细节，并与其他最先进的解算器进行了大量的数值比较。
FaRSA is a new method for minimizing the sum of a differentiable convex function and an -norm regularizer. The main features of the method include: (i) an evolving set of indices corresponding to variables that are predicted to be nonzero at a solution; (ii) subproblems that only need to be solved in a reduced space to lessen per-iteration computational costs; (iii) conditions that determine how accurately each subproblem must be solved, which allow conjugate gradient or coordinate descent techniques to be employed; (iv) a computationally practical condition that dictates when the subspace explored by the current subproblem should be updated; and (v) a reduced proximal gradient step that ensures a sufficient decrease in the objective function when it is decided that the index set that holds the nonzero variables should be expanded. We proved global convergence of the method and demonstrated its performance on a set of model prediction problems with a Matlab implementation. Here, we introduce an enhanced subproblem termination condition that allows us to prove that the iterates converge locally at a superlinear rate. Moreover, we present the details of our publicly available C implementation along with extensive numerical comparisons to other state-of-the-art solvers.