先说个实际场景。我之前在处理一个参数估计问题目标函数本身光滑可导但约束条件比较麻烦既有等式约束又有不等式约束。一开始图省事直接用了罚函数法罚因子调来调去约束残差始终压不到我想要的精度再加大罚因子数值又开始抖海森矩阵条件数直接爆炸。后来换成增广拉格朗日函数法配合简单的乘子更新问题很快就收敛到满足KKT条件的解。这个经历让我对这套方法印象极深。如果你也正在跟带约束的优化问题较劲或者看论文时总被“增广拉格朗日”“ADMM”这些词绕晕这篇文章可以把原理、推导、参数调节和实战经验一次讲清楚。增广拉格朗日函数法本质上是把经典拉格朗日乘子法和罚函数法融合在一起保留两者优点弥补各自短板。它既能像罚函数法那样把约束“吸”进目标函数又不像普通罚函数法那样必须让罚参数趋于无穷才能精确满足约束。工程上大火的ADMM就是增广拉格朗日函数法在可分离结构下的一种特殊实现。所以理解了增广拉格朗日后面看ADMM、分布式优化、压缩感知这些内容都会顺畅很多。下面我按自己的理解从经典方法的痛点开始讲起。1. 约束优化里传统方法为什么总是差口气1.1 罚函数法贪图简单但残差永远清不干净罚函数法的思路非常直观。面对一个带约束的优化问题min f(x)s.t. c(x) 0我直接把约束写成惩罚项塞进目标函数min f(x) (ρ/2)‖c(x)‖²这里的ρ是罚因子ρ越大迭代点偏离约束边界时受到的“惩罚”越重最后的解就越接近可行域。这个方法实现起来几乎没有门槛一个循环加一个无约束优化求解器就能跑起来。但它有一个绕不开的毛病想让我严格满足约束就必须把ρ推向无穷大。问题是ρ一旦变得很大目标函数里惩罚项的海森矩阵特征值就会变得异常巨大整个子问题的条件数急剧恶化。无约束优化的求解器在数值上会变得很僵硬每走一步都像是在深坑边缘探头探脑稍微有点舍入误差迭代就飘了。这就像用一根越来越硬的弹簧去拉一个物体弹簧越硬拉得越准但手稍微一抖整个系统就剧烈晃动。所以我用罚函数法的体验是它适合粗算不适合精算。想快速得到一个“约束大致满足、结果不会太离谱”的解罚函数法很香但如果对约束残差有硬指标比如要压到1e-6以下罚函数法会让你很痛苦。1.2 经典拉格朗日乘子法理论很优雅实际很难用经典拉格朗日乘子法走的是另一条路。我不惩罚约束而是给约束配上乘子构造拉格朗日函数L(x, λ) f(x) λᵀ c(x)然后在x和λ上同时寻找鞍点。理论上在凸问题、约束规范条件满足的情况下鞍点对应的x就是原问题的解λ就是最优乘子。这想法非常漂亮但实操起来有个巨大的难点对偶函数的计算往往极其困难。对偶函数定义为g(λ) inf_x L(x, λ)想对λ做梯度上升更新我就要先精确求出关于x的最小值点x*(λ)才能算出对偶函数的梯度∇g(λ) c(x*(λ))如果内部这个inf_x不能闭式求解那就只能再嵌套一层迭代每更新一次乘子都要完整跑一遍无约束优化代价极高。而且对于非凸问题经典拉格朗日函数的鞍点可能根本不存在或者对偶问题和原问题之间存在对偶间隙直接套用就会收敛到错误的结果。所以经典拉格朗日乘子法更像是一个理论工具用来推导KKT条件、分析解的性质很好用直接拿来做数值算法多数情况下是杀鸡用牛刀还杀不动。2. 增广拉格朗日函数法的工作原理和核心推导2.1 函数形式和罚项的作用增广拉格朗日函数法把上面两套思路拼在了一起。对等式约束问题min f(x)s.t. c(x) 0定义增广拉格朗日函数Lρ(x, λ) f(x) λᵀ c(x) (ρ/2)‖c(x)‖²看起来只是把普通拉格朗日函数加了一个二次罚项但这个改动是决定性的。二次罚项的存在让Lρ关于x在约束流形附近拥有了“恢复力”。当迭代点偏离约束边界时罚项会将它拉回可行域附近而乘子项λᵀc(x)则提供了经典拉格朗日才有的“精确性”。为什么说它精确注意一个关键区别在纯罚函数法中为了让解满足约束ρ必须趋于无穷但在增广拉格朗日法中我可以保持ρ为一个普通大小的常数通过不断更新乘子λ让约束残差c(x)最终趋于零。换句话说约束满足不是靠“罚得越来越重”而是靠“乘子记得越来越准”。这个特性在数值上极其宝贵。ρ可以不那么大子问题条件数就可控求解器不会因为罚因子过大而陷入病态。这很像一个老师傅带徒弟罚项是反馈校正每做一步都把偏差拉回来一点乘子则是累积经验做多了之后根本不需要大力道批评徒弟自己就知道该往哪走。2.2 乘子更新公式到底是怎么推出来的理解了函数形式剩下的核心问题就是乘子怎么更新。教科书上直接给出迭代式x_{k1} argmin_x Lρ(x, λ_k)λ_{k1} λ_k ρ c(x_{k1})很多初学者看到λ的更新公式会觉得很突然为什么步长恰好是ρ为什么方向是约束残差c(x)而不是别的这个公式其实是对偶上升法自然导出的。看对偶函数gρ(λ) inf_x Lρ(x, λ)假设x_ρ(λ)是让增广拉格朗日函数取得最小值的点那么对偶函数关于λ的梯度正好是约束残差∇gρ(λ) c(x_ρ(λ))想最大化对偶函数gρ(λ)最自然的做法就是沿梯度方向前进。梯度是c(x_ρ(λ))步长如果选ρ就得到λ_{k1} λ_k ρ c(x_{k1})。所以这个更新式本质上就是带步长ρ的梯度上升法只不过上升的变量是对偶乘子。从直觉上理解更简单如果第k1步求出的x_{k1}还没满足约束c(x_{k1}) 0说明当前乘子λ_k给出的“压力”还不够大我就要把乘子往上调让下一轮子问题更倾向于压低c(x)反之如果c(x_{k1}) 0我就往下调乘子。乘子就像积分项它不断累积历史偏差信息。正是因为有了这个“积分项”有限大小的ρ也能让约束最终精确满足。2.3 不等式约束怎么办不等式约束h(x) ≤ 0处理起来稍微绕一点但思路很直接。常见的做法是把它转化为等式约束引入一个辅助变量t ≥ 0h(x) t 0, t ≥ 0因此问题变成min f(x)s.t. h(x) t 0t ≥ 0然后对等式约束构造增广拉格朗日函数Lρ(x, t, λ) f(x) λᵀ(h(x) t) (ρ/2)‖h(x) t‖²在给定x、λ的情况下关于t做最小化是一个非常简单的一维问题显式解就是对max{0, -h(x) - λ/ρ}取投影。把它代回去经过整理就得到不等式约束情况下更常用的乘子更新形式λ_{k1} max{0, λ_k ρ h(x_{k1})}这个投影操作恰好对应着KKT条件里的互补松弛条件如果约束没有激活也就是h(x) 0那么乘子会被压到0如果约束已经激活乘子正常更新。这个处理方式在实际代码里非常好写也几乎不增加额外计算量。3. 收敛性、参数调节和停止准则3.1 什么条件下收敛增广拉格朗日函数法收敛性的标准结论在目标函数连续可微、约束规范条件成立、增广拉格朗日子问题能够精确求解等假设下迭代产生的点列会收敛到原问题的KKT点。对于凸问题这个收敛性通常更加稳健对于非凸问题只要初始点和参数选得不是太离谱也能得到局部收敛的结果。值得强调的是这里的“子问题精确求解”在实际中往往被放宽。理论推导时教科书会默认每一步argmin都是精确的但在工程项目里早期迭代根本不需要那么精确。我会先设定一个比较宽松的容差比如解到1e-3就开始更新乘子随着迭代慢慢收紧到1e-8。这么做不仅能大幅度省时间而且收敛过程往往更稳定。原因也好理解乘子更新本身带有噪声容忍能力前期用的粗糙解相当于给算法加了某种正则化。3.2 ρ怎么选、怎么动态调整参数ρ的选择是整个方法里最考验手感的地方。如果你把罚因子比喻成一根弹簧的刚度ρ太小约束残差的“回拉力”不足乘子更新很容易震荡迭代半天约束还是压不下去ρ太大子问题病态无约束优化求解器跑得很慢甚至x的更新本身就出现数值误差。我见过不少新手一上来就拍脑袋设ρ1然后发现不收敛又改成ρ1e6结果子问题完全跑不动。正确做法是采用递增策略。常见做法是每轮迭代后检查约束残差下降速度如果太慢就把ρ乘以一个倍数典型的偶数倍是2到10。更保守一点用1.1或者1.5的倍率逐步增长适合对最终精度要求很高的问题。还有一类做法是自适应的。一边看原始残差就是约束不满足的程度一边看对偶残差就是相邻两次迭代点变化的幅度。原始残差太大说明约束没拉住要考虑增大ρ对偶残差太大说明ρ偏大导致收敛步长太小可以考虑减小ρ。这个自适应逻辑我在后面专门讲这里先记住一点ρ不是越大越好而是要让原始残差和对偶残差保持基本同步下降。3.3 停止判据怎么定很多工程代码把停止条件简单写成迭代次数上限这种做法通常不靠谱。更合理的做法是同时监控两个量第一原始可行性。对等式约束就是‖c(x_k)‖对不等式约束就是‖max{0, h(x_k)}‖它反映了当前解离可行域还有多远。第二乘子更新的稳定程度。如果λ_k的变化幅度已经很小通常意味着对偶变量已经收敛继续迭代也榨不出更多精度。我个人的经验是原始可行性作为主判据乘子变化量作为辅助判据。当原始残差小于某个阈值比如1e-6并且相对上次迭代的改善小于10%就直接停止。这样做的好处是即便碰到约束本身尺度很小的问题也不会因为绝对阈值设得不合适而陷入死循环。4. 从增广拉格朗日到ADMM工程中最常用的一层皮4.1 变量拆分让增广拉格朗日能拆成小任务增广拉格朗日函数法的收敛性质已经很好但在很多工程问题上直接把Lρ关于整个x求最小化还是太累。尤其当目标函数里有可分离结构的时候比如min f(x) g(z)s.t. x z这里的两个变量x和z之间隔着约束但目标函数关于它们是可分的。如果直接对x和z联合求最小f和g纠缠在一起问题并不好解。但如果我们把增广拉格朗日函数写出来Lρ(x, z, λ) f(x) g(z) λᵀ(x - z) (ρ/2)‖x - z‖²然后不是一次性同时优化x和z而是拆成两步交替优化先固定z和λ只优化x再固定x和λ只优化z。这就是ADMM的基本思想Alternating Direction Method of Multipliers。ADMM本质上就是对增广拉格朗日函数做坐标下降法只不过坐标块就分成x和z两块。它每一轮的计算量大幅下降而且很多实际情况下单块子问题存在闭式解或高效的求解方法于是整个迭代过程可以变得非常快。4.2 交替方向迭代把鞍点问题变成一块一块地啃ADMM的标准更新过程如下x_{k1} argmin_x Lρ(x, z_k, λ_k)z_{k1} argmin_z Lρ(x_{k1}, z, λ_k)λ_{k1} λ_k ρ(x_{k1} - z_{k1})注意这里的x更新只用到了z_k和λ_kz更新用到了最新算出的x_{k1}。这种“快式”交替更新看似只是把联合优化简单拆开但它带来的收敛轨迹和联合优化完全不同。在实践中你会发现ADMM的初始几轮迭代特别有效率能在很短的迭代次数内把目标函数值压到一个理想的量级后面的迭代再慢慢收紧可行性。ADMM对凸问题有很好的收敛保证而且它天然适合并行计算。如果x和z各自又包含多个可分离的子变量那这些子任务完全可以丢到不同机器或者不同线程上算最后再汇总更新乘子。这也是它在分布式机器学习、联邦学习这类场景下被大量使用的原因。4.3 软阈值算子的诞生ADMM最漂亮的例子之一是求解带l1范数正则化的线性回归也就是LASSOmin (1/2)‖Ax - b‖² λ‖x‖₁直接拿这个目标函数做梯度类方法l1范数的不可导点会带来一堆麻烦。但用ADMM我把变量复制一份min (1/2)‖Ax - b‖² λ‖z‖₁s.t. x - z 0那么增广拉格朗日函数拆成两块后每一轮迭代里x更新是一个标准的最小二乘问题系数矩阵是AᵀA ρI。这个矩阵只需要做一次分解后续每轮都是回代非常快。z更新则变成了一个纯标量化问题它的闭式解就是软阈值算子z soft_threshold(x_{k1} u_k, λ/ρ)其中soft_threshold(a, t) sign(a)·max{0, |a| - t}。一个看起来不可导、纠缠着矩阵和稀疏性的优化问题被ADMM干净利落地拆成了一个线性代数子问题和一个逐元素软阈值操作。这套组合在压缩感知、图像去噪、稀疏信号恢复等领域几乎是标准配置我建议所有做相关方向的人都把这段推导亲手写一遍。5. 完整可复现示例5.1 用增广拉格朗日法求解等式约束二次规划我用一个很小的等式约束二次规划把增广拉格朗日法的完整流程走一遍。问题如下min 0.5·xᵀQx cᵀxs.t. A·x b取矩阵Q [[2, 0], [0, 2]]c [-2, -2]A [1, 1]b 1这个问题的KKT条件能直接解出来方便对照。手动解一下可以得到最优x [0.5, 0.5]最优乘子λ 1。下面用增广拉格朗日法迭代逼近这个结果。import numpy as np def augmented_lagrangian_solver(Q, c, A, b, x0, lam0, rho1.0, max_iter100, tol1e-8): x np.array(x0, dtypenp.float64) lam np.array(lam0, dtypenp.float64) n Q.shape[0] # 预分解系数矩阵避免每轮重新做分解 M Q rho * A.T A L np.linalg.cholesky(M) history [] for k in range(max_iter): # 1. 求解子问题min_x Lrho(x, lam) rhs rho * A.T b - c - A.T lam y np.linalg.solve(L, rhs) x_new np.linalg.solve(L.T, y) # 2. 乘子更新 lam_new lam rho * (A x_new - b) # 3. 记录和收敛判断 primal_res np.linalg.norm(A x_new - b) dual_res np.linalg.norm(rho * A.T (x_new - x)) history.append((primal_res, dual_res)) x, lam x_new, lam_new if primal_res tol and dual_res tol: break return x, lam, history Q np.array([[2.0, 0.0], [0.0, 2.0]]) c np.array([-2.0, -2.0]) A np.array([[1.0, 1.0]]) b np.array([1.0]) x_opt, lam_opt, hist augmented_lagrangian_solver( Q, c, A, b, x0[0.0, 0.0], lam0[0.0], rho1.0 ) print(x , x_opt) print(lambda , lam_opt) print(constraint residual , A x_opt - b) print(iterations used , len(hist))运行这个代码可以看到约束残差迅速下降x收敛到[0.5, 0.5]乘子收敛到1。这个例子虽然简单但把增广拉格朗日的三个关键动作都演示到位了求解子问题、更新乘子、检查残差。5.2 扩展到ADMM求解LASSO的思路把上面的代码扩展成ADMM关键变化是变量被拆成x和z两块并且z更新步骤要换成软阈值。还是LASSO问题min (1/2)‖Ax - b‖² λ‖z‖₁s.t. x - z 0用缩放变量u λ/ρADMM可以写成更紧凑的格式x_{k1} (AᵀA ρI)^{-1}(Aᵀb ρ(z_k - u_k))z_{k1} soft_threshold(x_{k1} u_k, λ/ρ)u_{k1} u_k x_{k1} - z_{k1}我写一下Python实现的核心部分def soft_threshold(a, t): return np.sign(a) * np.maximum(np.abs(a) - t, 0.0) def admm_lasso(A, b, lam, rho1.0, max_iter1000, tol1e-6): m, n A.shape # 预分解 (A^T A rho I) M A.T A rho * np.eye(n) L np.linalg.cholesky(M) Atb A.T b x np.zeros(n) z np.zeros(n) u np.zeros(n) for k in range(max_iter): # x-update rhs Atb rho * (z - u) y np.linalg.solve(L, rhs) x np.linalg.solve(L.T, y) # z-update z soft_threshold(x u, lam / rho) # u-update u u x - z primal_res np.linalg.norm(x - z) dual_res np.linalg.norm(rho * (z - x)) if primal_res tol and dual_res tol: break return x这套代码改造成本极低但处理的问题从简单的二次规划扩展到了带稀疏正则的高维问题。实际跑合成数据时你会发现它不像普通梯度法那样需要小心翼翼调学习率也不需要处理l1范数的次梯度整个流程非常清爽。6. 我踩过的坑和值得注意的细节6.1 子问题求解的精度不需要一开始就拉满我最早用增广拉格朗日法时有个习惯总想把每一步子问题都解得非常精确结果整个程序慢得没法接受。后来才意识到乘子更新本身每一轮都在变动前期把子问题解得再准也只是为了一个即将过期的λ服务的。更合理的做法是前期用宽松容差快速迭代让乘子先跑到大致靠谱的区域最后几轮再把子问题精度提上去。这样总迭代次数和单轮时间都能明显下降。实际操作中如果子问题是用梯度下降或者拟牛顿法求解的还可以把上一轮迭代的x作为下一轮的初始值。因为λ变化通常不会很大相邻两轮的子问题最优解位置也比较接近热启动能省掉大量重复计算。6.2 约束量级不一致会让乘子调整失衡一个特别容易被忽视的坑是约束的尺度问题。如果两个约束残差分别处在1e-6和1e6的量级放到同一个增广拉格朗日函数里乘子更新的步长就很容易被大尺度约束主导。小尺度约束的乘子可能一直被噪声淹没导致对应的约束迟迟不能满足。遇到这种情况我一般会先对约束做归一化处理把每一条约束除以一个合适的基准尺度。这就好比用同一个弹簧去拉一辆卡车和一个玩具车如果没有匹配的刚度很容易出现一个还没拉到、另一个已经弹飞了的情况。归一化是个土办法但真的有效。6.3 自适应调节ρ的实操前面说了ρ不能太大也不能太小实际代码里可以用一种简单的自适应策略来缓解调参焦虑。基本逻辑是如果原始残差大于对偶残差的某个倍数说明约束没有足够优先增大ρ如果对偶残差大于原始残差的某个倍数说明当前步骤推进太慢减小ρ。我用过的一个经验版本是把ρ乘以或除以一个系数通常取2然后做上下界限制。需要注意的是改变ρ之后之前预分解的矩阵M Q ρAᵀA也需要重新分解。如果问题维度很高频繁分解的开销很大。所以我只在必要时才调整比如每50轮检查一次而不是每轮都动。6.4 对非凸问题能救急但别迷信增广拉格朗日函数法在处理非凸问题时偶尔会给人“这也能收敛”的惊喜但它本质上并没有全局收敛保证。我见过有人在带约束的神经网络训练里硬套ADMM效果时好时坏。对于强非凸问题乘子序列可能震荡初始点选择对结果影响极大。如果非要在非凸场景里用增广拉格朗日我建议一是把ρ设得稍大一些给迭代更多“束缚力”二是多试几组随机初始点看乘子轨迹是否稳定三是别等它完全收敛把它当作一个寻找良好初值的手段后面再切换到其他更合适的算法。我在实际项目里用过很多次这套方法论比较深的体会是增广拉格朗日类算法真正强大的地方不在于某个问题它一定碾压其他方法而在于它提供了一种非常通用的思考框架把复杂约束问题拆成“无约束子问题乘子更新”两个部分。每当新问题出现我总习惯先看看能不能套进这个框架通常在画完变量拆分图后求解路径自己就会浮出来。对做优化算法应用的人来说这套思维方式比记住任何一个具体公式都值钱。