非线性规划中的乘子法（Method of Multipliers）

字数 2516 2025-12-06 09:05:30

非线性规划中的乘子法（Method of Multipliers）

首先，我们需要理解乘子法解决的是什么问题。考虑一个带等式约束的非线性规划问题：

\[\min f(x) \]

\[\text{s.t. } h_i(x)=0, \quad i=1,\dots,m \]

其中，$f$ 和 $h_i$ 是连续可微函数。这是一个经典的约束优化问题。为了解决它，我们先回顾一个你可能熟悉的方法。

第一步：从拉格朗日函数到罚函数的局限
对于上述问题，拉格朗日函数是 $L(x, \lambda) = f(x) + \sum_{i=1}^{m} \lambda_i h_i(x)$。如果直接求解其稳定点（KKT条件），在非凸问题时可能不易直接数值求解。另一种思路是罚函数法，例如外点罚函数法：构造罚函数 $P(x, \mu) = f(x) + \frac{\mu}{2} \sum_{i=1}^{m} h_i(x)^2$，通过逐渐增大罚参数 $\mu \to +\infty$，迫使 $h_i(x) \to 0$。但这种方法有一个显著缺点：当 $\mu$ 非常大时，罚函数 $P(x, \mu)$ 的 Hessian 矩阵条件数会变得非常差，导致数值计算困难（如迭代步长极小、收敛极慢）。

第二步：引入乘子法的核心思想——增广拉格朗日函数
为了克服大罚参数带来的数值病态，乘子法（也称增广拉格朗日法）对拉格朗日函数进行“增广”，构造如下函数：

\[L_A(x, \lambda; \mu) = f(x) + \sum_{i=1}^{m} \lambda_i h_i(x) + \frac{\mu}{2} \sum_{i=1}^{m} h_i(x)^2 \]

其中，$\mu > 0$ 是罚参数，$\lambda$ 是拉格朗日乘子估计。与纯罚函数相比，这里多了一项 $\sum \lambda_i h_i(x)$。它的妙处在于：在最优解 $x^*$ 和对应的最优乘子 $\lambda^*$ 处，即使 $\mu$ 不趋向无穷大，只要 $(\lambda, \mu)$ 选择合适，$x^*$ 就可能是 $L_A(x, \lambda; \mu)$ 的一个无约束极小点。这意味着我们不需要将 $\mu$ 推到无穷大也能精确求解原问题。

第三步：乘子法的迭代算法框架
乘子法是一个迭代算法，每轮迭代包含两个步骤：

固定乘子进行无约束极小化：给定当前的乘子估计 $\lambda^k$ 和罚参数 $\mu_k$，求解（近似）无约束子问题：

\[x^{k+1} \approx \arg\min_x L_A(x, \lambda^k; \mu_k) \]

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

更新乘子：利用得到的 $x^{k+1}$ 更新乘子：

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

然后，根据规则（如约束违反度是否显著下降）决定是否增大 $\mu_k$。

第四步：理解乘子更新的直观含义
为什么乘子更新公式是 $\lambda^{k+1} = \lambda^k + \mu h(x^{k+1})$？从最优性条件看，在原问题的最优点 $x^*$ 处，应满足 $\nabla_x L(x^*, \lambda^*) = 0$ 和 $h(x^*)=0$。而对增广拉格朗日函数，其梯度为：

\[\nabla_x L_A(x, \lambda; \mu) = \nabla f(x) + \sum (\lambda_i + \mu h_i(x)) \nabla h_i(x) \]

如果我们在 $x^{k+1}$ 处有 $\nabla_x L_A(x^{k+1}, \lambda^k; \mu_k) \approx 0$，那么对比标准拉格朗日函数的梯度条件 $\nabla f + \sum \lambda_i^* \nabla h_i = 0$，很自然地令 $\lambda_i^{k+1} = \lambda_i^k + \mu_k h_i(x^{k+1})$ 作为新的乘子估计。这可以看作是对原问题拉格朗日乘子的一种逼近修正。当 $h_i(x^{k+1}) \to 0$ 时，$\lambda^{k+1}$ 就趋近于最优乘子 $\lambda^*$。

第五步：收敛性与优势
在适当的条件下（如 $f$ 下有界，$\mu_k$ 充分大后固定），乘子法具有以下性质：

不需要 $\mu_k \to \infty$ 也能收敛到精确解，这与纯罚函数法不同。
由于 $\mu_k$ 不必趋于无穷，增广拉格朗日函数 $L_A$ 的 Hessian 矩阵不会无限病态，数值稳定性好。
乘子更新公式具有一阶收敛性质，当接近解时，收敛速度较快。

第六步：扩展到不等式约束
对于不等式约束 $g_j(x) \le 0$，可以通过引入松弛变量 $z_j \ge 0$ 将其化为等式约束 $g_j(x) + z_j^2 = 0$，然后应用上述乘子法。更直接的方法是使用如下形式的增广拉格朗日函数：

\[L_A(x, \mu, \sigma) = f(x) + \frac{1}{2\sigma} \sum_{j} \left\{ \left[ \max(0, \mu_j + \sigma g_j(x)) \right]^2 - \mu_j^2 \right\} \]

其中 $\mu_j$ 是乘子，$\sigma > 0$ 是罚参数，并有相应的乘子更新公式 $\mu_j^{k+1} = \max(0, \mu_j^k + \sigma g_j(x^{k+1}))$。其原理与等式约束类似。

总结来说，乘子法通过将拉格朗日乘子估计与罚函数结合，巧妙地平衡了精确性和数值稳定性，是求解非线性规划问题的一类重要且实用的算法。

