非线性规划中的增广拉格朗日函数法

字数 3005 2025-12-05 22:24:24

非线性规划中的增广拉格朗日函数法

首先，我们从一个常见的约束优化问题出发。假设我们需要最小化一个函数 \(f(x)\)，但变量 \(x\) 必须满足一些等式约束 \(h_i(x) = 0\)。这个问题可以写成：

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

第一步：回顾拉格朗日函数
为了解决这个带等式约束的问题，我们通常会引入拉格朗日乘子 \(\lambda_i\)，构造拉格朗日函数：

\[L(x, \lambda) = f(x) + \sum_{i=1}^{m} \lambda_i h_i(x)。 \]

在最优解 \(x^*\) 处，如果约束规格（如线性无关约束规范LICQ）满足，则存在乘子 \(\lambda^*\) 使得梯度 \(\nabla_x L(x^*, \lambda^*) = 0\)。然而，直接求解这个方程组（即一阶KKT条件）有时并不稳定，尤其是当约束非线性程度高时，数值求解可能困难。

第二步：增广拉格朗日函数的引入
为了改进求解的稳定性，我们引入一个“增广”的拉格朗日函数。它在标准拉格朗日函数基础上增加了一个惩罚项，形式如下：

\[\mathcal{L}_A(x, \lambda; \rho) = f(x) + \sum_{i=1}^{m} \lambda_i h_i(x) + \frac{\rho}{2} \sum_{i=1}^{m} h_i(x)^2。 \]

这里，\(\rho > 0\) 是一个惩罚参数，\(\frac{\rho}{2} \sum h_i(x)^2\) 是惩罚项。注意，这个函数仍然保留了乘子 \(\lambda\)。与标准的二次罚函数法（仅有惩罚项，没有乘子）相比，增广拉格朗日函数通过引入乘子，允许我们在有限的 \(\rho\) 下就能找到精确解，而不仅仅是近似满足约束。

第三步：方法的直观理解与优势
为什么加入惩罚项和乘子会更有效？我们可以从两个角度理解：

惩罚项的作用：当约束不满足时（即 \(h_i(x) \neq 0\)），惩罚项 \(\frac{\rho}{2} h_i(x)^2\) 会产生一个很大的代价，迫使迭代点向可行域靠近。这使得函数 \(\mathcal{L}_A\) 关于 \(x\) 的最小化问题更容易求解（因为其 Hessian 通常更好条件化）。
乘子的作用：乘子 \(\lambda\) 提供了一个“修正”机制。如果我们有一个当前乘子估计 \(\lambda^k\)，并最小化 \(\mathcal{L}_A(x, \lambda^k; \rho)\) 得到 \(x^k\)，那么约束违反度 \(h_i(x^k)\) 通常不为零。此时，我们可以更新乘子：\(\lambda_i^{k+1} = \lambda_i^k + \rho h_i(x^k)\)。这个更新公式来源于对偶上升或近端点的思想，它使得乘子能更准确地估计最优乘子 \(\lambda^*\)，从而在下次迭代中引导解更好地满足约束。

第四步：算法的具体步骤（乘子法）
对于仅含等式约束的问题，基本的乘子法（也称为增广拉格朗日法）迭代流程如下：

初始化：选择初始乘子 \(\lambda^0\)、惩罚参数 \(\rho_0 > 0\)、放大系数 \(\beta > 1\)（如 \(\beta = 10\)）、容忍误差 \(\epsilon > 0\)。
迭代（对于 k = 0, 1, 2, ...）：
a. x-子问题：以当前 \(\lambda^k\) 和 \(\rho_k\) 固定，求解无约束子问题（近似即可）：

\[ x^{k+1} \approx \arg\min_{x} \mathcal{L}_A(x, \lambda^k; \rho_k)。 \]

    这可以用任何无约束优化算法（如拟牛顿法）求解。

b. 约束违反检查：计算约束违反度，例如 \(\|h(x^{k+1})\|\)。如果已足够小（如小于 \(\epsilon\)），则停止迭代，输出 \(x^{k+1}\) 作为近似解。
c. 乘子更新：如果约束违反度不够小，则更新乘子：

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

d. 惩罚参数更新（可选）：如果约束违反度下降不够快，可以增大惩罚参数以施加更强惩罚：\(\rho_{k+1} = \beta \rho_k\)。否则，保持 \(\rho_{k+1} = \rho_k\)。

