每日时讯!ADMM——交替方向乘子法

2023-04-10 23:04:33 来源：博客园

ADMM（Alternating Direction Method of Multipliers，交替方向乘子法）是一种优化算法，主要用于解决分布式、大规模和非光滑的凸优化问题。ADMM通过将原始问题分解为多个易于处理的子问题来实现优化。它结合了两种经典优化方法：梯度下降法（gradient descent）和拉格朗日乘子法（Lagrangian multiplier method）。

(相关资料图)

ADMM

算法

ADMM考虑如下形式的凸优化问题：

$\min\limits_{x,z} f(x) + g(z)$$ s.t.\,\, Ax + Bz = c $

其中$x$和$z$是优化变量，$f(x)$和$g(z)$是凸函数，$A,B,c$是已知的系数矩阵与向量。为了解决这个问题，首先引入拉格朗日乘子$y\in R$，构造增广拉格朗日函数$L(x, z, y)$：

$\displaystyle L(x, z, y) = f(x) + g(z) + y^T(Ax + Bz - c) + \frac{\rho}{2} ||Ax + Bz - c||^2$

其中$\rho > 0$是一个超参数，定义算法迭代步伐。相较于普通拉格朗日函数，增广拉格朗日函数多了二范数约束，能更好地处理约束条件并加速算法的收敛。

ADMM算法通过以下迭代步骤进行优化直到收敛：

1、更新$x$：$x^{k+1} = \text{arg}\min\limits_x L(x, z^k, y^k)$　　2、更新$z$：$z^{k+1} = \text{arg}\min\limits_z L(x^{k+1}, z, y^k)$　　3、更新$y$：$y^{k+1} = y^k + \rho(Ax^{k+1} + Bz^{k+1} - c)$

收敛条件如：$\|x^{k+1}-x^{k}\|$与$\|z^{k+1}-z^{k}\|$小于一定阈值。

为什么可以优化到最小值

ADMM的收敛性可以从两个方面来理解：

可分离性：在ADMM的迭代过程中，$x$和$z$的优化问题是分开进行的。这意味着我们可以独立地解决$f(x)$和$g(z)$的优化问题。在每一步迭代中，我们都在尝试最小化原始问题的目标函数。

拉格朗日乘子法的收敛性：拉格朗日乘子法的目标是找到满足原始问题约束条件的最优解。在ADMM的迭代过程中，通过调整拉格朗日乘子$y$来强化原始问题的约束条件，从而保证算法在全局范围内收敛到满足约束条件的可行解。

综上所述，ADMM算法可以在全局范围内收敛到原始优化问题的最小值，因为它能够在每次迭代中分别优化目标函数，并逐渐强化约束条件。

直观理解：如果满足约束条件，迭代的前两步总是会使$f(x)$与$g(z)$变小，而第3步只是更新$y$，因此总体的迭代过程是单向让原始优化问题$f(x)+g(z)$变小的。而一旦约束不满足，第3步对$y$的更新就是约束对的前两步更新的反抗。如果前两步更新使约束不满足，那么在第3步$y$就会更新，使约束在下一次迭代的前两步产生相应的梯度。

参考：https://blog.csdn.net/weixin_44655342/article/details/121899501

关键词：