ADMM(交替方向乘子法详解与实现)

server/2025/3/15 18:57:26/

ADMM(Alternating Direction Method of Multipliers,交替方向乘子法)是一种强大的优化算法,广泛用于解决约束优化问题,尤其是在机器学习、大规模数据分析和信号处理领域。以下是对ADMM迭代算法的详细解析,包括其基本思想、数学推导、算法步骤以及应用场景。


1. ADMM的基本思想

ADMM是一种结合了对偶上升法乘子法的优化算法,特别适合解决带有约束的优化问题。其核心思想是通过分解问题,将复杂的优化问题拆解为多个子问题,并交替更新变量以逐步逼近最优解。

ADMM适用于以下形式的优化问题:

min ⁡ x , z f ( x ) + g ( z ) \min_{x, z} \, f(x) + g(z) x,zminf(x)+g(z)

subject to A x + B z = c \text{subject to} \, Ax + Bz = c subject toAx+Bz=c

其中:

  • x ∈ R n x \in \mathbb{R}^n xRn z ∈ R m z \in \mathbb{R}^m zRm 是优化变量;
  • f ( x ) f(x) f(x) g ( z ) g(z) g(z) 是目标函数,通常是凸函数;
  • A ∈ R p × n A \in \mathbb{R}^{p \times n} ARp×n, B ∈ R p × m B \in \mathbb{R}^{p \times m} BRp×m, c ∈ R p c \in \mathbb{R}^p cRp 是线性约束的矩阵和向量。

ADMM的目标是将问题分解为更易于求解的子问题,并通过引入拉格朗日乘子(Lagrange Multiplier)来处理约束。


2. ADMM的数学推导

为了推导ADMM,我们从问题的增广拉格朗日函数(Augmented Lagrangian)开始。增广拉格朗日函数引入了二次惩罚项,以提高算法的稳定性和收敛性。

2.1 增广拉格朗日函数

对于上述优化问题,增广拉格朗日函数定义为:

L ρ ( x , z , λ ) = f ( x ) + g ( z ) + λ T ( A x + B z − c ) + ρ 2 ∥ A x + B z − c ∥ 2 2 L_\rho(x, z, \lambda) = f(x) + g(z) + \lambda^T (Ax + Bz - c) + \frac{\rho}{2} \|Ax + Bz - c\|_2^2 Lρ(x,z,λ)=f(x)+g(z)+λT(Ax+Bzc)+2ρAx+Bzc22

其中:

  • λ ∈ R p \lambda \in \mathbb{R}^p λRp 是拉格朗日乘子(对偶变量);
  • ρ > 0 \rho > 0 ρ>0 是惩罚参数(也称为步长),用于控制约束违反的惩罚力度;
  • ρ 2 ∥ A x + B z − c ∥ 2 2 \frac{\rho}{2} \|Ax + Bz - c\|_2^2 2ρAx+Bzc22 是二次惩罚项,增强了对约束的满足。
2.2 ADMM的迭代更新

ADMM通过交替更新 x x x z z z λ \lambda λ 来最小化增广拉格朗日函数。每次迭代分为以下三个步骤:

  1. 更新 x x x(x-子问题)

x k + 1 = arg ⁡ min ⁡ x L ρ ( x , z k , λ k ) x^{k+1} = \arg\min_x L_\rho(x, z^k, \lambda^k) xk+1=argxminLρ(x,zk,λk)

即固定 z k z^k zk λ k \lambda^k λk,对 x x x 优化。

  1. 更新 z z z(z-子问题)

z k + 1 = arg ⁡ min ⁡ z L ρ ( x k + 1 , z , λ k ) z^{k+1} = \arg\min_z L_\rho(x^{k+1}, z, \lambda^k) zk+1=argzminLρ(xk+1,z,λk)

即固定 x k + 1 x^{k+1} xk+1 λ k \lambda^k λk,对 z z z 优化。

  1. 更新 λ \lambda λ(对偶变量更新)

λ k + 1 = λ k + ρ ( A x k + 1 + B z k + 1 − c ) \lambda^{k+1} = \lambda^k + \rho (Ax^{k+1} + Bz^{k+1} - c) λk+1=λk+ρ(Axk+1+Bzk+1c)

即根据约束的违反情况更新拉格朗日乘子。

这里的 k k k 表示迭代次数。

2.3 为什么交替更新?

ADMM的核心在于“交替”更新 x x x z z z,而不是同时更新。这是因为同时更新 x x x z z z 通常会导致难以求解的联合优化问题。通过分解,ADMM将问题拆解为两个独立的子问题,每个子问题通常更容易求解(例如,可能有闭式解或可以通过高效的迭代方法求解)。


