這篇文章是我之前一篇文章的兄弟篇，沒看過的可以看下面這個。

鄧康康：求解稀疏優(yōu)化問題——半光滑牛頓方法?zhuanlan.zhihu.com

我們考慮的問題仍然是如下的一般問題：

其中

,并且 特別大；

• 表示一個凸可微函數(shù)，例如
• 表示一個閉真凸函數(shù)，一般為稀疏正則函數(shù)，比如 LASSO： ，Fused LASSO，Clustered LASSO等

通過引入變量

，我們先把（P）轉化為約束問題

于是我們得到（P）的對偶問題為：

在之前的那篇文章中，我提到了怎么利用增廣拉格朗日方法（ALM）去求解對偶問題（D）,該方法中的子問題采用的是半光滑牛頓法。 主要idea大概分為三步：

將原問題轉化為對偶問題

利用增廣拉格朗日方法求解對偶問題

子問題采用半光滑牛頓法

主要代價在于半光滑牛頓法，而由于非光滑函數(shù)

的稀疏性，導致子問題中的Jacobian矩陣也是稀疏的，進而大大降低了該方法的計算量。本質上，這個方法是一個應用于對偶問題上的增廣拉格朗日方法。這篇文章我們換個角度，從原始問題（P）出發(fā)去設計算法。

在我的另一篇文章中

鄧康康：原始對偶角度下的幾類優(yōu)化方法?zhuanlan.zhihu.com

里面講到了：

對偶問題上的臨近點方法等價于原問題上的增廣拉格朗日方法。

而對偶問題的對偶問題是原問題。所以我們是不是有，

原始問題上的臨近點方法等價于對偶問題上的增廣拉格朗日方法？

所以這篇文章我們來講述臨近點方法應用到原始問題。參考的是孫老師的兩篇文章，見文章末尾的參考文獻。

---

一、鄰近算子和Moreau Envelope

首先，我給出一些需要用到的一些定義和性質。

定義

1.臨近算子

2. Moreau envelope

性質

是光滑函數(shù)，并且它的梯度為:

Moreau分解：

Moreau envelope分解：

---

二、臨近點方法求解原問題

首先，臨近點方法有如下迭代形式：

其中

表示罰參數(shù)。現(xiàn)在關鍵在于這個子問題怎么求？這要是沒有 就好了，直接一個臨近算子就搞定。 既然不好求，那我們就變成對偶問題去看看。首先對（1）做變量替換，轉化為約束問題：

構建拉格朗日函數(shù)：

那么其對偶問題為：

我們最終要求的就是對偶問題（D.1）。需要說明一下，這里的原始問題（P.1）和對偶問題（D.1）是針對臨近點方法的子問題而言的。我們來看一下對偶問題（D.1）的目標函數(shù)

的表達式：

其中第一部分關于

的問題是一個臨近算子，最后一個等式就是將 的臨近算子表達式代入。顯然上式看起來很復雜，接下來我們來簡化上式：

第一個等式用到了定義2，第二個等式用到了性質3。

最終我們將對偶問題（D.1）轉化為如下問題：

定義

為：

這個函數(shù)跟 鄧康康：求解稀疏優(yōu)化問題1——增廣拉格朗日方法+半光滑牛頓方法

中的函數(shù)一模一樣。

求到了對偶變量

之后，最終我們是要去得到 . 在式子（3）中我們知道二者的關系是：

綜合一下最終的迭代過程為：

其中

問題的求解采用的是半光滑牛頓法，具體的jacbi矩陣怎么求，稀疏性怎么利用參考下面這篇文章鄧康康：求解稀疏優(yōu)化問題1——增廣拉格朗日方法+半光滑牛頓方法?zhuanlan.zhihu.com

---

三、半光滑牛頓法求解對偶問題（D.1）

根據(jù)上面的推導，我們知道求解對偶問題（D.1）等價于求解

因為上述問題是個凸問題，我們只要找到梯度等于0的點即可：

首先根據(jù)

是個強凸函數(shù)，所以其共軛 是光滑的，再結合性質1，我們知道 是一個光滑函數(shù)，其梯度表達式為：

第一個等式用到了性質1，第二個等式用到了性質2。這里說一下為什么是半光滑牛頓法，因為

雖然函數(shù)光滑，但臨近算子的存在導致這個函數(shù)的梯度不是光滑的。

有了梯度之后，我們來求解其廣義Jacobian矩陣。

第一部分，

通常很簡單，比如二范數(shù)的平方。因此求二階導也不需要什么計算量。關鍵的地方在于計算后面這部分。當 是稀疏正則的時候，我們發(fā)現(xiàn)它的臨近算子的導數(shù)通常是稀疏的。舉例1范數(shù)正則，當 ，其臨近算子的導數(shù) 是一個對角矩陣，且對角元為：

這樣的話，（8）的后面這部分，我們只需要計算由非零元對應矩陣

的列構成的子矩陣相乘即可，當非零元較少的時候，這個計算量是很小的。

最后我們給出半光滑牛頓法的迭代過程：

其中

。

半光滑牛頓法迭代完之后，令

.這樣就完成了臨近點方法的第k次迭代。

再說一下：（5）是我們的外迭代，也就是臨近點方法求解原問題。而（8）是用半光滑牛頓法求解（5）中的第一個子問題。Over！

二、總結

最后梳理下這篇文章的idea：

臨近點方法求解原問題

將子問題轉化到對偶形式

半光滑牛頓法求解對偶問題

• 在之前那篇文章中，增廣拉格朗日方法中的罰參數(shù)就對應于這里臨近點方法的罰參數(shù)。二者的迭代是一樣的，只不過在參數(shù)的選擇和收斂性分析方面會有不同。
• 不同角度理解問題，得到不同的方法，雖然本質上是一樣的，但由此帶來的延伸就不一樣了，在增廣拉格朗日方法和臨近點方法上的改進可以完全不同。

歡迎關注我的專欄

最優(yōu)化理論和一階方法?zhuanlan.zhihu.com

詳細內(nèi)容和理論證明可以看孫德鋒老師主頁：

知乎 - 安全中心?www.polyu.edu.hk

參考文獻

[1] Zhang Y, Zhang N, Sun D, et al. A Proximal Point Dual Newton Algorithm for Solving Group Graphical Lasso Problems[J]. arXiv preprint arXiv:1906.04647, 2019.

[2] Lin M, Sun D, Toh K C, et al. A dual Newton based preconditioned proximal point algorithm for exclusive lasso models[J]. arXiv preprint arXiv:1902.00151, 2019.

總結

以上是生活随笔為你收集整理的割线法求解过程_求解稀疏优化问题2——临近点方法+半光滑牛顿法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。