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

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

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

其中

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

通過引入變量

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

1. 將原問題轉化為對偶問題
2. 利用增廣拉格朗日方法求解對偶問題
3. 子問題采用半光滑牛頓法

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

在我的另一篇文章中

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

里面講到了：

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

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

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

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

---

一、鄰近算子和Moreau Envelope

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

定義

1.臨近算子

性質

1. 是光滑函數，并且它的梯度為:
2. Moreau分解：
3. Moreau envelope分解：

---

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

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

其中

構建拉格朗日函數：

那么其對偶問題為：

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

其中第一部分關于

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

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

定義

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

中的函數一模一樣。

求到了對偶變量

其中

鄧康康：求解稀疏優化問題1——增廣拉格朗日方法+半光滑牛頓方法?zhuanlan.zhihu.com

---

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

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

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

首先根據

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

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

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

第一部分，

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

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

其中

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

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

二、總結

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

1. 臨近點方法求解原問題
2. 將子問題轉化到對偶形式
3. 半光滑牛頓法求解對偶問題

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

歡迎關注我的專欄

最優化理論和一階方法?zhuanlan.zhihu.com

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

知乎 - 安全中心?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.