非线性规划中的增广拉格朗日法（Augmented Lagrangian Method in Nonlinear Programming）
字数 3810 2025-12-17 10:39:23

非线性规划中的增广拉格朗日法（Augmented Lagrangian Method in Nonlinear Programming）

我将循序渐进地讲解这个在非线性规划中至关重要的方法，从基本问题引入，到核心思想剖析，再到算法细节和收敛性质。

第一步：从标准约束优化问题与拉格朗日函数法引入

  1. 问题模型：我们考虑带有等式约束的非线性规划问题：
    \(\min f(x)\)
    \(\text{s.t. } c_i(x) = 0, \quad i = 1, \ldots, m\)
    其中，\(x \in \mathbb{R}^n\)， \(f: \mathbb{R}^n \to \mathbb{R}\) 和 \(c_i: \mathbb{R}^n \to \mathbb{R}\) 是连续可微函数。为简化，我们先将讨论集中在等式约束上，不等式约束的扩展是增广拉格朗日法的重要延伸。

  2. 拉格朗日函数法的不足：对于这类约束问题，经典的拉格朗日函数为 \(L(x, \lambda) = f(x) + \sum_{i=1}^m \lambda_i c_i(x)\)，其中 \(\lambda\) 是拉格朗日乘子向量。在最优解 \(x^*\) 满足约束规格的条件下，存在 \(\lambda^*\) 使得 \(\nabla_x L(x^*, \lambda^*) = 0\)。然而，直接最小化 \(L(x, \lambda)\) 对于固定的 \(\lambda\) 通常不是求解原问题有效方法。因为 \(L(x, \lambda)\) 关于 \(x\) 的无约束极小点可能不对应于满足 \(c(x)=0\) 的点，特别是当 \(\lambda\) 远离 \(\lambda^*\) 时。该方法缺乏对违反约束的惩罚机制，无法将无约束优化过程“拉”向可行域。

第二步：惩罚函数法的思想及其缺点

  1. 惩罚函数法：为了强制满足约束，惩罚函数法构造一个无约束问题：\(\min_x \phi(x; \mu) = f(x) + \frac{\mu}{2} \sum_{i=1}^m c_i(x)^2\)，其中 \(\mu > 0\) 是惩罚参数。第二项是二次惩罚项。当 \(\mu \to \infty\) 时，这个无约束问题的解会逼近原约束问题的解。其优点是原理简单，可将约束问题转化为一系列无约束问题。

  2. 惩罚函数法的弊端：为了获得高精度的可行解，必须让惩罚参数 \(\mu\) 趋于无穷大。这会导致惩罚函数 \(\phi(x; \mu)\) 的海森矩阵条件数变得非常差（病态），使得无约束优化子问题极其难以用数值方法精确求解。即使找到了子问题解，其对应的拉格朗日乘子估计通常也不准确，收敛缓慢。

第三步：增广拉格朗日函数的核心构造——融合两者优势

  1. 核心洞察：增广拉格朗日法巧妙地结合了拉格朗日函数和惩罚函数的思想，旨在克服两者的缺点。它对标准的拉格朗日函数增加了一个惩罚项，故名“增广”。

  2. 函数定义：对于等式约束问题，增广拉格朗日函数定义为：
    \(L_A(x, \lambda; \mu) = f(x) + \sum_{i=1}^m \lambda_i c_i(x) + \frac{\mu}{2} \sum_{i=1}^m c_i(x)^2\)
    其中，\(\lambda\) 是乘子向量（可视为当前对最优乘子的估计），\(\mu > 0\) 是惩罚参数。比较 \(L_A\) 和 \(\phi\)：

  • \(L_A\) 在惩罚项 \(\frac{\mu}{2} \sum c_i^2\) 的基础上，增加了线性项 \(\sum \lambda_i c_i\)。
    • 这个线性项具有深刻的几何意义：它改变了惩罚函数的“谷底”形状。
  1. 关键性质：设 \(x^*\) 是原问题满足约束规格的局部最优解，对应乘子为 \(\lambda^*\)。那么，对于足够大的固定 \(\mu\)，存在 \(\mu_0 > 0\)，使得当 \(\mu \ge \mu_0\) 时，\(x^*\) 是增广拉格朗日函数 \(L_A(x, \lambda^*; \mu)\) 的一个无约束局部极小点。这是该方法最重要的理论基础。它意味着，如果我们能准确猜出（或通过迭代逼近）乘子 \(\lambda^*\)，我们可以在一个有限的惩罚参数 \(\mu\) 下，通过求解一个（条件良好的）无约束优化问题得到精确解 \(x^*\)。这避免了惩罚函数法中 \(\mu \to \infty\) 的必要性。

