班上大佬給討論班安排的目錄如下，所以我大概就按照這個思路來整理這一塊內容。我主要參考的就是S。Boyd、Deep ADMM-Net for Compressive Sensing MRI以及這篇部落格。

論文自取和參考書自取，連結：

https：//

pan。baidu。com/s/1Al57SO

mbXw12-xYWgv89eA

提取碼： jxah

ADMM(1)-Convex Analysis Seminar

因為涉及到的最佳化知識比較多，我就從最基本的開始整理，比如說對偶。

1。對偶

在求解一個最佳化命題時，如果其對偶形式便於求解，常常可以透過求解對偶問題來避免直接對原問題進行求解。比如機器學習中典型的SVM就涉及到對偶理論，以及拉格朗日乘子法、KKT條件等概念。細說的話，那就得長篇大論了。

對偶理論：一個最佳化命題也就有其對應的對偶最佳化命題，不過也有一些很難寫成顯示形式。

拉格朗日函式：將原最佳化命題的目標函式和約束整合成一個函式，一般記為

L

。

KKT條件：函式的最優值滿足的必要條件。（如果原問題是凸問題，則KKT條件為充要條件）

2。對偶上升法

對於凸函式的最佳化問題，對偶上升法核心思想就是引入一個對偶變數，然後利用交替最佳化的思路，使得兩者同時達到最優。一個凸函式的對偶函式其實就是原凸函式的一個下界，因此可以證明一個較好的性質：在強對偶性假設下，即最小化原凸函式（primal）等價於最大化對偶函式（dual），兩者會同時達到最優。這種轉化可以將原來很多的引數約束條件變得少了很多，以利於做最佳化。

\begin{array}{l}\min \quad f(x) \\ \text { s.t. } \quad A x=b\end{array} \Longrightarrow L(x, y)=f(x)+y^{T}(A x-b) \stackrel{\text { 對偶函式 }(\text { 下界 })}{\Longrightarrow} g(y)=\inf _{x} L(x, y)

在強對偶性的假設下，primal和dual問題同時達到最優，

x^{\star}=\arg \min _{x} L\left(x, y^{\star}\right)

。

因此，若對偶函式g（y）可導，便可以利用梯度上升法，交替更新引數，使得同時收斂到最優。迭代如下：

\begin{array}{l}x^{k+1}:=\arg \min _{x} L\left(x, y^{k}\right) \quad \\ y^{k+1}:=y^{k}+\alpha^{k} \nabla g(y)=y^{k}+\alpha^{k}\left(A x^{k+1}-b\right) \quad\end{array}

3。對偶分解法

雖然對偶上升法有缺陷，要求有些嚴格，但是他有一個非常好的性質，當目標函式f是可分的（separable）時候（或者說引數的特徵可分），整個問題可以拆解成多個子引數問題，分塊最佳化後彙集起來整體更新。這樣非常有利於並行化處理。形式化闡述如下：

\begin{array}{ll}\min & f(x)=\sum_{i=1}^{N} f_{i}\left(x_{i}\right), x_{i} \in \mathbf{R}^{n_{i}}, x \in \mathbf{R}^{n} \\ \text { s.t. } \quad A x=\sum_{i=1}^{N} A_{i} x_{i}=b\end{array} \Longrightarrow L(x, y)=\sum_{i=1}^{N} L_{i}\left(x_{i}, y\right)=\sum_{i=1}^{N}\left(f_{i}\left(x_{i}\right)+y^{T} A_{i} x_{i}-\frac{1}{N} y^{T} b\right)

因此可以看到其實下面在迭代最佳化時，第一步即可以拆分為多個子問題的並行最佳化，對偶變數更新不變這對於特徵特別多時還是很有用的。

4。增廣拉格朗日乘子法

從上面可以看到對偶上升法對於目標函式要求比較苛刻，為了放鬆假設條件，同時比較好最佳化，於是就有了增廣拉格朗日乘子法，目的就是放鬆對於f（x）嚴格凸的假設和其他一些條件，同時還能使得演算法更加穩健。

L_{\rho}(x, y)=f(x)+y^{T}(A x-b)+\frac{\rho}{2}\|A x-b\|_{2}^{2} \Longrightarrow \begin{array}{lc}\min & f(x)+\frac{\rho}{2}\|A x-b\|_{2}^{2} \\ & \text { s.t. } & A x=b\end{array}

從上面可以看到該問題等價於最初的問題，因為只要是可行解對目標函式就沒有影響，但是加了後面的懲罰項，懲罰項的好處是使得對偶函式在更一般的條件下可導。

\begin{array}{l}x^{k+1}=\arg \min _{x} L_{\rho}\left(x, y^{k}\right) \\ y^{k+1}=y^{k}+\rho\left(A x^{k+1}-b\right)\end{array}

上述也稱作乘子法，可能也是因為更新對偶變數y時步長由原來變化的

\alpha_k

轉為固定的

\rho

。該演算法在即使f（x）不是嚴格凸或者取值為+∞情況都可以成立，適用面更廣。同樣可以簡單證明primal變數x和對偶變數y可以同時達到最優。

雖然Augmented Lagrangians方法有優勢，但也破壞了對偶上升法的利用分解引數來並行的優勢。當f是separable時，對於Augmented Lagrangians卻是不可分解的（因為平方項寫成矩陣形式無法用之前那種分塊形式），因此在迭代的第一步時候無法並行最佳化。