非线性规划中的乘子法基础题
字数 2423 2025-10-26 09:00:52

非线性规划中的乘子法基础题

题目描述
考虑非线性约束优化问题：
最小化 \(f(x) = x_1^2 + x_2^2\)
满足约束 \(h(x) = x_1 + x_2 - 2 = 0\)。
要求使用乘子法（Method of Multipliers）求解该问题，并详细解释其原理和步骤。

解题过程
乘子法通过结合拉格朗日函数和罚函数的思想，将约束问题转化为一系列无约束子问题。其核心是动态更新乘子（拉格朗日乘子）和惩罚参数，以加速收敛。

1. 构造增广拉格朗日函数
对于等式约束问题，增广拉格朗日函数定义为：

\[L_A(x, \lambda, \mu) = f(x) + \lambda h(x) + \frac{\mu}{2} [h(x)]^2 \]

其中：

  • \(\lambda\) 是拉格朗日乘子（标量），
  • \(\mu\) 是惩罚参数（\(\mu > 0\)）。
    代入本题具体函数：

\[L_A(x, \lambda, \mu) = x_1^2 + x_2^2 + \lambda (x_1 + x_2 - 2) + \frac{\mu}{2} (x_1 + x_2 - 2)^2 \]

2. 乘子法迭代步骤
步骤 2.1：初始化
选择初始乘子 \(\lambda^{(0)}\)（例如 \(\lambda^{(0)} = 0\)）、惩罚参数 \(\mu^{(0)} > 0\)（例如 \(\mu^{(0)} = 1\)）、放大系数 \(\beta > 1\)（例如 \(\beta = 10\)），并设定收敛容差 \(\epsilon\)。

步骤 2.2：求解无约束子问题
在第 \(k\) 次迭代中，固定 \(\lambda^{(k)}\) 和 \(\mu^{(k)}\)，求解：

\[x^{(k)} = \arg\min_{x} L_A(x, \lambda^{(k)}, \mu^{(k)}) \]

通过梯度为零求解析解：

\[\nabla_x L_A = \begin{bmatrix} 2x_1 + \lambda^{(k)} + \mu^{(k)}(x_1 + x_2 - 2) \\ 2x_2 + \lambda^{(k)} + \mu^{(k)}(x_1 + x_2 - 2) \end{bmatrix} = 0 \]

由于两式对称，解得 \(x_1 = x_2\)。代入第一式：

\[2x_1 + \lambda^{(k)} + \mu^{(k)}(2x_1 - 2) = 0 \]

整理得：

\[x_1^{(k)} = x_2^{(k)} = \frac{2\mu^{(k)} - \lambda^{(k)}}{2 + 2\mu^{(k)}} \]

步骤 2.3：更新乘子
利用当前解 \(x^{(k)}\) 更新乘子：

\[\lambda^{(k+1)} = \lambda^{(k)} + \mu^{(k)} h(x^{(k)}) \]

代入 \(h(x) = x_1 + x_2 - 2\) 和 \(x_1^{(k)} = x_2^{(k)}\)：

\[\lambda^{(k+1)} = \lambda^{(k)} + \mu^{(k)} \left( 2 \cdot \frac{2\mu^{(k)} - \lambda^{(k)}}{2 + 2\mu^{(k)}} - 2 \right) \]

简化后：

\[\lambda^{(k+1)} = \lambda^{(k)} - \frac{2\mu^{(k)} (\lambda^{(k)} + 2)}{1 + \mu^{(k)}} \]

步骤 2.4：检查收敛性
若约束违反度 \(|h(x^{(k)})| \leq \epsilon\)（例如 \(\epsilon = 10^{-6}\)），则停止；否则进入下一步。

步骤 2.5：调整惩罚参数
若 \(|h(x^{(k)})|\) 下降不够快，可增大惩罚参数：

\[\mu^{(k+1)} = \beta \mu^{(k)} \]

但本题中，由于约束为线性，乘子更新已能保证收敛，无需频繁调整 \(\mu\)。

3. 迭代计算示例
取 \(\lambda^{(0)} = 0, \mu^{(0)} = 1, \beta = 10\)：

  • 迭代 1：
    \(x_1^{(1)} = x_2^{(1)} = (2 \cdot 1 - 0) / (2 + 2 \cdot 1) = 0.5\)，
    \(h(x^{(1)}) = 0.5 + 0.5 - 2 = -1\)，
    \(\lambda^{(2)} = 0 + 1 \cdot (-1) = -1\)。
  • 迭代 2：
    \(x_1^{(2)} = (2 \cdot 1 - (-1)) / 4 = 0.75\)，
    \(h(x^{(2)}) = 1.5 - 2 = -0.5\)，
    \(\lambda^{(3)} = -1 + 1 \cdot (-0.5) = -1.5\)。
    继续迭代，\(h(x)\) 逐渐趋近于 0，最终收敛到最优解 \(x_1^* = x_2^* = 1\)，此时 \(h(x^*) = 0\)，\(\lambda^* = -2\)。

4. 原理总结
乘子法通过增广拉格朗日函数将约束转化为无约束问题，其优势在于：

  • 惩罚项 \(\frac{\mu}{2} h(x)^2\) 保证子问题可解；
  • 乘子更新公式 \(\lambda^{(k+1)} = \lambda^{(k)} + \mu h(x^{(k)})\) 利用约束违反度动态修正乘子，比纯罚函数法更高效；
  • 线性约束下，有限步内即可收敛到精确解。