第四步：增广拉格朗日法的基本算法框架（乘子法）

  1. 算法逻辑：由于我们不知道最优乘子 \(\lambda^*\)，算法采用迭代方式同时更新变量 \(x\) 和乘子估计 \(\lambda\)。这是一个典型的双重迭代过程：
  • 内层迭代（x-更新）：固定当前的乘子估计 \(\lambda^k\) 和惩罚参数 \(\mu_k\)，求解（近似）无约束优化子问题：\(x^{k+1} \approx \arg\min_{x} L_A(x, \lambda^k; \mu_k)\)。
    • 外层迭代（λ-更新）：根据当前解对约束的违反程度，更新乘子估计。最经典的更新公式源于对KKT条件的观察：
      \(\lambda_i^{k+1} = \lambda_i^k + \mu_k c_i(x^{k+1}), \quad i=1,\ldots,m\)
      这个更新规则非常直观：如果当前解 \(x^{k+1}\) 违反第 \(i\) 个约束（即 \(c_i(x^{k+1}) \neq 0\)），我们就沿着使约束满足的方向调整乘子。调整的幅度与违反程度 \(c_i(x^{k+1})\) 和惩罚参数 \(\mu_k\) 成正比。
  1. 惩罚参数更新策略：\(\mu_k\) 通常不需要趋于无穷大。一种常见策略是：从一个适中的 \(\mu_0\) 开始，如果在某次迭代中约束违反度的下降不够显著（例如， \(\|c(x^{k+1})\|\) 没有比 \(\|c(x^k)\|\) 缩小某个比例），则增大 \(\mu_k\)（例如乘以一个因子如2或10），以加强惩罚，迫使下一次迭代的解更可行。一旦约束满足得很好，\(\mu_k\) 可以保持不变。

第五步：处理不等式约束的扩展

  1. 转换技巧：对于不等式约束 \(g_j(x) \le 0\)，可以引入非负松弛变量 \(s_j^2\) 将其转化为等式约束：\(g_j(x) + s_j^2 = 0\)。将其代入增广拉格朗日函数，并可以解析地消去松弛变量 \(s_j\)，得到一种更简洁的形式。

  2. 简化形式：对于不等式约束 \(g_j(x) \le 0\)，其对应的增广拉格朗日项（经过消去松弛变量后）通常写作：
    \(\frac{\mu}{2} \left[ \max\left(0, g_j(x) + \frac{\lambda_j}{\mu} \right) \right]^2 - \frac{\lambda_j^2}{2\mu}\)
    其中 \(\lambda_j \ge 0\) 是对应不等式约束的乘子。乘子更新规则变为：
    \(\lambda_j^{k+1} = \max\left(0, \lambda_j^k + \mu_k g_j(x^{k+1}) \right)\)
    这个形式在实践中更为常用，它直接处理不等式约束，而无需显式引入额外变量。

第六步：方法的优势、收敛性与总结

  1. 主要优势：
    • 数值稳定性：与惩罚函数法相比，它允许在有限、适中的惩罚参数下工作，子问题的Hessian矩阵条件数更好，求解更稳定高效。
    • 精确性：在精确的算术下，只要惩罚参数足够大，它可以在不驱动其趋于无穷的情况下，产生满足约束的精确解（精确满足约束，而不仅仅是近似）。
  • 对初始点依赖较低：对初始乘子估计 \(\lambda^0\) 通常不敏感，即使初始估计很差，算法也能通过更新规则自我修正。

  1. 收敛性质：在适当的假设下（如目标函数和约束函数足够光滑，原问题满足二阶充分条件等），增广拉格朗日法（乘子法）具有全局收敛性和局部超线性收敛速率。这意味着，一旦迭代点进入最优解的一个邻域，乘子更新能快速校正，使得收敛速度非常快。

  2. 与相关方法的联系：增广拉格朗日法是连接惩罚函数法和拉格朗日函数法的桥梁。它也构成了许多现代优化软件的基础，并且是指交替方向乘子法等分布式优化算法的核心组成部分。

总结来说，非线性规划中的增广拉格朗日法是一种通过将惩罚项与拉格朗日乘子估计相结合，来求解约束优化问题的强大框架。它通过迭代求解条件良好的无约束子问题和智能地更新乘子，有效地克服了传统惩罚函数法的病态问题，兼具鲁棒性和高效性。