第五步：扩展到不等式约束
对于形如 \(g_j(x) \le 0\) 的不等式约束，我们可以引入非负松弛变量 \(s_j\) 将其转化为等式约束：\(g_j(x) + s_j = 0, \quad s_j \ge 0\)。相应地，增广拉格朗日函数变为：

\[\mathcal{L}_A(x, s, \mu; \rho) = f(x) + \sum_{j=1}^{p} \left[ \mu_j (g_j(x) + s_j) + \frac{\rho}{2} (g_j(x) + s_j)^2 \right]， \]

并需满足 \(s_j \ge 0\)。通过分析，可以消去松弛变量 \(s_j\)，得到关于 \(x\) 的等价形式，其中涉及对 \(g_j(x)\) 的“算子投影”，乘子更新公式也相应调整。在实际软件中（如 LANCELOT、ALGENCAN），这些处理已被高效实现。

第六步：方法的特点与比较

与二次罚函数法比较：二次罚函数法需要 \(\rho \to \infty\) 才能得到精确解，这会导致子问题病态，难以求解。增广拉格朗日法通过乘子更新，通常只需有限且适中的 \(\rho\) 即可收敛，数值稳定性好得多。
与拉格朗日对偶上升法比较：标准的对偶上升法要求子问题严格凸，且步长选择敏感。增广拉格朗日法由于加入了惩罚项，即使 \(f\) 非凸，子问题也往往是强制的，且乘子更新步长为 \(\rho\)，在温和条件下就能收敛。
适用性：该方法非常适合大规模问题，因为子问题是无约束或边界约束的，可以用高效的梯度类算法求解。它也是许多现代优化软件（如 MATLAB 的 fmincon 在某些设置下）处理非线性约束的核心思想之一。

总结来说，非线性规划中的增广拉格朗日函数法，通过将拉格朗日函数与二次惩罚项相结合，并巧妙设计乘子更新规则，构建了一个稳定、高效的约束处理框架。它避免了大惩罚参数带来的数值困难，同时继承了拉格朗日方法的精确性，是求解非线性约束优化问题的一类重要且实用的方法。

