非线性规划中的自适应惩罚函数法基础题
题目描述
考虑非线性规划问题：
\[\min f(x) = x_1^2 + x_2^2 \]
满足约束：
\[g(x) = x_1 + x_2 - 1 \geq 0 \]
初始点为 \(x^{(0)} = (0, 0)\)，该点不满足约束（\(g(x^{(0)}) = -1 < 0\)）。使用自适应惩罚函数法，构造惩罚函数并迭代求解，逐步逼近最优解。
解题过程
1. 自适应惩罚函数法的基本思想
自适应惩罚函数法通过动态调整惩罚系数，平衡目标函数与约束违反程度。其惩罚函数形式为：
\[P(x, \mu) = f(x) + \mu \cdot \Phi(g(x)) \]
其中：
- \(\mu\) 是惩罚系数，随迭代自适应调整；
- \(\Phi(g(x))\) 是约束违反函数，通常取 \(\Phi(g) = [\min(0, g)]^2\)（对于不等式约束 \(g(x) \geq 0\)）。
自适应策略：若当前点违反约束，则增大 \(\mu\) 以加强惩罚；若满足约束，则减小 \(\mu\) 以优先优化目标函数。
2. 构造惩罚函数
对于约束 \(g(x) \geq 0\)，违反函数为：
\[\Phi(g(x)) = [\min(0, g(x))]^2 = [\min(0, x_1 + x_2 - 1)]^2 \]
惩罚函数为：
\[P(x, \mu) = x_1^2 + x_2^2 + \mu \cdot [\min(0, x_1 + x_2 - 1)]^2 \]
3. 迭代求解
初始设置：
- \(x^{(0)} = (0, 0)\)，\(\mu_0 = 1\)，容忍误差 \(\epsilon = 10^{-3}\)。
- 约束违反值 \(g(x^{(0)}) = -1\)，违反函数值 \(\Phi = (-1)^2 = 1\)。
第1轮迭代（\(k=0\)）
- 最小化惩罚函数：固定 \(\mu_0 = 1\)，求解无约束问题 \(\min P(x, 1)\)：
- 在区域 \(g(x) < 0\)（即 \(x_1 + x_2 < 1\)）时，惩罚项生效：
\[ P(x, 1) = x_1^2 + x_2^2 + (x_1 + x_2 - 1)^2 \]
- 求梯度并令其为0：
\[ \nabla P = \begin{bmatrix} 2x_1 + 2(x_1 + x_2 - 1) \\ 2x_2 + 2(x_1 + x_2 - 1) \end{bmatrix} = 0 \]
解得 $x_1 = x_2 = \frac{1}{3}$。
- 验证 \(g(\frac{1}{3}, \frac{1}{3}) = -\frac{1}{3} < 0\)，解有效。
- 更新 \(x^{(1)} = (0.333, 0.333)\)。
- 自适应调整 \(\mu\)：
- 约束违反值 \(g(x^{(1)}) = -0.333\)，仍违反约束。
- 增大惩罚系数：\(\mu_1 = 10 \mu_0 = 10\)。
第2轮迭代（\(k=1\)）
- 最小化 \(P(x, 10)\)：
\[ P(x, 10) = x_1^2 + x_2^2 + 10(x_1 + x_2 - 1)^2 \]
- 梯度为：
\[ \nabla P = \begin{bmatrix} 2x_1 + 20(x_1 + x_2 - 1) \\ 2x_2 + 20(x_1 + x_2 - 1) \end{bmatrix} = 0 \]
- 解得 \(x_1 = x_2 = \frac{10}{22} \approx 0.455\)。
- \(g(0.455, 0.455) = -0.09 < 0\)，解有效。
- 更新 \(x^{(2)} = (0.455, 0.455)\)。
- 调整 \(\mu\)：违反约束仍存在，继续增大：\(\mu_2 = 10 \mu_1 = 100\)。
第3轮迭代（\(k=2\)）
- 最小化 \(P(x, 100)\)：
- 梯度方程：
\[ 2x_1 + 200(x_1 + x_2 - 1) = 0, \quad 2x_2 + 200(x_1 + x_2 - 1) = 0 \]
- 解得 \(x_1 = x_2 = \frac{100}{202} \approx 0.495\)。
- \(g(0.495, 0.495) = -0.01\)，更新 \(x^{(3)} = (0.495, 0.495)\)。
- 调整 \(\mu\)：\(\mu_3 = 1000\)。
收敛判断
- 继续迭代，当 \(\mu_k\) 足够大时，解逼近约束边界 \(x_1 + x_2 = 1\)。
- 解析解：原问题最优解在约束边界上，由拉格朗日法易得 \(x_1^* = x_2^* = 0.5\)。
- 当 \(|\mu_k \cdot \Phi(g(x^{(k)}))| < \epsilon\) 时停止。本例中，经过若干次迭代后，\(x^{(k)} \to (0.5, 0.5)\)。
关键点总结
- 自适应惩罚：通过动态调整 \(\mu\)，避免手动选择固定惩罚系数的困难。
- 无约束优化：每次迭代求解一个无约束问题，可用梯度法或牛顿法。
- 收敛性：当 \(\mu \to \infty\)，惩罚函数解收敛于原问题解。