·1212· 智能系统学报 第14卷 定义4（拉格朗日乘子法、增广拉格朗日乘子 LJ,Z,0,S,C1,C2,C3)= 法、交替方向乘子法) 1)假定要求解八X)的最优化问题，满足 IWL.+ioz+aDo01,+gS计 (12) (C1,I-Z-S)+(C2,J-Z)+(C3,2-Z)+ h(X)=0,其中fX):R"→R,h(X):R"→Rm。基于 拉格朗日乘子法1可以得到以下目标函数： 5山-Z+-z-se+0-z) Le(x,A)=f(X)+uh(X) 其中(J,Q)=(J严)。C1、C2和C,是拉格朗日乘 2)在计算等式约束问题时，使用增广拉格朗 子，μ>0是惩罚参数。下面介绍详细迭代步骤： 日乘子法(ALM),ALM增加了二次惩罚项，基于 更新Z固定其他变量并通过下述步骤更新Z ALM可以得到以下目标函数： L=mm2oZ张+C,I-Z-s)+ L.(x,2)=f)+h(+Ih(X 3)要求解X)+g(Z)的最优化问题，满足约束 (CJm-z+(C0-z)+5-z+ 条件AX+BZ=C。这类问题需要用到交替方向乘 -z-s+le-z) 子法(ADMM)II,ADMM是ALM的进一步推广， 这相当于 它将对偶上升法的可分解性与ALM的收敛性相 结合，基于ADMM方法可以得到以下目标函数： L-mni-z-s+ (13) Le(x,z.)=f(X)+g(Z)+(AX+BZ-C)+ lAx+Bz-CIP mzCo-z9 其中R=[Y,0w-m]⊙Z。通过推导8L/8Z=0,可 2低秩分块矩阵的核近似算法 以得到Z的最优解，式(13)的闭式解为 算法1低秩分块矩阵的核近似算法 Z1=【2+1+K-R+U,+U2+U)(14) 输入特征矩阵X;参数，2,3；距离测量 矩阵D: 其中u1-s+号&=+号=Q侣。 输出系数矩阵Z。 更新J当固定其他变量时，式(12)的目标 初始化：=0，Z=0,Q=0,S=0,1,2,>0, 函数可以表示为J的函数，即 C=0,C2=0,C3=-0, J"=argminlI+(C.J)+ whil max(I-Z+1-S+,l1-Z+‖ oZ)>tol +-红-汇 通过使用奇异值阈值算子（见定义3），可以得 do 1)通过式(14)更新系数矩阵Z: 到一个封闭形式的解决方案，即 2)通过式(15)更新辅助变量： r=rwz-9=swn (15) 3)通过式(17)更新辅助变量2： 4)通过式(18)更新辅助变量S: 式中：U2Vr是亿-S)的奇异值分解：S0是 L 5)更新拉格朗日乘子C,C2和C3: 软阈值算子可.定义为 x-A ,x> C1=C1+'(I-Z+1-S+) S(x)={x+A,x< C'=C3+d(J+1-Z) 0,-1<x<1 C1=C3+t(g1-Z+) 6)更新4 更新Q当固定其他变量时，式(12)的目标 =min(umax.pu) 函数可以表示为Q的函数，即 end 为了优化式(10)，首先引入两个辅助变量 =学De+k--[ (16) J和Q来使问题可分离，将式(10)重写为 可以通过逐元素的方法进行更新。显然，式 盟UL.+之Aoz+aDoQ,+gS (16)可以等效为解决n×N个子问题。对于第i行 (11) 第j列元素K,式(16)的最优解是 s.t.S=I-Z,J=Z,0=Z,Z>0 然后，可以通过ALM得到式(11)的增广拉格朗 argmin DM)=(M) 日函数 (17)定义 4 (拉格朗日乘子法、增广拉格朗日乘子 法、交替方向乘子法) h(X) = 0 f(X) : R n → R h(X) : R n → R m 1 ) 假定要求 解 f(X) 的最优化问题，满足 ，其中 ， 。基于 拉格朗日乘子法[13] 可以得到以下目标函数： Lc(x, λ) = f(X)+µh(X) 2) 在计算等式约束问题时，使用增广拉格朗 日乘子法 (ALM)，ALM 增加了二次惩罚项，基于 ALM 可以得到以下目标函数： Lc(x, λ) = f(X)+µh(X)+ c 2 ∥h(X)∥ 2 3) 要求解 f(X)+g(Z) 的最优化问题，满足约束 条件 AX+BZ=C。这类问题需要用到交替方向乘 子法 (ADMM)[13] ，ADMM 是 ALM 的进一步推广， 它将对偶上升法的可分解性与 ALM 的收敛性相 结合，基于 ADMM 方法可以得到以下目标函数： Lc(x,z, λ) = f(X)+g(Z)+λ T (AX+ BZ −C)+ c 2 ∥Ax+ Bz−C∥ 2 2 低秩分块矩阵的核近似算法 算法 1 低秩分块矩阵的核近似算法 输入 特征矩阵 X；参数 λ1， ， ；距离测量 λ2 λ3 矩阵 D； 输出 系数矩阵 Z。 初始化：J=0, Z=0, Q=0, S=0, λ1， ， λ2 λ3>0, C1=0, C2=0, C3=0, while max( I− Z t+1 −S t+1 ∞ , J t+1 − Z t+1 ∞ , Q t+1 − Z t+1 ∞ ) > tol do 1) 通过式 (14) 更新系数矩阵 Z； 2) 通过式 (15) 更新辅助变量 J； 3) 通过式 (17) 更新辅助变量 Q； 4) 通过式 (18) 更新辅助变量 S； 5) 更新拉格朗日乘子 C1，C2 和 C3；    C t+1 1 = C t 1 +µ t (I− Z t+1 −S t+1 ) C t+1 2 = C t 2 +µ t (J t+1 − Z t+1 ) C t+1 3 = C t 3 +µ t (Q t+1 − Z t+1 ) 6) 更新 µ µ t+1 = min(µmax,ρµt ) end 为了优化式 (10)，首先引入两个辅助变量 J 和 Q 来使问题可分离，将式 (10) 重写为 min J,Z,Q,S ∥J∥∗ + λ1 2 A˜ ⊙ Z 2 F +λ2∥D⊙Q∥1 +λ3g(S) s.t.S = I− Z, J = Z,Q = Z, Z ⩾ 0 (11) 然后，可以通过 ALM 得到式 (11) 的增广拉格朗 日函数 L(J, Z,Q,S,C1,C2,C3)= ∥J∥∗ + λ1 2 A˜ ⊙ Z 2 F +λ2∥D⊙Q∥1 +λ3g(S)+ ⟨C1,I− Z −S⟩+⟨C2, J − Z⟩+⟨C3,Q− Z⟩+ µ 2 (∥J − Z∥ 2 F +∥I− Z −S∥ 2 F +∥Q− Z∥ 2 F ) (12) ⟨J,Q⟩ = tr(J TQ) µ > 0 其中 。C1、C2 和 C3 是拉格朗日乘 子， 是惩罚参数。下面介绍详细迭代步骤： 更新 Z 固定其他变量并通过下述步骤更新 Z L = min Z λ1 2 A˜ ⊙ Z 2 F + ⟨ C t 1 ,I− Z −S t ⟩ + ⟨ C t 2 , J t+1 − Z ⟩ + ⟨ C t 3 ,Q t − Z ⟩ + µ t 2 ( J t+1 − Z 2 F + I− Z −S t 2 F + Q t − Z 2 F ) 这相当于 L = min Z λ1 2 ∥Z − R∥ 2 F + µ t 2 ( I− Z −S t + C t 1 µ t 2 F + J t+1 − Z + C t 2 µ t 2 F + Q t − Z + C t 3 µ t 2 F ) (13) R = [Y,0n(N−n)]⊙ Z t 其中 。通过推导 ∂L/ ∂Z = 0 ，可 以得到 Z 的最优解，式 (13) 的闭式解为 Z t+1 = [(2+ λ1 µ t )I+ K] (−1)( λ1 µ t R+U1 +U2 +U3) (14) U1 = I−S t + C t 1 µ t U2 = J t+1 + C t 2 µ t U3 = Q t + C t 3 µ 其中 t ， ， 。 更新 J 当固定其他变量时，式 (12) 的目标 函数可以表示为 J 的函数，即 J t+1 = argmin J ∥J∥∗ + ⟨ C t 2 , J − Z t ⟩ + µ t 2 J − Z t 2 F = ∥J∥∗ + µ t 2 J − ( Z t − C t 2 µ t ) 2 F 通过使用奇异值阈值算子 (见定义 3)，可以得 到一个封闭形式的解决方案，即 J t+1 = Γ1/µt(Z t − C t 2 µ t ) = US 1/µt(Σ)V T (15) UΣV T (Z t − C t 2 µ t ) S 1/µ 式中： 是 的奇异值分解； t(·) 是 软阈值算子[7] ，定义为 S λ(x) =    x−λ , x > λ x+λ , x < λ 0 , −λ < x < λ 更新 Q 当固定其他变量时，式 (12) 的目标 函数可以表示为 Q 的函数，即 L = min Q λ2∥D⊙Q∥1 + µ t 2 Q− ( Z t+1 − C t 3 µ t ) 2 F (16) n×N 可以通过逐元素的方法进行更新。显然， 式 (16) 可以等效为解决 个子问题。对于第 i 行 第 j 列元素 Kij，式 (16) 的最优解是 Q t+1 i j = argmin Qi j λ2 Di j   Qi j   + µ t 2 (Qi j − Mi j) 2 = S λ2 Di j µ t (Mi j) (17) ·1212· 智 能 系 统 学 报 第 14 卷