3. ADMM的算法步骤

基于上述推导,ADMM的完整算法可以总结为以下步骤:

输入
  • 目标函数 f ( x ) f(x) f(x) g ( z ) g(z) g(z)
  • 约束参数 A A A B B B c c c
  • 惩罚参数 ρ > 0 \rho > 0 ρ>0
  • 初始值 x 0 x^0 x0 z 0 z^0 z0 λ 0 \lambda^0 λ0
  • 收敛容差 ϵ \epsilon ϵ
算法
  1. 初始化:设置 k = 0 k = 0 k=0,初始化 x 0 x^0 x0 z 0 z^0 z0 λ 0 \lambda^0 λ0
  2. 迭代:重复以下步骤直到收敛:
    • 步骤 1:更新 x x x

x k + 1 = arg ⁡ min ⁡ x ( f ( x ) + λ k T ( A x + B z k − c ) + ρ 2 ∥ A x + B z k − c ∥ 2 2 ) x^{k+1} = \arg\min_x \left( f(x) + \lambda^{kT} (Ax + Bz^k - c) + \frac{\rho}{2} \|Ax + Bz^k - c\|_2^2 \right) xk+1=argxmin(f(x)+λkT(Ax+Bzkc)+2ρAx+Bzkc22)

  • 步骤 2:更新 z z z

z k + 1 = arg ⁡ min ⁡ z ( g ( z ) + λ k T ( A x k + 1 + B z − c ) + ρ 2 ∥ A x k + 1 + B z − c ∥ 2 2 ) z^{k+1} = \arg\min_z \left( g(z) + \lambda^{kT} (Ax^{k+1} + Bz - c) + \frac{\rho}{2} \|Ax^{k+1} + Bz - c\|_2^2 \right) zk+1=argzmin(g(z)+λkT(Axk+1+Bzc)+2ρAxk+1+Bzc22)

  • 步骤 3:更新 λ \lambda λ

λ k + 1 = λ k + ρ ( A x k + 1 + B z k + 1 − c ) \lambda^{k+1} = \lambda^k + \rho (Ax^{k+1} + Bz^{k+1} - c) λk+1=λk+ρ(Axk+1+Bzk+1c)

  • 步骤 4:检查收敛条件(见下文)。
  1. 输出:返回最优解 x ∗ x^* x z ∗ z^* z 和对偶变量 λ ∗ \lambda^* λ
收敛条件

ADMM通常通过检查原残差(Primal Residual)和对偶残差(Dual Residual)来判断是否收敛:

  • 原残差: r k = A x k + B z k − c r^k = Ax^k + Bz^k - c rk=Axk+Bzkc,表示约束的违反程度;
  • 对偶残差: d k = ρ A T B ( z k − z k − 1 ) d^k = \rho A^T B (z^k - z^{k-1}) dk=ρATB(zkzk1),表示对偶变量的变化。

当以下条件满足时,算法停止:

∥ r k ∥ 2 ≤ ϵ 和 ∥ d k ∥ 2 ≤ ϵ \|r^k\|_2 \leq \epsilon \quad \text{和} \quad \|d^k\|_2 \leq \epsilon rk2ϵdk2ϵ


4. ADMM的优点与特性

4.1 优点
  1. 分解性:ADMM将复杂问题分解为多个子问题,适合并行计算和分布式优化。
  2. 鲁棒性:通过引入二次惩罚项,ADMM对初始值和参数的选择不太敏感。
  3. 适用性广:适用于凸问题,尤其在 f ( x ) f(x) f(x) g ( z ) g(z) g(z) 是凸函数时,ADMM保证收敛到全局最优解。
4.2 特性
  • 收敛性:当 f ( x ) f(x) f(x) g ( z ) g(z) g(z) 是凸函数,且约束矩阵 A A A B B B 满足一定条件时,ADMM保证收敛。
  • 非凸问题:在非凸问题中,ADMM可能不保证收敛到全局最优解,但仍常用于求解局部最优解(例如深度学习中的某些优化问题)。

5. ADMM的应用场景