非线性规划中的乘子法（Method of Multipliers）首先，我们需要理解乘子法解决的是什么问题。考虑一个带等式约束的非线性规划问题： $$\min f(x)$$ $$\text{s.t. } h_ i(x)=0, \quad i=1,\dots,m$$ 其中，$f$ 和 $h_ i$ 是连续可微函数。这是一个经典的约束优化问题。为了解决它，我们先回顾一个你可能熟悉的方法。第一步：从拉格朗日函数到罚函数的局限对于上述问题，拉格朗日函数是 $L(x, \lambda) = f(x) + \sum_ {i=1}^{m} \lambda_ i h_ i(x)$。如果直接求解其稳定点（KKT条件），在非凸问题时可能不易直接数值求解。另一种思路是罚函数法，例如外点罚函数法：构造罚函数 $P(x, \mu) = f(x) + \frac{\mu}{2} \sum_ {i=1}^{m} h_ i(x)^2$，通过逐渐增大罚参数 $\mu \to +\infty$，迫使 $h_ i(x) \to 0$。但这种方法有一个显著缺点：当 $\mu$ 非常大时，罚函数 $P(x, \mu)$ 的 Hessian 矩阵条件数会变得非常差，导致数值计算困难（如迭代步长极小、收敛极慢）。第二步：引入乘子法的核心思想——增广拉格朗日函数为了克服大罚参数带来的数值病态，乘子法（也称增广拉格朗日法）对拉格朗日函数进行“增广”，构造如下函数： $$L_ A(x, \lambda; \mu) = f(x) + \sum_ {i=1}^{m} \lambda_ i h_ i(x) + \frac{\mu}{2} \sum_ {i=1}^{m} h_ i(x)^2$$ 其中，$\mu > 0$ 是罚参数，$\lambda$ 是拉格朗日乘子估计。与纯罚函数相比，这里多了一项 $\sum \lambda_ i h_ i(x)$。它的妙处在于：在最优解 $x^ $ 和对应的最优乘子 $\lambda^ $ 处，即使 $\mu$ 不趋向无穷大，只要 $(\lambda, \mu)$ 选择合适，$x^* $ 就可能是 $L_ A(x, \lambda; \mu)$ 的一个无约束极小点。这意味着我们不需要将 $\mu$ 推到无穷大也能精确求解原问题。第三步：乘子法的迭代算法框架乘子法是一个迭代算法，每轮迭代包含两个步骤：固定乘子进行无约束极小化：给定当前的乘子估计 $\lambda^k$ 和罚参数 $\mu_ k$，求解（近似）无约束子问题： $$x^{k+1} \approx \arg\min_ x L_ A(x, \lambda^k; \mu_ k)$$ 这可以用任何无约束优化方法（如拟牛顿法）求解。更新乘子：利用得到的 $x^{k+1}$ 更新乘子： $$\lambda_ i^{k+1} = \lambda_ i^k + \mu_ k h_ i(x^{k+1}), \quad i=1,\dots,m$$ 然后，根据规则（如约束违反度是否显著下降）决定是否增大 $\mu_ k$。第四步：理解乘子更新的直观含义为什么乘子更新公式是 $\lambda^{k+1} = \lambda^k + \mu h(x^{k+1})$？从最优性条件看，在原问题的最优点 $x^ $ 处，应满足 $\nabla_ x L(x^ , \lambda^ ) = 0$ 和 $h(x^ )=0$。而对增广拉格朗日函数，其梯度为： $$\nabla_ x L_ A(x, \lambda; \mu) = \nabla f(x) + \sum (\lambda_ i + \mu h_ i(x)) \nabla h_ i(x)$$ 如果我们在 $x^{k+1}$ 处有 $\nabla_ x L_ A(x^{k+1}, \lambda^k; \mu_ k) \approx 0$，那么对比标准拉格朗日函数的梯度条件 $\nabla f + \sum \lambda_ i^* \nabla h_ i = 0$，很自然地令 $\lambda_ i^{k+1} = \lambda_ i^k + \mu_ k h_ i(x^{k+1})$ 作为新的乘子估计。这可以看作是对原问题拉格朗日乘子的一种逼近修正。当 $h_ i(x^{k+1}) \to 0$ 时，$\lambda^{k+1}$ 就趋近于最优乘子 $\lambda^* $。第五步：收敛性与优势在适当的条件下（如 $f$ 下有界，$\mu_ k$ 充分大后固定），乘子法具有以下性质：不需要 $\mu_ k \to \infty$ 也能收敛到精确解，这与纯罚函数法不同。由于 $\mu_ k$ 不必趋于无穷，增广拉格朗日函数 $L_ A$ 的 Hessian 矩阵不会无限病态，数值稳定性好。乘子更新公式具有一阶收敛性质，当接近解时，收敛速度较快。第六步：扩展到不等式约束对于不等式约束 $g_ j(x) \le 0$，可以通过引入松弛变量 $z_ j \ge 0$ 将其化为等式约束 $g_ j(x) + z_ j^2 = 0$，然后应用上述乘子法。更直接的方法是使用如下形式的增广拉格朗日函数： $$L_ A(x, \mu, \sigma) = f(x) + \frac{1}{2\sigma} \sum_ {j} \left\{ \left[ \max(0, \mu_ j + \sigma g_ j(x)) \right]^2 - \mu_ j^2 \right\}$$ 其中 $\mu_ j$ 是乘子，$\sigma > 0$ 是罚参数，并有相应的乘子更新公式 $\mu_ j^{k+1} = \max(0, \mu_ j^k + \sigma g_ j(x^{k+1}))$。其原理与等式约束类似。总结来说，乘子法通过将拉格朗日乘子估计与罚函数结合，巧妙地平衡了精确性和数值稳定性，是求解非线性规划问题的一类重要且实用的算法。