L1範數的最優化過程是怎麼樣的？梯度下降遇到不可導點怎麼辦？

01-03

對於目標函數中包含加性的非平滑項並使用梯度下降求解的問題，如果可以使用proximal operator，則解法如下：

假設目標函數為 $min_x f(x) + h(x)$ 其中 $f(x)$ 可導，而 $h(x)$ 不可導。

則每步迭代更新為 $x^{k+1} = Prox_{h,eta}(x^k - eta riangledown f(x^k))$

其中， $Prox_{h,eta} (x) = arg!min_y frac{1}{2eta}|y - x|^2 + h(y)$

如果 $h(x) = |x|_1$ ，也就是題目中要求的L1範數正則化，則對應的

$Prox_{h,eta} (x) = arg!min_y frac{1}{2eta}|y - x|^2 + |y|_1 = hat{y}$

$hat{y}_i = egin{cases} x_i - eta ext{if} x_i-eta > 0 \ x_i + eta ext{if} x_i+eta < 0 \ 0 ext{otherwise} \ end{cases}$

admm，天然適合解l1範數正則項問題，加十個l1正則項都能解

admm，fista，ista都簡直適合L1範數優化

而且通過改動了l1範數的係數也很容易寫出來同倫的演算法

目標函數不可導，要不讓構造一個函數去逼近呢？Huber函數。但比較麻煩的是要引入新的參數。

目標函數不可導，要不構造一個和導數性質相近的去逼近呢？凸函數的次梯度(或子梯度，subgradient)或者非凸函數的廣義梯度。利用次梯度的定義，就可以對目標函數含有L1的做梯度下降了。當然用得最多的還是Proximal Algorithms。

此外，Nesterov應該算是非光滑優化領域研究第一人了，其論文可以好好研究。感覺要不是因為不在美國，其影響力應該能與Boyd比肩。

我有個與題主差不多的問題，想問一下各位大牛：

L1範數更容易使某些特徵的係數降為0，是因為其最優解更容易出現在坐標軸的拐點處（不可導點）。而L2範數的最優解是在可導點。

---

我的問題是：

最優解在可導點和不可導點的不同之處在哪裡？

謝謝各位大牛的解答！！

首先感謝高票Eta的那個回答，但裡面的符號好像有點混亂，我重新整理了一下，如果不對，歡迎指出

我把L1範數優化的理解分為三重境界

----------------------------------------------------------------------------------------------------------------

第一境界：記住結論

到這裡就已經完了，下面都是解釋

---------------------------------------------------------------------------------------------------------------------

第二境界：知道上面的proximal mamping的如何推導出結論的分段函數

介紹一下上面的prox映射

proximal映射是關於函數h的一個映射

---------------------------------------------------------------------------------------------------------------------

第三境界：知道proximal mapping在這裡代表什麼，知道如何從目標函數展開泰勒公式，從而得到proximal mapping。（以下引用自西瓜書）

弱弱的問一句,為什麼不可以轉換成線性規劃?

可以參考這個 Proximal Algorithms

這個利用shrinkage operator 的定義和相關結論就可以