求解稀疏优化问题1——增广拉格朗日方法+半光滑牛顿方法

发布网友发布时间：2024-10-24 16:19

共1个回答

热心网友时间：2024-11-09 20:42

在当前一阶优化方法盛行的背景下，尽管二阶方法以其高精度吸引了一些关注，但其高昂的计算成本常常被提及。为寻求平衡，研究者们开发了一系列“似二非二”的算法，如拟牛顿法、随机牛顿和次采样牛顿，其中半光滑牛顿方法在稀疏问题求解中展现出独特的价值。孙德锋老师的团队在这方面贡献了许多研究成果，如果你感兴趣，可参考他的主页。

本文将聚焦于半光滑牛顿方法解决稀疏优化问题。首先，我们从一般问题出发，考虑如下表达式：

[公式]

其中[公式]，并且[公式]非常大。许多一阶方法，如临近梯度法和ADMM，虽然效率较高，但当[公式]很大时，效率会降低。半光滑牛顿方法利用了问题的特殊性，尤其是稀疏性。

具体来说，通过增广拉格朗日方法处理对偶问题，我们得到增广拉格朗日函数：

[公式]

在ALM的迭代过程中，关键在于解决[公式]的优化问题，利用半光滑牛顿法，我们利用临近算子的性质，将其简化为：

[公式]

这里，通过近似处理，即使目标函数复杂，但其梯度形式简单，便于求解。

半光滑牛顿法依赖于梯度和广义Hessian矩阵，当[公式]是稀疏的，其临近算子的雅可比矩阵通常是稀疏的，这使得每一步的计算复杂度接近于一阶算法，同时保持快速收敛。例如，当[公式]时，对角元素的计算可以简化为：

[公式]

总结起来，半光滑牛顿方法在处理稀疏优化问题时，巧妙地结合了二阶方法的精度和一阶方法的效率，是一种高效求解策略。

最后，对于进一步探索，你可以参考以下文献：

[1] Li X, Sun D, Toh K C. A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems[J]. SIAM Journal on Optimization, 2018, 28(1): 433-458.

[2] Beck, Amir. First-Order Methods in Optimization || Front Matter[J]. 10.1137/1.9781611974997:i-xii.