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

好的，接下来我将为你讲解一个尚未覆盖的运筹学重要词条。

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

第一步：理解核心思想
增广拉格朗日法，又称乘子法，是一种将约束优化问题转化为一系列相对容易求解的无约束优化问题的迭代算法。它是在标准拉格朗日函数的基础上，增加了一个“惩罚项”，从而克服了传统罚函数法（如二次罚函数法）可能遇到的数值困难（如病态问题需要惩罚因子趋于无穷大）。

核心目标：我们希望求解一个带等式约束的非线性规划问题：

\[\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & h_i(\mathbf{x}) = 0, \quad i = 1, \ldots, m \end{aligned} \]

其中，\(f\) 和 \(h_i\) 是连续可微函数。

第二步：从拉格朗日函数到增广拉格朗日函数

  1. 标准拉格朗日函数为： \(L(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \lambda_i h_i(\mathbf{x})\)。
  • 在最优解 \(\mathbf{x}^*\) 处，存在拉格朗日乘子向量 \(\boldsymbol{\lambda}^*\)，使得 \(\nabla_{\mathbf{x}} L(\mathbf{x}^*, \boldsymbol{\lambda}^*) = 0\) 且 \(h_i(\mathbf{x}^*) = 0\)。
  • 但直接最小化 \(L(\mathbf{x}, \boldsymbol{\lambda})\) 对 \(\mathbf{x}\) 无法保证收敛到约束解，因为它关于 \(\mathbf{x}\) 可能不是“足够凸”的。
  1. 增广拉格朗日函数 在标准形式基础上增加了约束的二次惩罚项：

\[ \mathcal{L}_c(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \lambda_i h_i(\mathbf{x}) + \frac{c}{2} \sum_{i=1}^m (h_i(\mathbf{x}))^2 \]

  • 这里，\(c > 0\) 是一个惩罚参数。
    • 这个函数可以看作标准拉格朗日函数（利用了最优性的一阶信息）和二次罚函数（强制满足约束）的混合体。

第三步：方法如何运作？
算法从一个初始的乘子估计 \(\boldsymbol{\lambda}^0\) 和一个固定的惩罚参数 \(c\) 开始，然后迭代以下两步：

  1. 子问题求解（关于 \(\mathbf{x}\) 的无约束优化）：
    在第 \(k\) 次迭代，固定当前的乘子 \(\boldsymbol{\lambda}^k\) 和参数 \(c^k\)，求解：

\[ \mathbf{x}^{k+1} = \arg \min_{\mathbf{x}} \mathcal{L}_{c^k}(\mathbf{x}, \boldsymbol{\lambda}^k) \]

这是一个无约束优化问题，可以用牛顿法、拟牛顿法、梯度下降等方法求解。由于惩罚项 \(\frac{c}{2} \sum h_i^2\) 的存在，即使惩罚参数 \(c\) 是有限的（不必趋于无穷大），这个子问题在最优解附近也通常是良态的、凸性良好的。

  1. 乘子更新（关于 \(\boldsymbol{\lambda}\) 的更新）：
    在得到 \(\mathbf{x}^{k+1}\) 后，我们更新拉格朗日乘子：

\[ \lambda_i^{k+1} = \lambda_i^k + c^k h_i(\mathbf{x}^{k+1}), \quad i = 1, \ldots, m \]

  • 这个更新规则的直观解释：在标准最优性条件（KKT条件）中，对等式约束有 \(h_i(\mathbf{x}^*) = 0\)。如果当前点 \(\mathbf{x}^{k+1}\) 不满足约束（即 \(h_i(\mathbf{x}^{k+1}) \neq 0\)），那么“违反”的程度 \(h_i(\mathbf{x}^{k+1})\) 应该反映到乘子的调整上。如果约束被违反（\(h_i > 0\)），乘子 \(\lambda_i\) 会增加，从而在下次迭代的增广拉格朗日函数中，对目标函数 \(f\) 施加更大的“压力”来满足该约束。
  • 惩罚参数 \(c^k\) 可以随着迭代缓慢增加，以加速收敛，但不像传统罚函数法那样需要趋于无穷大。

第四步：几何与收敛性解释

  • 双重角色：增广项 \(\frac{c}{2} \sum h_i^2\) 起到了两个关键作用：
    1. 惩罚作用：推动解向可行域靠近。
  1. 凸化作用：即使原问题非凸，在局部最优解附近，足够大的 \(c\) 也能使 \(\mathcal{L}_c(\mathbf{x}, \boldsymbol{\lambda}^*)\) 关于 \(\mathbf{x}\) 在该点处是局部凸的，这大大方便了子问题的求解。
  • 收敛性：在一定条件下（如 \(f\) 和 \(h_i\) 连续可微，且满足某些约束规格），该方法具有全局收敛性（即从任意初始点开始，算法产生的点列的极限点满足一阶最优性条件）和局部超线性收敛性（当接近最优解时，收敛速度非常快）。

第五步：处理不等式约束
对于带不等式约束的问题 \(g_j(\mathbf{x}) \le 0\)：

  1. 引入松弛变量，将其转化为等式约束：\(g_j(\mathbf{x}) + s_j^2 = 0\)，其中 \(s_j\) 是新的变量。
  2. 构造关于 \((\mathbf{x}, \mathbf{s})\) 的增广拉格朗日函数，并迭代求解。在子问题中，可以先关于 \(s_j\) 解析求解，得到一种简化形式。
  3. 更常用的简化更新：在每次迭代求解子问题得到 \(\mathbf{x}^{k+1}\) 后，乘子 \(\mu_j\)（对应不等式约束）按下式更新：

\[ \mu_j^{k+1} = \max(0, \mu_j^k + c^k g_j(\mathbf{x}^{k+1})) \]

这里 \(\max(0, \cdot)\) 确保了乘子的非负性（这是由不等式约束的KKT条件决定的）。

总结：
增广拉格朗日法巧妙地将拉格朗日乘子的对偶更新和惩罚函数的强制可行性结合起来。与经典罚函数法相比，它允许在有限大小的惩罚参数下工作，从而避免了病态数值问题。与标准拉格朗日法相比，增加的惩罚项提供了“曲率”，使子问题更容易求解。因此，它是求解中大规模非线性规划问题，特别是带大量等式约束或简单不等式约束问题的强大而实用的工具。

好的，接下来我将为你讲解一个尚未覆盖的运筹学重要词条。 非线性规划中的增广拉格朗日法（Augmented Lagrangian Method in Nonlinear Programming） 第一步：理解核心思想 增广拉格朗日法 ，又称乘子法，是一种将约束优化问题转化为一系列相对容易求解的无约束优化问题的迭代算法。它是在标准 拉格朗日函数 的基础上，增加了一个“惩罚项”，从而克服了传统罚函数法（如二次罚函数法）可能遇到的数值困难（如病态问题需要惩罚因子趋于无穷大）。 核心目标 ：我们希望求解一个带等式约束的非线性规划问题： \[ \begin{aligned} \min_ {\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & h_ i(\mathbf{x}) = 0, \quad i = 1, \ldots, m \end{aligned} \] 其中，\( f \) 和 \( h_ i \) 是连续可微函数。 第二步：从拉格朗日函数到增广拉格朗日函数 标准拉格朗日函数 为： \( L(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_ {i=1}^m \lambda_ i h_ i(\mathbf{x}) \)。 在最优解 \( \mathbf{x}^* \) 处，存在拉格朗日乘子向量 \( \boldsymbol{\lambda}^* \)，使得 \( \nabla_ {\mathbf{x}} L(\mathbf{x}^ , \boldsymbol{\lambda}^ ) = 0 \) 且 \( h_ i(\mathbf{x}^* ) = 0 \)。 但直接最小化 \( L(\mathbf{x}, \boldsymbol{\lambda}) \) 对 \( \mathbf{x} \) 无法保证收敛到约束解，因为它关于 \( \mathbf{x} \) 可能不是“足够凸”的。 增广拉格朗日函数 在标准形式基础上增加了约束的二次惩罚项： \[ \mathcal{L} c(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum {i=1}^m \lambda_ i h_ i(\mathbf{x}) + \frac{c}{2} \sum_ {i=1}^m (h_ i(\mathbf{x}))^2 \] 这里，\( c > 0 \) 是一个惩罚参数。 这个函数可以看作标准拉格朗日函数（利用了最优性的一阶信息）和二次罚函数（强制满足约束）的混合体。 第三步：方法如何运作？ 算法从一个初始的乘子估计 \( \boldsymbol{\lambda}^0 \) 和一个固定的惩罚参数 \( c \) 开始，然后迭代以下两步： 子问题求解（关于 \( \mathbf{x} \) 的无约束优化） ： 在第 \( k \) 次迭代，固定当前的乘子 \( \boldsymbol{\lambda}^k \) 和参数 \( c^k \)，求解： \[ \mathbf{x}^{k+1} = \arg \min_ {\mathbf{x}} \mathcal{L}_ {c^k}(\mathbf{x}, \boldsymbol{\lambda}^k) \] 这是一个 无约束优化问题 ，可以用牛顿法、拟牛顿法、梯度下降等方法求解。由于惩罚项 \( \frac{c}{2} \sum h_ i^2 \) 的存在，即使惩罚参数 \( c \) 是有限的（不必趋于无穷大），这个子问题在最优解附近也通常是良态的、凸性良好的。 乘子更新（关于 \( \boldsymbol{\lambda} \) 的更新） ： 在得到 \( \mathbf{x}^{k+1} \) 后，我们更新拉格朗日乘子： \[ \lambda_ i^{k+1} = \lambda_ i^k + c^k h_ i(\mathbf{x}^{k+1}), \quad i = 1, \ldots, m \] 这个更新规则的直观解释 ：在标准最优性条件（KKT条件）中，对等式约束有 \( h_ i(\mathbf{x}^* ) = 0 \)。如果当前点 \( \mathbf{x}^{k+1} \) 不满足约束（即 \( h_ i(\mathbf{x}^{k+1}) \neq 0 \)），那么“违反”的程度 \( h_ i(\mathbf{x}^{k+1}) \) 应该反映到乘子的调整上。如果约束被违反（\( h_ i > 0 \)），乘子 \( \lambda_ i \) 会增加，从而在下次迭代的增广拉格朗日函数中，对目标函数 \( f \) 施加更大的“压力”来满足该约束。 惩罚参数 \( c^k \) 可以随着迭代缓慢增加，以加速收敛，但不像传统罚函数法那样需要趋于无穷大。 第四步：几何与收敛性解释 双重角色 ：增广项 \( \frac{c}{2} \sum h_ i^2 \) 起到了两个关键作用： 惩罚作用 ：推动解向可行域靠近。 凸化作用 ：即使原问题非凸，在局部最优解附近，足够大的 \( c \) 也能使 \( \mathcal{L}_ c(\mathbf{x}, \boldsymbol{\lambda}^* ) \) 关于 \( \mathbf{x} \) 在该点处是局部凸的，这大大方便了子问题的求解。 收敛性 ：在一定条件下（如 \( f \) 和 \( h_ i \) 连续可微，且满足某些约束规格），该方法具有 全局收敛性 （即从任意初始点开始，算法产生的点列的极限点满足一阶最优性条件）和 局部超线性收敛性 （当接近最优解时，收敛速度非常快）。 第五步：处理不等式约束 对于带不等式约束的问题 \( g_ j(\mathbf{x}) \le 0 \)： 引入松弛变量 ，将其转化为等式约束：\( g_ j(\mathbf{x}) + s_ j^2 = 0 \)，其中 \( s_ j \) 是新的变量。 构造关于 \( (\mathbf{x}, \mathbf{s}) \) 的增广拉格朗日函数，并迭代求解。在子问题中，可以先关于 \( s_ j \) 解析求解，得到一种简化形式。 更常用的简化更新 ：在每次迭代求解子问题得到 \( \mathbf{x}^{k+1} \) 后，乘子 \( \mu_ j \)（对应不等式约束）按下式更新： \[ \mu_ j^{k+1} = \max(0, \mu_ j^k + c^k g_ j(\mathbf{x}^{k+1})) \] 这里 \( \max(0, \cdot) \) 确保了乘子的非负性（这是由不等式约束的KKT条件决定的）。 总结 ： 增广拉格朗日法 巧妙地将 拉格朗日乘子的对偶更新 和 惩罚函数的强制可行性 结合起来。与经典罚函数法相比，它允许在 有限大小的惩罚参数 下工作，从而避免了病态数值问题。与标准拉格朗日法相比，增加的惩罚项提供了“曲率”，使子问题更容易求解。因此，它是求解中大规模非线性规划问题，特别是带大量等式约束或简单不等式约束问题的强大而实用的工具。