增广拉格朗日法
字数 3891 2025-11-02 00:38:02

增广拉格朗日法

增广拉格朗日法是一种求解约束优化问题的数值算法。它结合了拉格朗日乘子法的思想（通过引入乘子将约束问题转化为无约束问题）和罚函数法的思想（通过在目标函数中添加约束违反的惩罚项来迫使迭代点趋向可行域），旨在克服单纯罚函数法可能遇到的数值困难（如病态条件）以及拉格朗日乘子法在无约束子问题求解上的不稳定性。

第一步：问题背景与动机

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

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

其中，\(f, h_i: \mathbb{R}^n \to \mathbb{R}\) 是连续可微函数。

  • 拉格朗日函数为：\(L(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i h_i(\mathbf{x})\)。在理想条件下，原问题的局部最优解 \(\mathbf{x}^*\) 对应某个乘子 \(\boldsymbol{\lambda}^*\)，使得 \((\mathbf{x}^*, \boldsymbol{\lambda}^*)\) 是 \(L\) 的鞍点。然而，直接最小化 \(L(\mathbf{x}, \boldsymbol{\lambda})\) 关于 \(\mathbf{x}\)（对于固定的 \(\boldsymbol{\lambda}\)）可能无法得到一个有意义的解，因为 \(L\) 关于 \(\mathbf{x}\) 可能无下界。
  • 二次罚函数为：\(P(\mathbf{x}; \mu) = f(\mathbf{x}) + \frac{\mu}{2} \sum_{i=1}^{m} [h_i(\mathbf{x})]^2\)，其中 \(\mu > 0\) 是罚参数。当 \(\mu \to \infty\) 时，罚问题的最优解会逼近原问题的可行解。但为了精确满足约束，\(\mu\) 必须取得非常大，这会导致罚函数 \(P\) 的Hessian矩阵条件数很差，使得无约束优化子问题数值上难以求解。

增广拉格朗日法的核心动机是：能否构造一个函数，使得在乘子的某个估计值附近，该函数关于 \(\mathbf{x}\) 的最小化问题能够在不要求罚参数 \(\mu\) 趋于无穷大的情况下，就产生原问题的精确解？

第二步：增广拉格朗日函数的定义

针对上述等式约束问题，增广拉格朗日函数（也称为乘子罚函数）定义为：

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

其中：

  • \(\mathbf{x}\) 是决策变量。
  • \(\boldsymbol{\lambda} = (\lambda_1, \dots, \lambda_m)^T\) 是拉格朗日乘子向量（是算法的变量，而不仅仅是常数）。
  • \(\mu > 0\) 是罚参数。

这个函数可以看作是标准拉格朗日函数 \(L(\mathbf{x}, \boldsymbol{\lambda})\) 加上一个约束违反的二次惩罚项 \(\frac{\mu}{2} \sum_{i} [h_i(\mathbf{x})]^2\)。

第三步：算法的关键思想与步骤

增广拉格朗日法是一种迭代算法，它交替地更新变量 \(\mathbf{x}\) 和乘子 \(\boldsymbol{\lambda}\)。

  1. 初始化：选择初始乘子估计 \(\boldsymbol{\lambda}^0\)、初始罚参数 \(\mu^0 > 0\)、放大因子 \(\rho > 1\)（用于在需要时增大 \(\mu\)）、以及收敛容差 \(\epsilon > 0\)。设 \(k = 0\)。

  2. 无约束子问题求解（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) \]

这个子问题比单纯的二次罚函数子问题数值性质更好，因为当乘子估计 \(\boldsymbol{\lambda}^k\) 接近最优乘子 \(\boldsymbol{\lambda}^*\) 时，即使 \(\mu^k\) 不是特别大，该问题的最优解也接近原问题的最优解 \(\mathbf{x}^*\)。

  1. 乘子更新（λ-更新）：利用新得到的点 \(\mathbf{x}^{k+1}\) 来更新乘子。更新公式为：

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

这个更新公式具有直观的解释：如果在第 \(k+1\) 次迭代中，约束 \(h_i(\mathbf{x}) = 0\) 没有被精确满足（即 \(h_i(\mathbf{x}^{k+1}) \neq 0\)），那么我们就在当前乘子估计 \(\lambda_i^k\) 的基础上，沿着约束违反的方向（由 \(h_i(\mathbf{x}^{k+1})\) 的符号决定）进行一个修正，修正的步长由罚参数 \(\mu^k\) 控制。这个更新规则可以从对偶上升的角度或一阶最优性条件推导出来。

  1. 收敛性检查与罚参数更新：检查是否满足收敛条件，例如 \(\| \mathbf{h}(\mathbf{x}^{k+1}) \| < \epsilon\)。如果满足，则算法终止，\((\mathbf{x}^{k+1}, \boldsymbol{\lambda}^{k+1})\) 作为近似解。如果不满足，且约束违反度下降不够明显，可以选择增大罚参数以施加更强的惩罚：\(\mu^{k+1} = \rho \mu^k\)（其中 \(\rho > 1\)）。否则，保持 \(\mu^{k+1} = \mu^k\)。然后令 \(k = k+1\)，返回步骤2。

