非线性规划中的修正拉格朗日法（Augmented Lagrangian Method）
字数 2885 2025-12-10 09:15:27

非线性规划中的修正拉格朗日法（Augmented Lagrangian Method）

好的，我们开始讲解“非线性规划中的修正拉格朗日法”，也被更广泛地称为“增广拉格朗日法”。我将从最基础的约束优化问题开始，循序渐进地展开，确保每一步都清晰易懂。

步骤1：从基础约束优化问题与经典拉格朗日法讲起

我们考虑一个标准的非线性规划问题：
最小化 f(x)
满足 c_i(x) = 0, i = 1, …, m （等式约束）
这里，x ∈ R^n 是决策变量，f: R^n -> R 是目标函数，c_i: R^n -> R 是约束函数。

  1. 经典拉格朗日函数：对于此类问题，我们引入拉格朗日乘子 λ_i，构造经典拉格朗日函数：L(x, λ) = f(x) + Σ_{i=1}^{m} λ_i * c_i(x)。
  2. 一阶最优性条件：在满足一定约束规格（如LICQ）的最优点 x* 处，存在乘子 λ* 使得梯度为零：∇_x L(x*, λ*) = 0 且 c_i(x*) = 0。这组方程就是著名的KKT条件（对于只有等式约束的情况）。
  3. 经典法的局限性：理论上，我们可以通过求解方程组 ∇_x L(x, λ) = 0 和 c(x)=0 来寻找最优解。但这通常是一个非线性方程组，求解困难。更重要的是，经典拉格朗日函数 L(x, λ) 关于 x 在鞍点 (x*, λ*) 处可能不是凸的，这意味着直接最小化 L(x, λ)（对于固定的λ）可能不会导向可行解，甚至无界。它缺乏“强制性”，即当 x 远离可行域时，L(x, λ) 的值不会显著增大以惩罚不可行性。

步骤2：引入“增广”思想以增强稳定性和收敛性

为了解决经典拉格朗日法的缺陷，修正/增广拉格朗日法的核心思想是：在经典拉格朗日函数的基础上，增加一个惩罚项，这个惩罚项专门针对约束违反度。

  1. 增广拉格朗日函数：其形式如下：
    L_ρ(x, λ) = f(x) + Σ_{i=1}^{m} λ_i * c_i(x) + (ρ/2) * Σ_{i=1}^{m} [c_i(x)]^2
    其中，ρ > 0 是一个惩罚参数，最后一项 (ρ/2) ||c(x)||^2 就是惩罚项。

  2. “修正”体现在哪：

    • 与罚函数法的区别：纯粹的二次罚函数法是 f(x) + (ρ/2) ||c(x)||^2。其缺点是当 ρ -> ∞ 时，子问题会变得病态（Hessian矩阵条件数很差），且只有取无穷大的惩罚参数才能得到精确解。
    • 与经典拉格朗日法的区别：增加了惩罚项 (ρ/2) ||c(x)||^2。这个增加项是“修正”的关键。它带来了两个核心好处：
      a. 强制性：当 x 不可行（c(x) 不为零）时，惩罚项会变大，迫使子问题的解倾向于满足约束。
      b. 改善凸性：惩罚项的Hessian矩阵是 ρ * ∇c(x)∇c(x)^T，这是一个半正定矩阵。它的加入可以改善增广拉格朗日函数 L_ρ(x, λ) 在 x* 附近的凸性，即使原始问题非凸，只要 ρ 足够大，L_ρ 在解附近关于 x 也可以是凸的。

步骤3：算法的基本框架与核心原理

增广拉格朗日法是一种迭代的双层算法：

  1. 外层迭代（乘子更新）：给定当前乘子估计 λ^k 和惩罚参数 ρ_k。
  2. 内层迭代（子问题求解）：近似求解关于 x 的无约束（或简单约束）子问题：
    x^{k+1} ≈ arg min_x L_{ρ_k}(x, λ^k)
    注意，这里子问题由于增加了惩罚项，通常比最小化经典拉格朗日函数更好求解，且不需要 ρ_k -> ∞。
  3. 乘子更新规则：在得到 x^{k+1} 后，按照一个非常直观且重要的公式更新拉格朗日乘子：
    λ_i^{k+1} = λ_i^k + ρ_k * c_i(x^{k+1})
    这个更新公式的原理是什么？
    假设在最优解 (x*, λ*) 处，我们有 c_i(x*) = 0。在迭代中，如果 c_i(x^{k+1}) > 0，说明约束被违反了（x 在使 c_i(x)=0 的“错误”一侧）。根据更新公式，λ_i 会增加。回顾增广拉格朗日函数 L_ρ(x, λ) = f(x) + Σ λ_i c_i(x) + (ρ/2) Σ c_i(x)^2，λ_i 增加相当于在下一轮的子问题中，加大了对于违反约束 c_i(x)=0 的代价，从而驱动下一次迭代的 x 更倾向于满足该约束。反之，如果 c_i(x) < 0，λ_i 会减小。这个过程可以看作是对“梯度”或“价格”的一种修正。