非线性规划中的增广拉格朗日函数法首先，我们从一个常见的约束优化问题出发。假设我们需要最小化一个函数 \( f(x) \)，但变量 \( x \) 必须满足一些等式约束 \( h_ i(x) = 0 \)。这个问题可以写成： \[ \begin{aligned} \min_ {x} \quad & f(x) \\ \text{s.t.} \quad & h_ i(x) = 0, \quad i = 1, \dots, m. \end{aligned} \] 第一步：回顾拉格朗日函数为了解决这个带等式约束的问题，我们通常会引入拉格朗日乘子 \( \lambda_ i \)，构造拉格朗日函数： \[ L(x, \lambda) = f(x) + \sum_ {i=1}^{m} \lambda_ i h_ i(x)。 \] 在最优解 \( x^* \) 处，如果约束规格（如线性无关约束规范LICQ）满足，则存在乘子 \( \lambda^* \) 使得梯度 \( \nabla_ x L(x^ , \lambda^ ) = 0 \)。然而，直接求解这个方程组（即一阶KKT条件）有时并不稳定，尤其是当约束非线性程度高时，数值求解可能困难。第二步：增广拉格朗日函数的引入为了改进求解的稳定性，我们引入一个“增广”的拉格朗日函数。它在标准拉格朗日函数基础上增加了一个惩罚项，形式如下： \[ \mathcal{L} A(x, \lambda; \rho) = f(x) + \sum {i=1}^{m} \lambda_ i h_ i(x) + \frac{\rho}{2} \sum_ {i=1}^{m} h_ i(x)^2。 \] 这里，\( \rho > 0 \) 是一个惩罚参数，\( \frac{\rho}{2} \sum h_ i(x)^2 \) 是惩罚项。注意，这个函数仍然保留了乘子 \( \lambda \)。与标准的二次罚函数法（仅有惩罚项，没有乘子）相比，增广拉格朗日函数通过引入乘子，允许我们在有限的 \( \rho \) 下就能找到精确解，而不仅仅是近似满足约束。第三步：方法的直观理解与优势为什么加入惩罚项和乘子会更有效？我们可以从两个角度理解：惩罚项的作用：当约束不满足时（即 \( h_ i(x) \neq 0 \)），惩罚项 \( \frac{\rho}{2} h_ i(x)^2 \) 会产生一个很大的代价，迫使迭代点向可行域靠近。这使得函数 \( \mathcal{L}_ A \) 关于 \( x \) 的最小化问题更容易求解（因为其 Hessian 通常更好条件化）。乘子的作用：乘子 \( \lambda \) 提供了一个“修正”机制。如果我们有一个当前乘子估计 \( \lambda^k \)，并最小化 \( \mathcal{L}_ A(x, \lambda^k; \rho) \) 得到 \( x^k \)，那么约束违反度 \( h_ i(x^k) \) 通常不为零。此时，我们可以更新乘子：\( \lambda_ i^{k+1} = \lambda_ i^k + \rho h_ i(x^k) \)。这个更新公式来源于对偶上升或近端点的思想，它使得乘子能更准确地估计最优乘子 \( \lambda^* \)，从而在下次迭代中引导解更好地满足约束。第四步：算法的具体步骤（乘子法）对于仅含等式约束的问题，基本的乘子法（也称为增广拉格朗日法）迭代流程如下：初始化：选择初始乘子 \( \lambda^0 \)、惩罚参数 \( \rho_ 0 > 0 \)、放大系数 \( \beta > 1 \)（如 \( \beta = 10 \)）、容忍误差 \( \epsilon > 0 \)。迭代（对于 k = 0, 1, 2, ...）： a. x-子问题：以当前 \( \lambda^k \) 和 \( \rho_ k \) 固定，求解无约束子问题（近似即可）： \[ x^{k+1} \approx \arg\min_ {x} \mathcal{L} A(x, \lambda^k; \rho_ k)。 \] 这可以用任何无约束优化算法（如拟牛顿法）求解。 b. 约束违反检查：计算约束违反度，例如 \( \|h(x^{k+1})\| \)。如果已足够小（如小于 \( \epsilon \)），则停止迭代，输出 \( x^{k+1} \) 作为近似解。 c. 乘子更新：如果约束违反度不够小，则更新乘子： \[ \lambda_ i^{k+1} = \lambda_ i^k + \rho_ k h_ i(x^{k+1}), \quad i=1,\dots,m。 \] d. 惩罚参数更新（可选）：如果约束违反度下降不够快，可以增大惩罚参数以施加更强惩罚：\( \rho {k+1} = \beta \rho_ k \)。否则，保持 \( \rho_ {k+1} = \rho_ k \)。第五步：扩展到不等式约束对于形如 \( g_ j(x) \le 0 \) 的不等式约束，我们可以引入非负松弛变量 \( s_ j \) 将其转化为等式约束：\( g_ j(x) + s_ j = 0, \quad s_ j \ge 0 \)。相应地，增广拉格朗日函数变为： \[ \mathcal{L} A(x, s, \mu; \rho) = f(x) + \sum {j=1}^{p} \left[ \mu_ j (g_ j(x) + s_ j) + \frac{\rho}{2} (g_ j(x) + s_ j)^2 \right ]， \] 并需满足 \( s_ j \ge 0 \)。通过分析，可以消去松弛变量 \( s_ j \)，得到关于 \( x \) 的等价形式，其中涉及对 \( g_ j(x) \) 的“算子投影”，乘子更新公式也相应调整。在实际软件中（如 LANCELOT、ALGENCAN），这些处理已被高效实现。第六步：方法的特点与比较与二次罚函数法比较：二次罚函数法需要 \( \rho \to \infty \) 才能得到精确解，这会导致子问题病态，难以求解。增广拉格朗日法通过乘子更新，通常只需有限且适中的 \( \rho \) 即可收敛，数值稳定性好得多。与拉格朗日对偶上升法比较：标准的对偶上升法要求子问题严格凸，且步长选择敏感。增广拉格朗日法由于加入了惩罚项，即使 \( f \) 非凸，子问题也往往是强制的，且乘子更新步长为 \( \rho \)，在温和条件下就能收敛。适用性：该方法非常适合大规模问题，因为子问题是无约束或边界约束的，可以用高效的梯度类算法求解。它也是许多现代优化软件（如 MATLAB 的 fmincon 在某些设置下）处理非线性约束的核心思想之一。总结来说，非线性规划中的增广拉格朗日函数法，通过将拉格朗日函数与二次惩罚项相结合，并巧妙设计乘子更新规则，构建了一个稳定、高效的约束处理框架。它避免了大惩罚参数带来的数值困难，同时继承了拉格朗日方法的精确性，是求解非线性约束优化问题的一类重要且实用的方法。