第四步：处理不等式约束

对于包含不等式约束的问题：

\[\begin{aligned} \min_{\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_j(\mathbf{x}) \le 0, \quad j = 1, \dots, p \end{aligned} \]

常用的方法是通过引入松弛变量将其转化为等式约束。定义增广拉格朗日函数为：

\[\mathcal{L}_{A}(\mathbf{x}, \boldsymbol{\mu}; \mu) = f(\mathbf{x}) + \frac{\mu}{2} \sum_{j=1}^{p} \left( \max\left(0, \mu_j / \mu + g_j(\mathbf{x}) \right) \right)^2 - \frac{1}{2\mu} \sum_{j=1}^{p} (\mu_j)^2 \]

或者更常用且等价的简化形式是，在乘子更新步骤中采用如下规则：

\[\mu_j^{k+1} = \max\left(0, \mu_j^k + \mu^k g_j(\mathbf{x}^{k+1}) \right), \quad j = 1, \dots, p \]

这确保了乘子始终非负（与不等式约束的KKT条件一致）。

第五步：方法的特点与优势

  • 缓解病态问题：与纯罚函数法相比，由于乘子的存在，即使罚参数 \(\mu\) 取一个适中的固定值，算法也可能收敛到精确解，从而避免了Hessian矩阵条件数随 \(\mu\) 增大而急剧恶化的问题。
  • 收敛性：在适当的条件下（如 \(f\) 和约束函数光滑，且满足某些约束品性），该方法具有局部超线性或全局收敛性。
  • 实用性：该方法构成了许多现代约束优化软件包（如LANCELOT, ALGENCAN）的基础。其思想也被推广用于构造一些更复杂的算法，如交替方向乘子法（ADMM），后者特别适用于分布式优化和大规模问题。

总结来说，增广拉格朗日法通过巧妙地将拉格朗日乘子和二次惩罚项结合，提供了一个在数值稳定性和收敛速度之间取得良好平衡的框架，用于求解带有等式和不等式约束的非线性优化问题。

增广拉格朗日法 增广拉格朗日法是一种求解约束优化问题的数值算法。它结合了拉格朗日乘子法的思想（通过引入乘子将约束问题转化为无约束问题）和罚函数法的思想（通过在目标函数中添加约束违反的惩罚项来迫使迭代点趋向可行域），旨在克服单纯罚函数法可能遇到的数值困难（如病态条件）以及拉格朗日乘子法在无约束子问题求解上的不稳定性。 第一步：问题背景与动机 考虑如下等式约束优化问题： \[ \begin{aligned} \min_ {\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & h_ i(\mathbf{x}) = 0, \quad i = 1, \dots, m \end{aligned} \] 其中，\( f, h_ i: \mathbb{R}^n \to \mathbb{R} \) 是连续可微函数。 拉格朗日函数 为：\( L(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_ {i=1}^{m} \lambda_ i h_ i(\mathbf{x}) \)。在理想条件下，原问题的局部最优解 \( \mathbf{x}^* \) 对应某个乘子 \( \boldsymbol{\lambda}^* \)，使得 \( (\mathbf{x}^ , \boldsymbol{\lambda}^ ) \) 是 \( L \) 的鞍点。然而，直接最小化 \( L(\mathbf{x}, \boldsymbol{\lambda}) \) 关于 \( \mathbf{x} \)（对于固定的 \( \boldsymbol{\lambda} \)）可能无法得到一个有意义的解，因为 \( L \) 关于 \( \mathbf{x} \) 可能无下界。 二次罚函数 为：\( P(\mathbf{x}; \mu) = f(\mathbf{x}) + \frac{\mu}{2} \sum_ {i=1}^{m} [ h_ i(\mathbf{x}) ]^2 \)，其中 \( \mu > 0 \) 是罚参数。当 \( \mu \to \infty \) 时，罚问题的最优解会逼近原问题的可行解。但为了精确满足约束，\( \mu \) 必须取得非常大，这会导致罚函数 \( P \) 的Hessian矩阵条件数很差，使得无约束优化子问题数值上难以求解。 增广拉格朗日法的核心动机是： 能否构造一个函数，使得在乘子的某个估计值附近，该函数关于 \( \mathbf{x} \) 的最小化问题能够在不要求罚参数 \( \mu \) 趋于无穷大的情况下，就产生原问题的精确解？ 第二步：增广拉格朗日函数的定义 针对上述等式约束问题，增广拉格朗日函数（也称为乘子罚函数）定义为： \[ \mathcal{L} {A}(\mathbf{x}, \boldsymbol{\lambda}; \mu) = f(\mathbf{x}) + \sum {i=1}^{m} \lambda_ i h_ i(\mathbf{x}) + \frac{\mu}{2} \sum_ {i=1}^{m} [ h_ i(\mathbf{x}) ]^2 \] 其中： \( \mathbf{x} \) 是决策变量。 \( \boldsymbol{\lambda} = (\lambda_ 1, \dots, \lambda_ m)^T \) 是拉格朗日乘子向量（是算法的变量，而不仅仅是常数）。 \( \mu > 0 \) 是罚参数。 这个函数可以看作是标准拉格朗日函数 \( L(\mathbf{x}, \boldsymbol{\lambda}) \) 加上一个约束违反的二次惩罚项 \( \frac{\mu}{2} \sum_ {i} [ h_ i(\mathbf{x}) ]^2 \)。 第三步：算法的关键思想与步骤 增广拉格朗日法是一种迭代算法，它交替地更新变量 \( \mathbf{x} \) 和乘子 \( \boldsymbol{\lambda} \)。 初始化 ：选择初始乘子估计 \( \boldsymbol{\lambda}^0 \)、初始罚参数 \( \mu^0 > 0 \)、放大因子 \( \rho > 1 \)（用于在需要时增大 \( \mu \)）、以及收敛容差 \( \epsilon > 0 \)。设 \( k = 0 \)。 无约束子问题求解（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) \] 这个子问题比单纯的二次罚函数子问题数值性质更好，因为当乘子估计 \( \boldsymbol{\lambda}^k \) 接近最优乘子 \( \boldsymbol{\lambda}^* \) 时，即使 \( \mu^k \) 不是特别大，该问题的最优解也接近原问题的最优解 \( \mathbf{x}^* \)。 乘子更新（λ-更新） ：利用新得到的点 \( \mathbf{x}^{k+1} \) 来更新乘子。更新公式为： \[ \lambda_ i^{k+1} = \lambda_ i^k + \mu^k h_ i(\mathbf{x}^{k+1}), \quad i = 1, \dots, m \] 这个更新公式具有直观的解释：如果在第 \( k+1 \) 次迭代中，约束 \( h_ i(\mathbf{x}) = 0 \) 没有被精确满足（即 \( h_ i(\mathbf{x}^{k+1}) \neq 0 \)），那么我们就在当前乘子估计 \( \lambda_ i^k \) 的基础上，沿着约束违反的方向（由 \( h_ i(\mathbf{x}^{k+1}) \) 的符号决定）进行一个修正，修正的步长由罚参数 \( \mu^k \) 控制。这个更新规则可以从对偶上升的角度或一阶最优性条件推导出来。 收敛性检查与罚参数更新 ：检查是否满足收敛条件，例如 \( \| \mathbf{h}(\mathbf{x}^{k+1}) \| < \epsilon \)。如果满足，则算法终止，\( (\mathbf{x}^{k+1}, \boldsymbol{\lambda}^{k+1}) \) 作为近似解。如果不满足，且约束违反度下降不够明显，可以选择增大罚参数以施加更强的惩罚：\( \mu^{k+1} = \rho \mu^k \)（其中 \( \rho > 1 \)）。否则，保持 \( \mu^{k+1} = \mu^k \)。然后令 \( k = k+1 \)，返回步骤2。 第四步：处理不等式约束 对于包含不等式约束的问题： \[ \begin{aligned} \min_ {\mathbf{x}} \quad & f(\mathbf{x}) \\ \text{s.t.} \quad & g_ j(\mathbf{x}) \le 0, \quad j = 1, \dots, p \end{aligned} \] 常用的方法是通过引入松弛变量将其转化为等式约束。定义增广拉格朗日函数为： \[ \mathcal{L} {A}(\mathbf{x}, \boldsymbol{\mu}; \mu) = f(\mathbf{x}) + \frac{\mu}{2} \sum {j=1}^{p} \left( \max\left(0, \mu_ j / \mu + g_ j(\mathbf{x}) \right) \right)^2 - \frac{1}{2\mu} \sum_ {j=1}^{p} (\mu_ j)^2 \] 或者更常用且等价的简化形式是，在乘子更新步骤中采用如下规则： \[ \mu_ j^{k+1} = \max\left(0, \mu_ j^k + \mu^k g_ j(\mathbf{x}^{k+1}) \right), \quad j = 1, \dots, p \] 这确保了乘子始终非负（与不等式约束的KKT条件一致）。 第五步：方法的特点与优势 缓解病态问题 ：与纯罚函数法相比，由于乘子的存在，即使罚参数 \( \mu \) 取一个适中的固定值，算法也可能收敛到精确解，从而避免了Hessian矩阵条件数随 \( \mu \) 增大而急剧恶化的问题。 收敛性 ：在适当的条件下（如 \( f \) 和约束函数光滑，且满足某些约束品性），该方法具有局部超线性或全局收敛性。 实用性 ：该方法构成了许多现代约束优化软件包（如 LANCELOT , ALGENCAN ）的基础。其思想也被推广用于构造一些更复杂的算法，如交替方向乘子法（ADMM），后者特别适用于分布式优化和大规模问题。 总结来说，增广拉格朗日法通过巧妙地将拉格朗日乘子和二次惩罚项结合，提供了一个在数值稳定性和收敛速度之间取得良好平衡的框架，用于求解带有等式和不等式约束的非线性优化问题。