ADMM在许多领域都有广泛应用,以下是几个典型例子:

  1. Lasso回归(L1正则化线性回归):

    • 问题形式: min ⁡ x 1 2 ∥ A x − b ∥ 2 2 + λ ∥ x ∥ 1 \min_x \frac{1}{2} \|Ax - b\|_2^2 + \lambda \|x\|_1 minx21Axb22+λx1
    • ADMM通过引入辅助变量 z z z 将问题分解为 x x x-子问题(二次优化)和 z z z-子问题(软阈值运算)。
  2. 图像处理(如图像去噪):

    • 问题形式: min ⁡ x ∥ x − y ∥ 2 2 + λ ∥ ∇ x ∥ 1 \min_x \|x - y\|_2^2 + \lambda \|\nabla x\|_1 minxxy22+λ∥∇x1
    • ADMM分解为去噪子问题和正则化子问题。
  3. 分布式优化

    • 在分布式机器学习中,ADMM用于分解大规模问题,例如在多节点上并行优化。
  4. 矩阵分解(如主成分分析或低秩矩阵补全):

    • 问题形式: min ⁡ X ∥ X − Y ∥ F 2 + λ rank ( X ) \min_X \|X - Y\|_F^2 + \lambda \text{rank}(X) minXXYF2+λrank(X)
    • ADMM通过引入辅助变量处理秩约束。

6. ADMM的实现细节与技巧

6.1 选择惩罚参数 ρ \rho ρ
  • ρ \rho ρ 的选择对收敛速度影响很大:
    • 如果 ρ \rho ρ 太小,可能导致收敛过慢;
    • 如果 ρ \rho ρ 太大,可能导致数值不稳定或收敛到次优解。
  • 实践中,可以使用自适应 ρ \rho ρ 策略,例如根据原残差和对偶残差的比值动态调整 ρ \rho ρ
6.2 子问题的求解
  • x x x-子问题和 z z z-子问题可能是解析解(如软阈值运算)或需要数值优化(如梯度下降法)。
  • 如果子问题没有闭式解,可以使用迭代方法(如共轭梯度法)求解。
6.3 并行与分布式实现
  • ADMM的分解特性使其非常适合并行计算。例如,在分布式系统中,可以将 x x x-子问题和 z z z-子问题分配到不同的计算节点。

7. ADMM的伪代码

以下是ADMM的伪代码,用于帮助理解和实现:

输入:f(x), g(z), A, B, c, ρ, x⁰, z⁰, λ⁰, ε
输出:x*, z*, λ*初始化:k = 0
while 未收敛 do# 步骤 1:更新 xx^(k+1) = argmin_x L_ρ(x, z^k, λ^k)# 步骤 2:更新 zz^(k+1) = argmin_z L_ρ(x^(k+1), z, λ^k)# 步骤 3:更新 λλ^(k+1) = λ^k + ρ (A x^(k+1) + B z^(k+1) - c)# 步骤 4:检查收敛r^k = A x^(k+1) + B z^(k+1) - c  # 原残差d^k = ρ A^T B (z^(k+1) - z^k)    # 对偶残差if ||r^k||_2 ≤ ε 且 ||d^k||_2 ≤ ε then收敛,退出循环end ifk = k + 1
end while返回:x^(k+1), z^(k+1), λ^(k+1)

python_201">8.python代码实现

python">import numpy as np
from sklearn.utils.validation import check_arraydef soft_thresholding_numpy(x, threshold):"""软阈值函数(NumPy 版本)"""return np.sign(x) * np.maximum(np.abs(x) - threshold, 0.0)def admm_lasso_sklearn(X, y, lambda_reg, rho=1.0, max_iter=1000, tol=1e-4):"""使用 ADMM 解决 Lasso 回归问题(基于 NumPy 和 scikit-learn)参数:X: 输入矩阵 (m, n)y: 观测向量 (m,)lambda_reg: L1 正则化参数rho: 惩罚参数max_iter: 最大迭代次数tol: 收敛容差返回:x: 优化后的解"""X = check_array(X)  # 确保输入格式正确y = check_array(y, ensure_2d=False)m, n = X.shapex = np.zeros(n)  # 初始化 xz = np.zeros(n)  # 初始化 zu = np.zeros(n)  # 初始化对偶变量 u# 预计算矩阵X_t_X = X.T @ XX_t_y = X.T @ yI = np.eye(n)Q = X_t_X + rho * I  # x-子问题的矩阵Q_inv = np.linalg.inv(Q)  # 预计算矩阵的逆for k in range(max_iter):# 步骤 1: 更新 x (x-子问题)x_new = Q_inv @ (X_t_y + rho * (z - u))# 步骤 2: 更新 z (z-子问题)z_new = soft_thresholding_numpy(x_new + u, lambda_reg / rho)# 步骤 3: 更新 u (对偶变量)u_new = u + x_new - z_new# 计算残差r_primal = np.linalg.norm(x_new - z_new)  # 原残差r_dual = rho * np.linalg.norm(z_new - z)  # 对偶残差# 更新变量x, z, u = x_new, z_new, u_new# 检查收敛if r_primal < tol and r_dual < tol:print(f"Converged after {k+1} iterations")breakreturn x# 示例用法
if __name__ == "__main__":from sklearn.datasets import make_regression# 生成随机数据X, y = make_regression(n_samples=50, n_features=100, n_informative=10, noise=0.1, random_state=42)# 参数设置lambda_reg = 1.0  # 正则化参数rho = 1.0  # 惩罚参数# 运行 ADMMx_hat = admm_lasso_sklearn(X, y, lambda_reg, rho)print("Estimated x:", x_hat[:10])  # 打印部分解

