鄧康康，福州大學應用數學系在讀博士生，研究方向:運籌優化算法設計與應用、流形優化。
本文轉載自知乎專欄 求解稀疏優化問題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帷幄 的文章
