交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）是一种解决可分解凸优化问题的简单方法，尤其在解决大规模问题上卓有成效，利用ADMM算法可以将原问题的目标函数等价的分解成若干个可求解的子问题，然后并行求解每一个子问题，最后协调子问题的解得到原问题的全局解。ADMM 最早分别由 Glowinski & Marrocco 及 Gabay & Mercier 于 1975 年和 1976 年提出，并被 Boyd 等人于 2011 年重新综述并证明其适用于大规模分布式优化问题。由于 ADMM 的提出早于大规模分布式计算系统和大规模优化问题的出现，所以在 2011 年以前，这种方法并不广为人知。
对偶上升方法考虑等式约束的最优化问题如下 min x f ( x ) min_x f(x) xminf(x) s t . A x = b st. Ax=b st.Ax=b其中 x ∈ R n , A ∈ R m × n , f : R n ∈ R xinmathbb R^n,Ainmathbb R^{m imes n},f:mathbb R^n inmathbb R x∈Rn,A∈Rm×n,f:Rn∈R是凸函数 原问题的拉格朗日函数为： L ( x , y ) = f ( x ) + y T ( A x − b ) L(x,y) = f(x) + y^T(Ax-b) L(x,y)=f(x)+yT(Ax−b)那么其对偶函数为: g ( y ) = i n f x L ( x , y ) = − f ∗ ( − A T y ) − b T y g(y)=inf_xL(x,y)=-f^*(-A^Ty)-b^Ty g(y)=infxL(x,y)=−f∗(−ATy)−bTy其中 y y y是拉格朗日乘子，也是对偶变量， f ∗ f^* f∗是 f f f共轭函数。 假设满足强对偶性，则原问题和对偶问题的最优值相等。我们设原问题最优解为 x ∗ x^* x∗,对偶问题最优解为 y ∗ y^* y∗，则 x ∗ = a r g m i n x L ( x , y ∗ ) x^*=argmin_xL(x,y^*) x∗=argminxL(x,y∗)在对偶上升方法中，对偶问题是通过梯度上升方法来解，因此对偶上升迭代更新为: x k + 1 = a r g m i n x L ( x , y k ) x_{k+1}=argmin_xL(x,y^k) xk+1=argminxL(x,yk) y k + 1 = y k + α k ( A x k + 1 − b ) y^{k+1}=y^k+alpha_k(Ax^k+1-b) yk+1=yk+αk(Axk+1−b)其中 α k > 0 alpha_k>0 αk>0,是梯度上升的步长。
对偶分解性对偶上升方法中在满足强对偶性条件下，通过梯度上升来逐步调整对偶变量，再通过对偶变量来求解原问题最优解，这样的好处是在有些情况下可以使算法可分解，假设目标函数是可分解的，即， f ( x ) = ∑ i = 1 N f i ( x i ) f(x)=sum_{i=1}^Nf_i(x_i) f(x)=i=1∑Nfi(xi)其中 x = ( x 1 , x 2 , … , x N ) , x i ∈ R n i x=(x_1,x_2,dots,x_N),x_iinmathbb R^{n_i} x=(x1,x2,…,xN),xi∈Rni,划分矩阵A A = [ A 1 , A 2 , ⋯ , A N ] A=[A_1,A_2,cdots,A_N] A=[A1,A2,⋯,AN]所以 A x = ∑ i = 1 N A i x i Ax=sum_{i=1}^NA_ix_i Ax=∑i=1NAixi,则拉格函数重写成 L ( x , y ) = ∑ i = 1 N L i ( x i , y ) = ∑ i = 1 N ( f i ( x i ) + y T A i x i − ( 1 N ) y T b ) L(x,y)=sum_{i=1}^NL_i(x_i,y)=sum_{i=1}^N(f_i(x_i)+y^TA_ix_i-(frac{1}{ N})y^Tb) L(x,y)=i=1∑NLi(xi,y)=i=1∑N(fi(xi)+yTAixi−(N1)yTb)对偶上升的迭代更新: x i k + 1 = a r g m i n x i L i ( x i , y k ) x_i^{k+1}=argmin_{x_i}L_i(x_i,y^k) xik+1=argminxiLi(xi,yk) y k + 1 = y k + α k ( A x k + 1 − b ) y^{k+1}=y^k+alpha^k(Ax^{k+1}-b) yk+1=yk+αk(Axk+1−b)
增广拉格朗日（乘子法）为了增加对偶上升方法的鲁棒性和放松目标强凸的要求，引入了增广拉格朗日，增广拉格朗日，形式如下: L ρ ( x , y ) = f ( x