9. 总结

ADMM是一种功能强大且灵活的优化算法,特别适合处理带有约束的凸优化问题。其核心在于通过交替更新变量和对偶变量,将复杂问题分解为更易于求解的子问题。ADMM在理论上保证收敛(在凸问题中),在实践中也表现出良好的鲁棒性和高效性。通过适当的参数调整和子问题求解策略,ADMM可以应用于广泛的实际问题,从机器学习到信号处理再到分布式优化。


http://www.ppmy.cn/server/175235.html

相关文章

工作记录 2017-01-12

序号 工作 相关人员 1 协助BPO进行Billing的工作。 处理Amazing Charts的数据查询。 修改BillingJobPoster&#xff0c;处理CCDA 的自动导入&#xff0c;预计还需一天才能完成。 修改录入Code的界面&#xff08;code 移动到指定位置&#xff09;&#xff0c;预计明天更新。…

《MySQL数据库从零搭建到高效管理|表的增删改查(基础)》

目录 引言&#xff1a; 一、表的操作 1.1 创建学生表 1.2 查看表结构 1.3 删除表 1.4 修改表名 1.5 添加字段 1.6 修改字段 1.7 删除字段 1.8 小结 二、CRUD 2.1 新增&#xff08;Create&#xff09;数据 2.2 查询&#xff08;Retrieve&#xff09;数据 2.3 修改&…

vue3 动态添加路由并生成左侧菜单栏

先说下思路&#xff0c;登录后跳转到基础页面&#xff0c; 每访问一个页面时&#xff0c;会进到路由守卫的方法 守卫进行身份验证&#xff0c;登录成功后才能跳转到静态路由外的页面&#xff0c;否则就重定向回login页面 登录后跳转到基础页面&#xff08;因为基础页面包含了左…

linux 命令 case

在 Linux Shell 脚本中&#xff0c;case 是一个强大的多条件分支控制命令&#xff0c;用于基于模式匹配执行不同代码块。它类似于其他编程语言中的 switch-case 语句&#xff0c;但更灵活&#xff0c;支持通配符和模式组合。以下是其核心用法和实 一、基础语法 case 变量 in …

基于相量测量单元(PMU)的电力系统故障分析MATLAB仿真

“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 模型简介&#xff1a; PMU是用于电力系统状态估计的Matlab函数&#xff0c;特别是使用相量测量单元(PMU)数据来估计系统的状态。它的主要功能是通过处理来自电网各个节点的测量数据来估计电网的电压大小和相角。此模…

基于Java 童装在线销售系统(源码+lw+部署文档+讲解),源码可白嫖!

摘要&#xff1a; 当今社会进入了科技进步、经济社会快速发展的新时代。国际信息和学术交流也不断加强&#xff0c;计算机技术对经济社会发展和人民生活改善的影响也日益突出&#xff0c;人类的生存和思考方式也产生了变化。传统购物管理采取了人工的管理方法&#xff0c;但这…

策略模式(Strategy Pattern)与状态模式(State Pattern)的异同

相同点 行为委托 两者均通过将行为委托给其他对象来实现功能解耦&#xff0c;遵循“组合优于继承”的原则。 策略模式&#xff1a;将算法逻辑委托给具体的策略类。 状态模式&#xff1a;将状态相关的行为委托给具体的状态类。 类结构相似 两者在类图结构上高度相似&#xff…

C#—【在不同的场景该用哪种线程?】

C#—【在不同的场景该用哪种线程&#xff1f;】 在C#中有很多种线程操作方法但都运用在不同的场景。 以下是针对不同场景选择 线程&#xff08;Thread&#xff09;、线程池&#xff08;ThreadPool&#xff09;、异步编程&#xff08;async/await&#xff09; 或 后台线程&…