非线性规划中的增广拉格朗日法（Augmented Lagrangian Method in Nonlinear Programming） 我将循序渐进地讲解这个在非线性规划中至关重要的方法，从基本问题引入，到核心思想剖析，再到算法细节和收敛性质。 第一步：从标准约束优化问题与拉格朗日函数法引入 问题模型 ：我们考虑带有等式约束的非线性规划问题： \( \min f(x) \) \( \text{s.t. } c_ i(x) = 0, \quad i = 1, \ldots, m \) 其中，\( x \in \mathbb{R}^n \)， \( f: \mathbb{R}^n \to \mathbb{R} \) 和 \( c_ i: \mathbb{R}^n \to \mathbb{R} \) 是连续可微函数。为简化，我们先将讨论集中在等式约束上，不等式约束的扩展是增广拉格朗日法的重要延伸。 拉格朗日函数法的不足 ：对于这类约束问题，经典的拉格朗日函数为 \( L(x, \lambda) = f(x) + \sum_ {i=1}^m \lambda_ i c_ i(x) \)，其中 \( \lambda \) 是拉格朗日乘子向量。在最优解 \( x^* \) 满足约束规格的条件下，存在 \( \lambda^* \) 使得 \( \nabla_ x L(x^ , \lambda^ ) = 0 \)。然而，直接最小化 \( L(x, \lambda) \) 对于固定的 \( \lambda \) 通常 不是 求解原问题有效方法。因为 \( L(x, \lambda) \) 关于 \( x \) 的无约束极小点可能不对应于满足 \( c(x)=0 \) 的点，特别是当 \( \lambda \) 远离 \( \lambda^* \) 时。该方法缺乏对违反约束的惩罚机制，无法将无约束优化过程“拉”向可行域。 第二步：惩罚函数法的思想及其缺点 惩罚函数法 ：为了强制满足约束，惩罚函数法构造一个无约束问题：\( \min_ x \phi(x; \mu) = f(x) + \frac{\mu}{2} \sum_ {i=1}^m c_ i(x)^2 \)，其中 \( \mu > 0 \) 是惩罚参数。第二项是二次惩罚项。当 \( \mu \to \infty \) 时，这个无约束问题的解会逼近原约束问题的解。其优点是原理简单，可将约束问题转化为一系列无约束问题。 惩罚函数法的弊端 ：为了获得高精度的可行解，必须让惩罚参数 \( \mu \) 趋于无穷大。这会导致惩罚函数 \( \phi(x; \mu) \) 的 海森矩阵条件数 变得非常差（病态），使得无约束优化子问题极其难以用数值方法精确求解。即使找到了子问题解，其对应的拉格朗日乘子估计通常也不准确，收敛缓慢。 第三步：增广拉格朗日函数的核心构造——融合两者优势 核心洞察 ：增广拉格朗日法巧妙地结合了拉格朗日函数和惩罚函数的思想，旨在克服两者的缺点。它对标准的拉格朗日函数 增加 了一个惩罚项，故名“增广”。 函数定义 ：对于等式约束问题，增广拉格朗日函数定义为： \( L_ A(x, \lambda; \mu) = f(x) + \sum_ {i=1}^m \lambda_ i c_ i(x) + \frac{\mu}{2} \sum_ {i=1}^m c_ i(x)^2 \) 其中，\( \lambda \) 是乘子向量（可视为当前对最优乘子的估计），\( \mu > 0 \) 是惩罚参数。比较 \( L_ A \) 和 \( \phi \)： \( L_ A \) 在惩罚项 \( \frac{\mu}{2} \sum c_ i^2 \) 的基础上，增加了线性项 \( \sum \lambda_ i c_ i \)。 这个线性项具有深刻的几何意义：它改变了惩罚函数的“谷底”形状。 关键性质 ：设 \( x^* \) 是原问题满足约束规格的局部最优解，对应乘子为 \( \lambda^* \)。那么，对于足够大的固定 \( \mu \)， 存在 \( \mu_ 0 > 0 \)，使得当 \( \mu \ge \mu_ 0 \) 时，\( x^* \) 是增广拉格朗日函数 \( L_ A(x, \lambda^ ; \mu) \) 的一个 无约束局部极小点 。这是该方法最重要的理论基础。它意味着，如果我们能准确猜出（或通过迭代逼近）乘子 \( \lambda^ \)，我们可以在一个 有限 的惩罚参数 \( \mu \) 下，通过求解一个（条件良好的）无约束优化问题得到精确解 \( x^* \)。这避免了惩罚函数法中 \( \mu \to \infty \) 的必要性。 第四步：增广拉格朗日法的基本算法框架（乘子法） 算法逻辑 ：由于我们不知道最优乘子 \( \lambda^* \)，算法采用迭代方式同时更新变量 \( x \) 和乘子估计 \( \lambda \)。这是一个典型的 双重迭代 过程： 内层迭代（x-更新） ：固定当前的乘子估计 \( \lambda^k \) 和惩罚参数 \( \mu_ k \)，求解（近似）无约束优化子问题：\( x^{k+1} \approx \arg\min_ {x} L_ A(x, \lambda^k; \mu_ k) \)。 外层迭代（λ-更新） ：根据当前解对约束的违反程度，更新乘子估计。最经典的更新公式源于对KKT条件的观察： \( \lambda_ i^{k+1} = \lambda_ i^k + \mu_ k c_ i(x^{k+1}), \quad i=1,\ldots,m \) 这个更新规则非常直观：如果当前解 \( x^{k+1} \) 违反第 \( i \) 个约束（即 \( c_ i(x^{k+1}) \neq 0 \)），我们就沿着使约束满足的方向调整乘子。调整的幅度与违反程度 \( c_ i(x^{k+1}) \) 和惩罚参数 \( \mu_ k \) 成正比。 惩罚参数更新策略 ：\( \mu_ k \) 通常不需要趋于无穷大。一种常见策略是：从一个适中的 \( \mu_ 0 \) 开始，如果在某次迭代中约束违反度的下降不够显著（例如， \( \|c(x^{k+1})\| \) 没有比 \( \|c(x^k)\| \) 缩小某个比例），则增大 \( \mu_ k \)（例如乘以一个因子如2或10），以加强惩罚，迫使下一次迭代的解更可行。一旦约束满足得很好，\( \mu_ k \) 可以保持不变。 第五步：处理不等式约束的扩展 转换技巧 ：对于不等式约束 \( g_ j(x) \le 0 \)，可以引入非负松弛变量 \( s_ j^2 \) 将其转化为等式约束：\( g_ j(x) + s_ j^2 = 0 \)。将其代入增广拉格朗日函数，并可以解析地消去松弛变量 \( s_ j \)，得到一种更简洁的形式。 简化形式 ：对于不等式约束 \( g_ j(x) \le 0 \)，其对应的增广拉格朗日项（经过消去松弛变量后）通常写作： \( \frac{\mu}{2} \left[ \max\left(0, g_ j(x) + \frac{\lambda_ j}{\mu} \right) \right]^2 - \frac{\lambda_ j^2}{2\mu} \) 其中 \( \lambda_ j \ge 0 \) 是对应不等式约束的乘子。乘子更新规则变为： \( \lambda_ j^{k+1} = \max\left(0, \lambda_ j^k + \mu_ k g_ j(x^{k+1}) \right) \) 这个形式在实践中更为常用，它直接处理不等式约束，而无需显式引入额外变量。 第六步：方法的优势、收敛性与总结 主要优势 ： 数值稳定性 ：与惩罚函数法相比，它允许在有限、适中的惩罚参数下工作，子问题的Hessian矩阵条件数更好，求解更稳定高效。 精确性 ：在精确的算术下，只要惩罚参数足够大，它可以在不驱动其趋于无穷的情况下，产生满足约束的精确解（精确满足约束，而不仅仅是近似）。 对初始点依赖较低 ：对初始乘子估计 \( \lambda^0 \) 通常不敏感，即使初始估计很差，算法也能通过更新规则自我修正。 收敛性质 ：在适当的假设下（如目标函数和约束函数足够光滑，原问题满足二阶充分条件等），增广拉格朗日法（乘子法）具有 全局收敛性 和 局部超线性收敛速率 。这意味着，一旦迭代点进入最优解的一个邻域，乘子更新能快速校正，使得收敛速度非常快。 与相关方法的联系 ：增广拉格朗日法是连接 惩罚函数法 和 拉格朗日函数法 的桥梁。它也构成了许多现代优化软件的基础，并且是指 交替方向乘子法 等分布式优化算法的核心组成部分。 总结来说， 非线性规划中的增广拉格朗日法 是一种通过将惩罚项与拉格朗日乘子估计相结合，来求解约束优化问题的强大框架。它通过迭代求解条件良好的无约束子问题和智能地更新乘子，有效地克服了传统惩罚函数法的病态问题，兼具鲁棒性和高效性。