非线性规划中的乘子法基础题 题目描述 考虑非线性约束优化问题： 最小化 \( f(x) = x_ 1^2 + x_ 2^2 \) 满足约束 \( h(x) = x_ 1 + x_ 2 - 2 = 0 \)。 要求使用乘子法（Method of Multipliers）求解该问题，并详细解释其原理和步骤。 解题过程 乘子法通过结合拉格朗日函数和罚函数的思想，将约束问题转化为一系列无约束子问题。其核心是动态更新乘子（拉格朗日乘子）和惩罚参数，以加速收敛。 1. 构造增广拉格朗日函数 对于等式约束问题，增广拉格朗日函数定义为： \[ L_ A(x, \lambda, \mu) = f(x) + \lambda h(x) + \frac{\mu}{2} [ h(x) ]^2 \] 其中： \(\lambda\) 是拉格朗日乘子（标量）， \(\mu\) 是惩罚参数（\(\mu > 0\)）。 代入本题具体函数： \[ L_ A(x, \lambda, \mu) = x_ 1^2 + x_ 2^2 + \lambda (x_ 1 + x_ 2 - 2) + \frac{\mu}{2} (x_ 1 + x_ 2 - 2)^2 \] 2. 乘子法迭代步骤 步骤 2.1：初始化 选择初始乘子 \(\lambda^{(0)}\)（例如 \(\lambda^{(0)} = 0\)）、惩罚参数 \(\mu^{(0)} > 0\)（例如 \(\mu^{(0)} = 1\)）、放大系数 \(\beta > 1\)（例如 \(\beta = 10\)），并设定收敛容差 \(\epsilon\)。 步骤 2.2：求解无约束子问题 在第 \(k\) 次迭代中，固定 \(\lambda^{(k)}\) 和 \(\mu^{(k)}\)，求解： \[ x^{(k)} = \arg\min_ {x} L_ A(x, \lambda^{(k)}, \mu^{(k)}) \] 通过梯度为零求解析解： \[ \nabla_ x L_ A = \begin{bmatrix} 2x_ 1 + \lambda^{(k)} + \mu^{(k)}(x_ 1 + x_ 2 - 2) \\ 2x_ 2 + \lambda^{(k)} + \mu^{(k)}(x_ 1 + x_ 2 - 2) \end{bmatrix} = 0 \] 由于两式对称，解得 \(x_ 1 = x_ 2\)。代入第一式： \[ 2x_ 1 + \lambda^{(k)} + \mu^{(k)}(2x_ 1 - 2) = 0 \] 整理得： \[ x_ 1^{(k)} = x_ 2^{(k)} = \frac{2\mu^{(k)} - \lambda^{(k)}}{2 + 2\mu^{(k)}} \] 步骤 2.3：更新乘子 利用当前解 \(x^{(k)}\) 更新乘子： \[ \lambda^{(k+1)} = \lambda^{(k)} + \mu^{(k)} h(x^{(k)}) \] 代入 \(h(x) = x_ 1 + x_ 2 - 2\) 和 \(x_ 1^{(k)} = x_ 2^{(k)}\)： \[ \lambda^{(k+1)} = \lambda^{(k)} + \mu^{(k)} \left( 2 \cdot \frac{2\mu^{(k)} - \lambda^{(k)}}{2 + 2\mu^{(k)}} - 2 \right) \] 简化后： \[ \lambda^{(k+1)} = \lambda^{(k)} - \frac{2\mu^{(k)} (\lambda^{(k)} + 2)}{1 + \mu^{(k)}} \] 步骤 2.4：检查收敛性 若约束违反度 \(|h(x^{(k)})| \leq \epsilon\)（例如 \(\epsilon = 10^{-6}\)），则停止；否则进入下一步。 步骤 2.5：调整惩罚参数 若 \(|h(x^{(k)})|\) 下降不够快，可增大惩罚参数： \[ \mu^{(k+1)} = \beta \mu^{(k)} \] 但本题中，由于约束为线性，乘子更新已能保证收敛，无需频繁调整 \(\mu\)。 3. 迭代计算示例 取 \(\lambda^{(0)} = 0, \mu^{(0)} = 1, \beta = 10\)： 迭代 1 ： \(x_ 1^{(1)} = x_ 2^{(1)} = (2 \cdot 1 - 0) / (2 + 2 \cdot 1) = 0.5\)， \(h(x^{(1)}) = 0.5 + 0.5 - 2 = -1\)， \(\lambda^{(2)} = 0 + 1 \cdot (-1) = -1\)。 迭代 2 ： \(x_ 1^{(2)} = (2 \cdot 1 - (-1)) / 4 = 0.75\)， \(h(x^{(2)}) = 1.5 - 2 = -0.5\)， \(\lambda^{(3)} = -1 + 1 \cdot (-0.5) = -1.5\)。 继续迭代，\(h(x)\) 逐渐趋近于 0，最终收敛到最优解 \(x_ 1^* = x_ 2^* = 1\)，此时 \(h(x^ ) = 0\)，\(\lambda^ = -2\)。 4. 原理总结 乘子法通过增广拉格朗日函数将约束转化为无约束问题，其优势在于： 惩罚项 \(\frac{\mu}{2} h(x)^2\) 保证子问题可解； 乘子更新公式 \(\lambda^{(k+1)} = \lambda^{(k)} + \mu h(x^{(k)})\) 利用约束违反度动态修正乘子，比纯罚函数法更高效； 线性约束下，有限步内即可收敛到精确解。