视频字幕
ADMM算法，即交替方向乘子法，是求解约束凸优化问题的重要算法。它专门处理形如最小化f(x)加g(z)，约束条件为Ax加Bz等于c的问题。ADMM通过将复杂的约束优化问题分解为更简单的子问题，交替求解，在机器学习、信号处理、图像处理和统计学习等领域有广泛应用。
拉格朗日对偶理论是ADMM算法的重要理论基础。拉格朗日函数L等于目标函数f(x)加g(z)，再加上对偶变量y与约束违反量的内积。对偶变量y具有重要的几何意义，它表示约束的拉格朗日乘子，反映了梯度方向的权重。KKT条件要求拉格朗日函数对原变量的梯度为零。在凸优化中，强对偶性保证了原问题与对偶问题的等价性，这为后续的增广拉格朗日方法奠定了基础。
增广拉格朗日方法是ADMM算法的数学基础。它在原拉格朗日函数基础上添加了惩罚项，形成增广拉格朗日函数。惩罚项的形式是ρ除以2乘以约束违反量的二范数平方。这个增广项具有重要作用：它能改善算法的收敛性质，避免对偶变量更新时的数值不稳定问题，并增强算法的鲁棒性。惩罚参数ρ控制着对约束违反的惩罚强度，ρ值越大，对约束违反的惩罚越严厉。
ADMM算法的核心是三个迭代步骤的交替执行。第一步是x最小化，固定z和y，求解x的最优值。第二步是z最小化，利用刚更新的x值，固定y，求解z的最优值。第三步是对偶更新，根据约束违反程度更新对偶变量y。这三个步骤循环执行，通过交替优化的方式逐步逼近最优解。每次迭代都会改善目标函数值和约束满足程度，直到收敛。
ADMM算法全称为交替方向乘子法，是一种强大的凸优化算法。它特别适用于可以分解为两个子问题的优化问题，问题的一般形式是最小化f(x)加g(z)，约束条件为Ax加Bz等于c。ADMM算法在机器学习、图像处理、分布式优化等多个领域都有重要应用。
ADMM算法的核心是增广拉格朗日函数。与标准拉格朗日函数不同，增广拉格朗日函数包含三个部分：原目标函数f(x)加g(z)，拉格朗日乘子项λ转置乘以约束Ax加Bz减c，以及一个二次惩罚项。惩罚参数ρ大于0确保约束违反时有额外惩罚，这不仅改善了算法的收敛性质，还平衡了目标函数优化和约束满足之间的关系。
ADMM算法包含三个交替更新步骤。第一步，固定z和λ，对x进行优化；第二步，固定刚更新的x和λ，对z进行优化；第三步，使用新的x和z值更新拉格朗日乘子λ。这三个步骤不断循环，直到算法收敛。每一步的优化通常都有闭式解或者可以通过简单的数值方法求解，这是ADMM算法高效的重要原因。
让我们通过LASSO回归来看一个具体例子。LASSO回归的目标是最小化平方误差加上L1正则化项。我们可以将其重写为ADMM形式：引入辅助变量z，约束条件为x等于z。这样，第一个子问题变成带二次正则化的最小二乘问题，有闭式解；第二个子问题是软阈值操作；第三个子问题是简单的乘子更新。通过这种分解，每个子问题都很容易求解，算法快速收敛到最优解。
ADMM算法的收敛性分析是理论研究的重要内容。算法收敛的充分条件包括目标函数f和g的凸性，以及适当的正则性条件。在这些条件下，ADMM算法具有O(1/k)的收敛率。惩罚参数ρ的选择对收敛速度有重要影响：ρ过小会导致收敛缓慢，ρ过大可能引起数值不稳定。实际应用中，我们通过监控原始残差和对偶残差来判断算法的收敛情况，当这两个残差都降到预设阈值以下时，算法达到收敛。