步骤4：方法的优势与关键性质

这种方法巧妙结合了拉格朗日法的精确性和罚函数法的稳定性：

  1. 有限惩罚参数：与纯罚函数法不同，增广拉格朗日法在有限的惩罚参数 ρ 下，只要子问题求解得足够精确，就能收敛到精确解。无需让 ρ_k -> ∞ 来迫使可行性，从而避免了子问题的病态数值问题。
  2. 改善的收敛性：在较温和的条件下，算法具有全局收敛性（即从任意起始点开始都能收敛）和局部超线性收敛速率（当接近解时，收敛非常快）。
  3. 灵活性：子问题是一个无约束（或边界约束）优化问题，可以使用各种成熟的算法求解，如拟牛顿法、共轭梯度法等。这为大规模问题求解提供了可能。

步骤5：扩展到不等式约束与实际问题

  1. 处理不等式约束：对于不等式约束 c_i(x) ≤ 0，标准的处理方式是引入松弛变量 s_i ≥ 0，将其转化为等式约束 c_i(x) + s_i = 0，并对 s_i ≥ 0 进行处理。更高效的方法是直接定义对应的增广拉格朗日函数，其乘子更新规则变为：
    λ_i^{k+1} = max(0, λ_i^k + ρ_k * c_i(x^{k+1}))
    这确保了乘子的非负性（对应不等式约束的乘子符号要求）。

  2. 与交替方向乘子法的联系：增广拉格朗日法是许多现代分布式优化算法的基础。当目标函数可分离时（如 f(x) = f1(x1) + f2(x2)，且约束为 Ax + Bz = c），对其应用增广拉格朗日法，并对变量 x 和 z 交替最小化，就得到了著名的交替方向乘子法，它是大规模分布式计算的核心算法之一。

总结：
非线性规划中的修正拉格朗日法（增广拉格朗日法） 是一种将拉格朗日乘子法与二次罚函数法有机结合的精妙算法。它通过在原拉格朗日函数中增加一个约束违反度的二次惩罚项，构造出性质更好的增广拉格朗日函数。算法通过交替进行“最小化增广拉格朗日函数”和“根据约束违反度更新乘子”两步来迭代。其核心优势在于，使用有限的惩罚参数即可收敛到问题的精确解，既克服了纯罚函数法子问题病态和需要无穷大惩罚参数的缺点，又比经典拉格朗日法更稳定、更具强制性，是现代处理非线性约束优化问题的基石性方法。

