增广拉格朗日法

增广拉格朗日法 (Augmented Lagrangian Method)

增广拉格朗日法 (Augmented Lagrangian Method, ALM)，亦称 乘子法 (Method of Multipliers)，是求解带 约束优化 (Constrained Optimization) 问题的一类重要数值方法。该方法由 Hestenes (1969) 和 Powell (1969) 各自独立提出，其核心思想是将 拉格朗日乘子法 (Lagrange Multiplier Method) 与 惩罚函数法 (Penalty Method) 有机结合，从而克服两者各自的缺陷：惩罚法随惩罚参数趋于无穷时出现的 病态 (ill-conditioning) 问题，以及经典拉格朗日法要求 海塞矩阵 (Hessian Matrix) 在约束流形上正定这一过于严苛的条件。

增广拉格朗日法现已成为求解大规模约束优化问题的标准工具之一，广泛应用于 机器学习、最优控制、图像处理、压缩感知 以及 偏微分方程约束优化 等领域。

问题的提法

考虑如下等式的束优化问题：

其中 $f: \mathbb{R}^n \to \mathbb{R}$ 是 目标函数 (Objective Function)，$\mathbf{c}(\mathbf{x}) = (c_1(\mathbf{x}), \dots, c_m(\mathbf{x}))^T = \mathbf{0}$ 是等式约束。对于不等式约束 $g_j(\mathbf{x}) \leq 0$，可通过引入松弛变量将其转化为等式约束，或直接扩展增广拉格朗日函数的定义。

增广拉格朗日函数

增广拉格朗日函数 (Augmented Lagrangian) 在经典拉格朗日函数的基础上增加了一个二次惩罚项，定义为：

其中：

• $\boldsymbol{\lambda} = (\lambda_1, \dots, \lambda_m)^T$ 是 拉格朗日乘子 (Lagrange Multiplier) 向量，其最优值即为 KKT 条件中的乘子。
• $\mu > 0$ 是 惩罚参数 (Penalty Parameter)，控制着约束违反项的惩罚力度。
• 第三项 $\frac{\mu}{2} \sum c_i^2$ 正是惩罚函数法中的二次惩罚项。

算法的核心迭代

增广拉格朗日法并非同时更新所有变量，而是采用交替更新的策略。记第 $k$ 次迭代的近似解为 $\mathbf{x}^{(k)}$，拉格朗日乘子估计为 $\boldsymbol{\lambda}^{(k)}$，惩罚参数为 $\mu_k$。每一次完整的迭代包含以下两步：

1. 子问题求解（$\mathbf{x}$ 的更新）：固定当前的 $\boldsymbol{\lambda}^{(k)}$ 和 $\mu_k$，以近似无约束方式求解 \[ \mathbf{x}^{(k+1)} \approx \arg\min_{\mathbf{x}} \mathcal{L}_A(\mathbf{x}, \boldsymbol{\lambda}^{(k)}; \mu_k) \] 通常只需要求得不精确解即可（达到一定容差），无需精确收敛。这一步可借助 梯度下降法 (Gradient Descent)、拟牛顿法 (Quasi-Newton Method) 或 共轭梯度法 (Conjugate Gradient Method) 完成。
2. 乘子更新（$\boldsymbol{\lambda}$ 的更新）：按以下显式公式更新乘子估计 \[ \lambda_i^{(k+1)} = \lambda_i^{(k)} + \mu_k \, c_i(\mathbf{x}^{(k+1)}), \quad i = 1, \dots, m \] 这一更新规则源于对增广拉格朗日函数在稳定点处一阶条件的重新整理：在最优解 $\mathbf{x}^*$ 处，$\nabla f(\mathbf{x}^*) + \sum (\lambda_i + \mu c_i(\mathbf{x}^*)) \nabla c_i(\mathbf{x}^*) = 0$，这表明 $\lambda_i^*$ 的修正方向正是约束违反量乘以惩罚参数。

惩罚参数 $\mu_k$ 也可动态调整：若当前约束违反量下降不足，则增大 $\mu_{k+1} = \rho \mu_k$（$\rho > 1$）；反之可保持不变或适当减小。

与惩罚法和拉格朗日法的对比

