機器學習與控制:ADMM的ODE模型與基于Lyapunov的收斂分析
- 前言
-
- ADMM算法
- Lyapunov函數
- ADMM算法的ODE模型
- 基于Lypunov函數的算法穩定性與收斂分析
前言
機器學習與控制領域的結合研究最近得到很多研究者的關注,但是文獻中的數學推導與讨論往往省略了很多細節與背景知識,本系列的文章主要基于最新文獻,嘗試複現并詳化其中的數學推導與讨論,希望剛剛入門的同學也可以很容易地了解。也歡迎各位同學的批評指正,共同學習!
本文是機器學習與控制系列的第一篇文章,主要深入介紹交替方向乘子法 Alternating Direction Method of Multipliers(ADMM)算法的常微分方程 Ordinary Differential Equation(ODE)模型以及基于Lyapunov函數的收斂分析。優化算法的收斂速度分析往往比較複雜,而且沒有統一的數學工具來分析。将優化算法轉換為ODE方程,然後結合控制理論中簡單的穩定性分析,我們可以很容易地得到算法的收斂速度。本文中我們将使用Lyapunov函數的方法來分析得到的ODE方程的穩定性,進而得出收斂速度。
本文主要分為一下幾個部分,第一部分為ADMM背景介紹,簡單介紹ADMM優化算法以及ODE模組化優化算法的背景;第二部分主要介紹Lyapunov函數的背景知識;第三部分詳細推導如何用ODE模組化ADMM算法;最後通過Lypunov函數分析ADMM算法的收斂速度。有基礎的同學可以跳着閱讀。
注:本篇博文基于以下文獻:ADMM and accelerated ADMM as continuous dynamical systems.[^1]
ADMM算法
假設我們考慮如下的優化問題:
min ( x , z ) ∈ R n × R m { V ( x , z ) : = f ( x ) + g ( z ) } s.t. z = A x \text{min}_{(x,z)\in R^{n} \times R^{m}}\ \{ V(x,z):=f(x)+g(z) \} \\\ \text{s.t.}\ \ \ z = Ax min(x,z)∈Rn×Rm {V(x,z):=f(x)+g(z)} s.t. z=Ax
其中:
- f f f 和 g g g 均可導且為凸函數
- 矩陣 A A A 列滿秩
- V ( x , z ) : = f ( x ) + g ( z ) V(x,z):=f(x)+g(z) V(x,z):=f(x)+g(z)
- V ( x , z ) : = f ( x ) + g ( A x ) V(x,z):=f(x)+g(Ax) V(x,z):=f(x)+g(Ax)
ADMM的疊代更新如下:
x k + 1 = arg min x f ( x ) + ρ 2 ∥ A x − z k + u k ∥ 2 , ( 1 a ) z k + 1 = arg min z g ( x ) + ρ 2 ∥ A x k + 1 − z + u k ∥ 2 , ( 1 b ) u k + 1 = u k + A x k + 1 − z k + 1 , ( 1 c ) x_{k+1} = \text{arg min}_{x} \ f(x) + \frac{\rho}{2} \| Ax-z_k+u_k \|^2, \ \ \ (1a)\\ z_{k+1} = \text{arg min}_{z}\ g(x) + \frac{\rho}{2} \| Ax_{k+1}-z+u_k \|^2,\ \ \ (1b)\\ u_{k+1} = u_k + Ax_{k+1} - z_{k+1},\ \ \ (1c) xk+1=arg minx f(x)+2ρ∥Ax−zk+uk∥2, (1a)zk+1=arg minz g(x)+2ρ∥Axk+1−z+uk∥2, (1b)uk+1=uk+Axk+1−zk+1, (1c)
其中 ρ > 0 \rho> 0 ρ>0為懲罰參數, u k ∈ R m u_k\in R^m uk∈Rm 是限制條件 z = A x z = Ax z=Ax 的第 k k k 個拉格朗日乘數估計。
Lyapunov函數
Lyapunov函數為控制理論中很重要的用來分析系統平衡點穩定性的工具。簡單來說,我們針對某個系統建構Lyapunov函數 E ( . ) \mathcal{E}(.) E(.)(一個正定函數),然後對這個函數求導,如果 E ˙ ( . ) ≤ 0 \dot\mathcal{E}(.)\leq 0 E˙(.)≤0,那麼我們可以說系統為Lyapunov穩定。這裡如果我們将 Lyapunov函數看作是系統的能量函數,對能量函數求導并且其導數一直為負,則說明系統的能量是遞減的,也就說明系統是穩定的。
我們考慮以下的一階ODE系統模型:
Y ˙ = F ( Y , t ) , Y ( t 0 ) = Y 0 \dot Y = F(Y,t), \ \ Y(t_0) = Y_0 Y˙=F(Y,t), Y(t0)=Y0
首先定義系統的平衡點為 Y ∗ Y^* Y∗, Y ∗ Y^* Y∗ 滿足 F ( Y ∗ , t ) = 0 F(Y^*,t)=0 F(Y∗,t)=0。我們分析系統的穩定性,即是針對系統的平衡點來分析,是以 Lyapunov函數也往往定義在包含 Y ∗ Y^* Y∗ 的一個開放集。下面的定理總結了如何應用 Lyapunov 函數來分析 Y ∗ Y^* Y∗ 的穩定性。
定理: 假設 Y ∗ Y^* Y∗ 為系統的平衡點,定義包含 Y ∗ Y^* Y∗ 的一個開放集 O \mathcal{O} O, 以及函數 E : O → R \mathcal{E}: \mathcal{O} \rightarrow R E:O→R,則我們有以下結論:
如果 E ( . ) \mathcal{E}(.) E(.) 滿足
那麼 Y ∗ Y^* Y∗ 穩定并且 E ( . ) \mathcal{E}(.) E(.) 為 Lyapunov 函數。如果進一步我們有 E ˙ ( Y ) < 0 ∀ Y ∈ O ∖ Y ∗ \dot\mathcal{E}(Y) < 0 \ \ \ \ \forall \ Y \in \mathcal{O}\setminus Y^* E˙(Y)<0 ∀ Y∈O∖Y∗ 那麼 Y ∗ Y^* Y∗ 為漸進穩定并且 E ( . ) \mathcal{E}(.) E(.) 為嚴格 Lyapunov 函數。
- E ( Y ∗ ) = 0 \mathcal{E}(Y^*)=0 E(Y∗)=0 \quad \quad \quad \quad \quad \quad \quad \ \ \ \ \quad \qquad ( L . 1 ) (L.1) (L.1)
- E ( Y ) > 0 ∀ Y ∈ O ∖ Y ∗ \mathcal{E}(Y)>0 \ \ \ \ \forall \ Y \in \mathcal{O}\setminus Y^* E(Y)>0 ∀ Y∈O∖Y∗ \quad \quad \ \ \ \qquad ( L . 2 ) (L.2) (L.2)
- E ˙ ( Y ) ≤ 0 ∀ Y ∈ O ∖ Y ∗ \dot\mathcal{E}(Y)\leq 0 \ \ \ \ \forall \ Y \in \mathcal{O}\setminus Y^* E˙(Y)≤0 ∀ Y∈O∖Y∗ \quad \quad \ \ \ \qquad ( L . 3 ) (L.3) (L.3)
ADMM算法的ODE模型
我們将通過上式 ( 1 ) (1) (1) 推導出ADMM的ODE模型,基于我們對函數 f f f 和 g g g 的假設 (i.e. f f f 和 g g g 為凸函數),我們可以得出優化問題 (1a) 和 (1b) 為強凸問題 (strongly convex)。是以每一步的疊代 ( x k + 1 x_{k+1} xk+1, z k + 1 z_{k+1} zk+1, u k + 1 u_{k+1} uk+1) 都是唯一的。通過 (1a) 和 (1b) 的最優條件 (即目标函數求導等于0),我們可以得到 ( x k + 1 x_{k+1} xk+1, z k + 1 z_{k+1} zk+1, u k + 1 u_{k+1} uk+1) 滿足下面的代數方程:
∇ f ( x k + 1 ) + ρ A T ( A x k + 1 − z k + u k ) = 0 , ( 2 a ) ∇ g ( x k + 1 ) − ρ ( A x k + 1 − z k + 1 + u k ) = 0 , ( 2 b ) u k + 1 − u k − A x k + 1 + z k + 1 = 0 , ( 2 c ) \nabla f(x_{k+1}) + \rho A^T(Ax_{k+1} - z_k + u_k)= 0, \ \ \ (2a)\\ \nabla g(x_{k+1}) - \rho (Ax_{k+1} - z_{k+1} + u_k)= 0, \ \ \ (2b)\\ u_{k+1} - u_k - Ax_{k+1} + z_{k+1}=0,\ \ \ (2c) ∇f(xk+1)+ρAT(Axk+1−zk+uk)=0, (2a)∇g(xk+1)−ρ(Axk+1−zk+1+uk)=0, (2b)uk+1−uk−Axk+1+zk+1=0, (2c)
将 (2b) 左乘 A T A^T AT, 并與 (2a) 相加,可以得到:
∇ f ( x k + 1 ) + A T ∇ g ( x k + 1 ) + ρ A T ( z k + 1 − z k ) = 0 , ( 3 ) \nabla f(x_{k+1}) + A^T\nabla g(x_{k+1}) + \rho A^T(z_{k+1} - z_k ) = 0, \ \ (3) ∇f(xk+1)+AT∇g(xk+1)+ρAT(zk+1−zk)=0, (3)
假設 t = δ k t=\delta k t=δk 并且 x k = X ( t ) x_k = X(t) xk=X(t), z k = Z ( t ) z_k = Z(t) zk=Z(t), u k = U ( t ) u_k = U(t) uk=U(t)。
下面我們研究向量 z k + 1 z_{k+1} zk+1 的第 i i i 項:由于 z k , i = Z i ( t ) z_{k,i} = Z_i(t) zk,i=Zi(t), 且 t = δ k t=\delta k t=δk, 我們有: z k + 1 , i = Z i ( t + δ ) = Z i ( t ) + δ Z ˙ i ( t + λ i δ ) z_{k+1,i} = Z_i(t+\delta)=Z_i(t)+\delta \dot Z_i(t+\lambda_i\delta) zk+1,i=Zi(t+δ)=Zi(t)+δZ˙i(t+λiδ),其中 λ i ∈ [ 0 , 1 ] \lambda_i \in [0,1] λi∈[0,1]。這裡我們應用中值定理得到 Z ˙ i ( t + λ i δ ) \dot Z_i(t+\lambda_i\delta) Z˙i(t+λiδ) 的形式。是以,當 δ \delta δ 無限趨近于0時,我們有:
lim δ → 0 z k + 1 , i − z k , i δ = lim δ → 0 Z ˙ i ( t + λ i δ ) = Z ˙ i ( t ) \lim_{\delta\to 0} \frac{z_{k+1,i}-z_{k,i}}{\delta} = \lim_{\delta\to 0}\dot Z_i(t+\lambda_i\delta) = \dot Z_i(t) δ→0limδzk+1,i−zk,i=δ→0limZ˙i(t+λiδ)=Z˙i(t)
z k + 1 z_{k+1} zk+1 向量中的每一項都滿足上式,是以 (3) 式中的第三項 ρ A T ( z k + 1 − z k ) \rho A^T(z_{k+1} - z_k ) ρAT(zk+1−zk) 可以直接表示成 A T Z ˙ ( t ) A^T\dot Z(t) ATZ˙(t),如果我們取 ρ = 1 / δ \rho = 1/ \delta ρ=1/δ。對于 (3) 式中的前兩項,我們有:
lim δ → 0 ∇ f ( x k + 1 ) + A T ∇ g ( x k + 1 ) = lim δ → 0 ∇ f ( X ( t + δ ) ) + A T ∇ g ( Z ( t + δ ) ) = f ( X ( t ) ) + A T ∇ g ( Z ( t ) ) \lim_{\delta\to 0} \nabla f(x_{k+1}) + A^T\nabla g(x_{k+1}) = \lim_{\delta\to 0} \nabla f(X(t+\delta)) + A^T\nabla g(Z(t+\delta)) = f(X(t)) + A^T\nabla g(Z(t)) δ→0lim∇f(xk+1)+AT∇g(xk+1)=δ→0lim∇f(X(t+δ))+AT∇g(Z(t+δ))=f(X(t))+AT∇g(Z(t))
是以,對 (3) 式求極限 ( δ → 0 \delta \rightarrow 0 δ→0),我們可以得到:
f ( X ( t ) ) + A T ∇ g ( Z ( t ) ) + A T Z ˙ ( t ) = 0 , ( 4 ) f(X(t)) + A^T\nabla g(Z(t)) + A^T\dot Z(t) = 0, \ \ \ (4) f(X(t))+AT∇g(Z(t))+ATZ˙(t)=0, (4)
下面我們考慮式 (2c) 的第 i i i 項:
0 = U i ( t + δ ) − U i ( t ) − ( A X ) i ( t + δ ) + Z i ( t + δ ) = δ U ˙ i ( t + λ i δ ) − ( A X ) i ( t + δ ) + Z i ( t + δ ) 0 = U_i (t+\delta) -U_i (t) -(AX)_i(t+\delta) + Z_i(t+\delta) \\ =\delta\dot U_i(t+\lambda_i\delta) -(AX)_i(t+\delta) + Z_i(t+\delta) 0=Ui(t+δ)−Ui(t)−(AX)i(t+δ)+Zi(t+δ)=δU˙i(t+λiδ)−(AX)i(t+δ)+Zi(t+δ)
對上式求極限 ( δ → 0 \delta \rightarrow 0 δ→0),我們可以得到:
0 = Z i ( t ) − ( A X ) i ( t ) 0 = Z_i(t)-(AX)_i(t) 0=Zi(t)−(AX)i(t)
上式對向量中的每一項都滿足,可得 Z ( t ) = A X ( t ) Z(t) = AX(t) Z(t)=AX(t) 并且 Z ˙ ( t ) = A X ˙ ( t ) \dot Z(t) = A \dot X(t) Z˙(t)=AX˙(t)。注意到我們有 V ( x , z ) = f ( x ) + g ( z ) V(x,z) = f(x) + g(z) V(x,z)=f(x)+g(z),我們有 ∇ f ( x ) + A T ∇ g ( A X ) = ∇ V ( X ) \nabla f(x) +A^T \nabla g(AX) = \nabla V(X) ∇f(x)+AT∇g(AX)=∇V(X)。
是以式 (4) 可以表示為:
∇ V ( X ) + A T A X ˙ ( t ) = 0 \nabla V(X) + A^TA\dot X(t) = 0 ∇V(X)+ATAX˙(t)=0
基于假設,矩陣 A A A 為列滿秩矩陣 ( A T A A^TA ATA 可逆),我們有:
X ˙ ( t ) + ( A T A ) − 1 ∇ V ( X ) = 0 ( 5 ) \dot X(t) + (A^TA)^{-1}\nabla V(X) = 0 \quad (5) X˙(t)+(ATA)−1∇V(X)=0(5)
基于Lypunov函數的算法穩定性與收斂分析
本節我們将讨論通過選擇合适的Lyapunov函數,我們可以證明ADMM算法的穩定性以及得到ADMM算法的收斂速度。
上節中我們得到了ADMM算法的ODE形式:
X ˙ ( t ) + ( A T A ) − 1 ∇ V ( X ) = 0 \dot X(t) + (A^TA)^{-1}\nabla V(X) = 0 X˙(t)+(ATA)−1∇V(X)=0
下面的定理給出了ADMM算法穩定性的結果:
定理: 假設 X ∗ X^* X∗ 為目标函數 V ( . ) V(.) V(.) 的一個獨立的局部最小點,(即存在集合 O ∈ R n \mathcal{O} \in R^n O∈Rn 使得 X ∗ ∈ O X^* \in \mathcal{O} X∗∈O, ∇ V ( X ) = 0 , ∀ X ∗ ∈ O ∖ X ∗ \nabla V(X) = 0, \forall X^* \in \mathcal{O}\setminus X^* ∇V(X)=0,∀X∗∈O∖X∗ ),我們有:
V ( X ) > V ( X ∗ ) ∀ X ∗ ∈ O ∖ X ∗ V(X) > V(X^*) \quad \forall X^* \in \mathcal{O}\setminus X^* V(X)>V(X∗)∀X∗∈O∖X∗
是以 X ∗ X^* X∗ 為ADMM算法ODE形式 (5) 的漸進穩定平衡點。
證明: 由于 X ∗ X^* X∗ 為 V ( . ) V(.) V(.) 的一個最小點,由最優條件,我們可以得到 ∇ V ( x ∗ ) = 0 \nabla V(x^*) = 0 ∇V(x∗)=0,即 X ∗ X^* X∗ 為式 (5) 的一個平衡點。下面我們定義 Lyapunov 函數來證明 X ∗ X^* X∗ 為漸進穩定。考慮下面的 Lyapunov 函數:
E ( X ) = V ( X ) − V ( X ∗ ) \mathcal{E}(X)=V(X) - V(X^*) E(X)=V(X)−V(X∗)
我們可以得到此函數滿足對 Lyapunov 函數條件 ( L . 1 ) (L.1) (L.1) 和 ( L . 2 ) (L.2) (L.2):
E ( X ∗ ) = V ( X ∗ ) − V ( X ∗ ) = 0 ( L . 1 ) \mathcal{E}(X^*)=V(X^*) - V(X^*)=0 \quad \text(L.1) E(X∗)=V(X∗)−V(X∗)=0(L.1)
E ( X ) > V ( X ∗ ) − V ( X ∗ ) = 0 ( L . 2 ) \mathcal{E}(X)>V(X^*) - V(X^*)=0\quad \text(L.2) E(X)>V(X∗)−V(X∗)=0(L.2)
對 E ( X ) \mathcal E (X) E(X) 求導,我們得到:
E ˙ ( X ) = ∇ V ( X ) T X ˙ = − ( A T A X ˙ ( t ) ) T X ˙ = − ( A T X ˙ ( t ) ) T A X ˙ = − ∥ A X ˙ ∥ 2 \dot \mathcal{E}(X)= \nabla V(X)^T \dot X= - (A^TA\dot X(t))^T \dot X= -(A^T\dot X(t))^T A \dot X= -\| A \dot X \|^2 E˙(X)=∇V(X)TX˙=−(ATAX˙(t))TX˙=−(ATX˙(t))TAX˙=−∥AX˙∥2
因為我們假設 X ∗ X^* X∗ 為目标函數 V ( . ) V(.) V(.) 的一個獨立的局部最小點,是以如果 X ∈ O ∖ X ∗ X \in \mathcal{O} \setminus X^* X∈O∖X∗,我們有 ∇ V ( x ) ≠ 0 \nabla V(x) \neq 0 ∇V(x)=0, 由式 (5) 以及對矩陣 A A A 滿秩的假設,我們可以得到 X ˙ ( t ) ≠ 0 \dot X(t) \neq 0 X˙(t)=0。 是以 E ( X ) \mathcal{E}(X) E(X) 也滿足 Lyapunov 函數的第三個條件 ( L . 3 ) (L.3) (L.3):
E ˙ ( X ) < 0 ( L . 3 ) \dot \mathcal{E}(X) < 0 \quad \text(L.3) E˙(X)<0(L.3)
進而我們證明了 X ∗ X^* X∗ 為ADMM算法ODE形式 (5) 的漸進穩定平衡點。
通過對動态系統 (5) 構造不同的 Lyapunov 函數,我們還可以研究 ADMM 算法的收斂速度,即目标函數需要多久可以收斂到最優值。比如,如果我們考慮下面的 Lyapunov 函數:
E ( X , t ) = t [ V ( X ) − V ( X ∗ ) ] + 1 2 ∥ A ( X − X ∗ ) ∥ 2 \mathcal{E}(X,t)=t[V(X) - V(X^*)] + \frac{1}{2} \| A(X-X^*) \|^2 E(X,t)=t[V(X)−V(X∗)]+21∥A(X−X∗)∥2
很容易我們可以得到此函數滿足對 Lyapunov 函數條件 ( L . 1 ) (L.1) (L.1) 和 ( L . 2 ) (L.2) (L.2):
E ( X ∗ , t ) = t [ V ( X ∗ ) − V ( X ∗ ) ] + 1 2 ∥ A ( X ∗ − X ∗ ) ∥ 2 = 0 ( L . 1 ) \mathcal{E}(X^*,t)=t[V(X^*) - V(X^*)] + \frac{1}{2} \| A(X^*-X^*) \|^2=0 \quad \text(L.1) E(X∗,t)=t[V(X∗)−V(X∗)]+21∥A(X∗−X∗)∥2=0(L.1)
E ( X , t ) > t [ V ( X ∗ ) − V ( X ∗ ) ] + 1 2 ∥ A ( X ∗ − X ∗ ) ∥ 2 = 0 ( L . 2 ) \mathcal{E}(X,t)>t[V(X^*) - V(X^*)] + \frac{1}{2} \| A(X^*-X^*) \|^2=0\quad \text(L.2) E(X,t)>t[V(X∗)−V(X∗)]+21∥A(X∗−X∗)∥2=0(L.2)
對 E ( X , t ) \mathcal E (X,t) E(X,t) 求導,我們得到:
E ˙ ( X , t ) = t ∇ V ( X ) T X ˙ + V ( X ) − V ( X ∗ ) + ( X − X ∗ ) T ( A T A X ˙ ) = − t ∥ A X ˙ ∥ 2 + V ( X ) − V ( X ∗ ) + ( X − X ∗ ) T ∇ V ( X ) \dot \mathcal{E}(X,t)=t\nabla V(X)^T \dot X+V(X)-V(X^*)+(X-X^*)^T(A^TA\dot X) \\ \ \ \ \ = -t\| A\dot X\|^2+V(X)-V(X^*)+(X-X^*)^T\nabla V(X) E˙(X,t)=t∇V(X)TX˙+V(X)−V(X∗)+(X−X∗)T(ATAX˙) =−t∥AX˙∥2+V(X)−V(X∗)+(X−X∗)T∇V(X)
上式中,我們有: − t ∥ A X ˙ ∥ 2 ≤ 0 -t\| A\dot X\|^2 \leq 0 −t∥AX˙∥2≤0,由于 V ( X ) V(X) V(X) 是凸函數,根據凸函數的定義,我們有: V ( X ) − V ( X ∗ ) + ( X − X ∗ ) T ∇ V ( X ) ≥ 0 V(X)-V(X^*)+(X-X^*)^T\nabla V(X) \geq 0 V(X)−V(X∗)+(X−X∗)T∇V(X)≥0。是以我們有:
E ˙ ( X , t ) ≤ 0 \dot \mathcal{E}(X,t) \leq 0 E˙(X,t)≤0
是以 ∀ t ≥ t 0 \forall \ t \geq t_0 ∀ t≥t0,我們有 E ( X , t ) ≤ E ( X 0 , t 0 ) \mathcal{E}(X,t) \leq \mathcal{E}(X_0,t_0) E(X,t)≤E(X0,t0),根據 $\mathcal{E}(X,t) $ 的定義,可以得到:
V ( X ) − V ( X ∗ ) = 1 t E ( X , t ) − 1 2 t ∥ A ( X − X ∗ ) ∥ 2 ≤ 1 t E ( X , t ) ≤ 1 t E ( X 0 , t 0 ) V(X) - V(X^*) = \frac{1}{t} \mathcal{E}(X,t) - \frac{1}{2t} \| A(X-X^*) \|^2 \leq \frac{1}{t} \mathcal{E}(X,t) \leq \frac{1}{t} \mathcal{E}(X_0,t_0) V(X)−V(X∗)=t1E(X,t)−2t1∥A(X−X∗)∥2≤t1E(X,t)≤t1E(X0,t0)
是以,當我們假設目标函數為凸函數時,通過對 ADMM 算法的ODE形式構造合适的 Lyapunov 函數得到目标函數的收斂速度為 O ( 1 / t ) O(1/t) O(1/t),這與 ADMM 算法的收斂速度 O ( 1 / k ) O(1/k) O(1/k) 一緻。
在 França, Robinson 和 Vidal 2018年的 ADMM 文章中,還對加速 ADMM (Accelerated ADMM) 進行了ODE模組化,并通過構造 Lyapunov 函數了分析了該算法的穩定性和收斂速度。感興趣的同學可以看看原始論文。
通過結合控制理論中已經發展很成熟理論 (Lyapunov 函數) 來研究優化算法的收斂性質最近收到越來越多人的關注,一方面是因為成熟的控制理論一定程度上簡化了傳統繁瑣的證明過程。另一方面,通過對系統的深入分析,我們可以得到一系列優化算法的變種。由理論指導實踐,我相信這将會是以後的一個重要的研究方向。
[1]: França, G., Robinson, D.P. and Vidal, R., 2018. ADMM and accelerated ADMM as continuous dynamical systems. arXiv preprint arXiv:1805.06579.