非线性规划中的修正拉格朗日法（Augmented Lagrangian Method） 好的，我们开始讲解“非线性规划中的修正拉格朗日法”，也被更广泛地称为“增广拉格朗日法”。我将从最基础的约束优化问题开始，循序渐进地展开，确保每一步都清晰易懂。 步骤1：从基础约束优化问题与经典拉格朗日法讲起 我们考虑一个标准的非线性规划问题： 最小化 f(x) 满足 c_i(x) = 0, i = 1, …, m （等式约束） 这里， x ∈ R^n 是决策变量， f: R^n -> R 是目标函数， c_i: R^n -> R 是约束函数。 经典拉格朗日函数 ：对于此类问题，我们引入 拉格朗日乘子 λ_ i ，构造经典拉格朗日函数： L(x, λ) = f(x) + Σ_{i=1}^{m} λ_i * c_i(x) 。 一阶最优性条件 ：在满足一定约束规格（如LICQ）的最优点 x* 处，存在乘子 λ* 使得梯度为零： ∇_x L(x*, λ*) = 0 且 c_i(x*) = 0 。这组方程就是著名的KKT条件（对于只有等式约束的情况）。 经典法的局限性 ：理论上，我们可以通过求解方程组 ∇_x L(x, λ) = 0 和 c(x)=0 来寻找最优解。但这通常是一个非线性方程组，求解困难。更重要的是， 经典拉格朗日函数 L(x, λ) 关于 x 在鞍点 (x*, λ*) 处可能不是凸的 ，这意味着直接最小化 L(x, λ) （对于固定的λ）可能不会导向可行解，甚至无界。它缺乏“强制性”，即当 x 远离可行域时， L(x, λ) 的值不会显著增大以惩罚不可行性。 步骤2：引入“增广”思想以增强稳定性和收敛性 为了解决经典拉格朗日法的缺陷， 修正/增广拉格朗日法 的核心思想是：在经典拉格朗日函数的基础上，增加一个 惩罚项 ，这个惩罚项专门针对约束违反度。 增广拉格朗日函数 ：其形式如下： L_ρ(x, λ) = f(x) + Σ_{i=1}^{m} λ_i * c_i(x) + (ρ/2) * Σ_{i=1}^{m} [c_i(x)]^2 其中， ρ > 0 是一个惩罚参数，最后一项 (ρ/2) ||c(x)||^2 就是惩罚项。 “修正”体现在哪 ： 与罚函数法的区别 ：纯粹的二次罚函数法是 f(x) + (ρ/2) ||c(x)||^2 。其缺点是当 ρ -> ∞ 时，子问题会变得病态（Hessian矩阵条件数很差），且只有取无穷大的惩罚参数才能得到精确解。 与经典拉格朗日法的区别 ：增加了惩罚项 (ρ/2) ||c(x)||^2 。这个增加项是“修正”的关键。它带来了两个核心好处： a. 强制性 ：当 x 不可行（ c(x) 不为零）时，惩罚项会变大，迫使子问题的解倾向于满足约束。 b. 改善凸性 ：惩罚项的Hessian矩阵是 ρ * ∇c(x)∇c(x)^T ，这是一个半正定矩阵。它的加入可以改善增广拉格朗日函数 L_ρ(x, λ) 在 x* 附近的凸性，即使原始问题非凸，只要 ρ 足够大， L_ρ 在解附近关于 x 也可以是凸的。 步骤3：算法的基本框架与核心原理 增广拉格朗日法是一种迭代的双层算法： 外层迭代（乘子更新） ：给定当前乘子估计 λ^k 和惩罚参数 ρ_k 。 内层迭代（子问题求解） ： 近似 求解关于 x 的无约束（或简单约束）子问题： x^{k+1} ≈ arg min_x L_{ρ_k}(x, λ^k) 注意，这里子问题由于增加了惩罚项，通常比最小化经典拉格朗日函数更好求解，且不需要 ρ_k -> ∞ 。 乘子更新规则 ：在得到 x^{k+1} 后，按照一个非常直观且重要的公式更新拉格朗日乘子： λ_i^{k+1} = λ_i^k + ρ_k * c_i(x^{k+1}) 这个更新公式的原理是什么？ 假设在最优解 (x*, λ*) 处，我们有 c_i(x*) = 0 。在迭代中，如果 c_i(x^{k+1}) > 0 ，说明约束被违反了（ x 在使 c_i(x)=0 的“错误”一侧）。根据更新公式， λ_i 会增加。回顾增广拉格朗日函数 L_ρ(x, λ) = f(x) + Σ λ_i c_i(x) + (ρ/2) Σ c_i(x)^2 ， λ_i 增加相当于在下一轮的子问题中， 加大了对于违反约束 c_i(x)=0 的代价 ，从而驱动下一次迭代的 x 更倾向于满足该约束。反之，如果 c_i(x) < 0 ， λ_i 会减小。这个过程可以看作是对“梯度”或“价格”的一种修正。 步骤4：方法的优势与关键性质 这种方法巧妙结合了 拉格朗日法的精确性 和 罚函数法的稳定性 ： 有限惩罚参数 ：与纯罚函数法不同，增广拉格朗日法在 有限的惩罚参数 ρ 下，只要子问题求解得足够精确，就能收敛到精确解。无需让 ρ_k -> ∞ 来迫使可行性，从而避免了子问题的病态数值问题。 改善的收敛性 ：在较温和的条件下，算法具有全局收敛性（即从任意起始点开始都能收敛）和局部超线性收敛速率（当接近解时，收敛非常快）。 灵活性 ：子问题是一个无约束（或边界约束）优化问题，可以使用各种成熟的算法求解，如拟牛顿法、共轭梯度法等。这为大规模问题求解提供了可能。 步骤5：扩展到不等式约束与实际问题 处理不等式约束 ：对于不等式约束 c_i(x) ≤ 0 ，标准的处理方式是引入松弛变量 s_i ≥ 0 ，将其转化为等式约束 c_i(x) + s_i = 0 ，并对 s_i ≥ 0 进行处理。更高效的方法是直接定义对应的增广拉格朗日函数，其乘子更新规则变为： λ_i^{k+1} = max(0, λ_i^k + ρ_k * c_i(x^{k+1})) 这确保了乘子的非负性（对应不等式约束的乘子符号要求）。 与交替方向乘子法的联系 ：增广拉格朗日法是许多现代分布式优化算法的基础。当目标函数可分离时（如 f(x) = f1(x1) + f2(x2) ，且约束为 Ax + Bz = c ），对其应用增广拉格朗日法，并对变量 x 和 z 交替最小化，就得到了著名的 交替方向乘子法 ，它是大规模分布式计算的核心算法之一。 总结 ： 非线性规划中的 修正拉格朗日法（增广拉格朗日法） 是一种将拉格朗日乘子法与二次罚函数法有机结合的精妙算法。它通过在原拉格朗日函数中增加一个约束违反度的二次惩罚项，构造出性质更好的增广拉格朗日函数。算法通过交替进行“ 最小化增广拉格朗日函数 ”和“ 根据约束违反度更新乘子 ”两步来迭代。其核心优势在于， 使用有限的惩罚参数即可收敛到问题的精确解 ，既克服了纯罚函数法子问题病态和需要无穷大惩罚参数的缺点，又比经典拉格朗日法更稳定、更具强制性，是现代处理非线性约束优化问题的基石性方法。