• 相对于惩罚函数法：惩罚法仅当 $\mu \to \infty$ 时极限解才严格满足约束，但此时海塞矩阵 $\nabla^2 \mathcal{L}_A$ 的条件数趋于无穷，导致数值算法严重病态。ALM 通过引入乘子项 $\lambda_i$，在有限 $\mu$ 下即可使 $\mathbf{x}^{(k)} \to \mathbf{x}^*$，无需令 $\mu \to \infty$，从根本上避开了病态问题。事实上，可以证明：若 $\boldsymbol{\lambda}^{(k)}$ 恰好等于真实的拉格朗日乘子 $\boldsymbol{\lambda}^*$，则对任意 $\mu > 0$，$\mathbf{x}^*$ 都是 $\mathcal{L}_A(\cdot, \boldsymbol{\lambda}^*; \mu)$ 的一个严格局部极小点。
• 相对于经典拉格朗日法：经典拉格朗日法直接在 $(\mathbf{x}, \boldsymbol{\lambda})$ 空间求解鞍点系统 $\nabla f + \nabla \mathbf{c} \cdot \boldsymbol{\lambda} = 0$，需解一阶必要条件方程组，收敛性要求海塞矩阵在约束切空间上正定。ALM 将乘子更新与原始变量更新解耦，每次只需求解一个无约束（或简单界约束）的子问题，实现更为稳健。

不等式约束的推广

对于含不等式约束 $g_j(\mathbf{x}) \leq 0$ 的问题，可通过引入松弛变量 $s_j \geq 0$ 并令 $g_j(\mathbf{x}) + s_j = 0$，将其纳入等式约束框架，再消去 $s_j$。最终得到针对不等式约束的增广拉格朗日函数：

$\mathcal{L}_A$($\mathbf{x}$, $\boldsymbol{\lambda}$; $\mu$) = f($\mathbf{x}$) + $\sum_{j=1}^{p}$ P($g_j$($\mathbf{x}$), $\lambda_j$; $\mu$)

其中惩罚-乘子修正项 $P$ 通常采用 Rockafellar 形式：

-\dfrac{$\lambda^2$}{2$\mu$}, \& $\text{否则}$ \end{cases}

对应的乘子更新公式为 $\lambda_j^{(k+1)} = \max(0, \lambda_j^{(k)} + \mu_k g_j(\mathbf{x}^{(k+1)}))$，这保证了不等式乘子的非负性。

交替方向乘子法 (ADMM)

增广拉格朗日法的一个重要变体是 交替方向乘子法 (Alternating Direction Method of Multipliers, ADMM)，专门用于求解含两块分离变量的结构化凸优化问题：

ADMM 将 ALM 中的联合子问题分解为关于 $\mathbf{x}$ 和 $\mathbf{z}$ 的两个较小的子问题交替求解，每一步仅涉及单个变量块，在大规模分布式优化和 统计学习 中应用极为广泛。

收敛性与实际应用

增广拉格朗日法在较弱条件下具有全局收敛性：当 $f$ 和 $c_i$ 光滑且满足适当的约束规范（如 LICQ）时，若每次子问题求解足够精确且惩罚参数 $\mu_k$ 有上界，则迭代序列收敛到 KKT 点。实践中，ALM 的超线性收敛速度可通过在子问题求解中采用 牛顿法 或其近似来实现。

典型应用包括：

• 分布式优化：ADMM 用于多智能体网络的协同训练、资源分配问题。
• 图像与信号处理：全变分去噪、压缩感知重构中的 $\ell_1$ 正则化问题。
• 机器学习的约束训练：在 支持向量机 (SVM) 和大规模逻辑回归中处理约束或正则项。
• 最优控制与模型预测控制 (MPC)：处理动态系统约束和终端约束。

小结

增广拉格朗日法通过在经典拉格朗日框架中注入二次惩罚项，以优雅且高效的方式弥合了惩罚法的数值病态与纯拉格朗日法收敛条件严苛之间的鸿沟。其核心洞察在于：乘子估计 $\boldsymbol{\lambda}$ 的逐次修正与惩罚参数 $\mu$ 的适度调节协同作用，使得算法既能在有限惩罚下获得可行解，又保持了良好的数值稳定性。从理论优化走向大规模计算实践，ALM 及其衍生方法（尤其是 ADMM）已成为现代计算科学与工程优化中不可或缺的核心算法。