邓康康，福州大学应用数学系在读博士生，研究方向:运筹优化算法设计与应用、流形优化。
本文转载自知乎专栏 求解稀疏优化问题1——增广拉格朗日方法+半光滑牛顿方法
原文链接：https://zhuanlan.zhihu.com/p/92230537
本文介绍了一种二阶方法去求解稀疏优化问题。首先在对偶问题上应用增广拉格朗日方法，对于其子问题采用半光滑牛顿法求解，问题的稀疏结构使得算法得到快速的求解。
在这个一阶方法盛行的时代中，二阶方法看起来不那么受欢迎，能想到的优点好像只有“精度高”，但是原始的二阶方法（Newton,trust region,cubic regularizarion Newton）代价实在是太大了。为了权衡优缺点，出现了很多“似二非二”的算法，比如拟牛顿（quasi Newton），随机牛顿（stochastic Newton），次采样牛顿（subsample Newton）。这篇文章想讲下二阶方法一个很有意思的应用：利用半光滑牛顿（semismooth Newton）快速求解稀疏问题。目前已经出了许多相关文章，主要来自孙德锋老师的团队。有兴趣的可以参考他的主页。关于理论性的东西我就不说了（好像你会似的），这里我想简单阐述下这些文章的主要思想。
这个问题太general了，并且特别多的一阶方法可以去求解它，比如临近梯度方法（proximal gradient）以及它的加速版FISTA；交替方向乘子法（ADMM），原始对偶（primal dual）等等。这些方法说快也挺快的，毕竟只用到了一阶信息。但是他们没有考虑到两点：
不多废话，开始。
一
增广拉格朗日方法求解（P）的对偶问题
二
半光滑牛顿法求解ALM子问题（5）
三
总结
首先我讲的这个是一个general的算法框架，非光滑函数不限于Lasso，可以是其他稀疏正则。差别就在于如何计算其临近算子的jacbi矩阵。目前主要的一些正则函数都出了文章了，参考孙老师主页
https://link.zhihu.com/?target=http%3A//www.polyu.edu.hk/ama/profile/dfsun/
虽然非光滑函数可以是任意凸的函数，但如果没有稀疏性或者其他结构的话，这个方法不见得有效。所以说没有一个一统江湖的方法，只有合适某类问题的方法。
参考文献
[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.
閱讀更多 運籌OR帷幄 的文章
