非线性规划中的松弛线性规划法基础题
题目描述
考虑非线性规划问题：
\[\min f(x) = (x_1 - 2)^2 + (x_2 - 1)^2 \]
满足约束：
\[g_1(x) = x_1^2 - x_2 \le 0, \quad g_2(x) = x_1 + x_2 - 2 \le 0 \]
初始可行点 \(x^{(0)} = (0, 0)\)，使用松弛线性规划法（SLP）进行两次迭代，并说明其原理。
解题过程
1. 方法原理
松弛线性规划法（Sequential Linear Programming, SLP）通过线性化非线性函数，将原问题转化为一系列线性规划子问题：
- 在当前点 \(x^{(k)}\) 对目标函数和约束进行一阶泰勒展开；
- 添加移动限制（信任域）\(\|d\| \le \delta^{(k)}\)，防止线性近似误差过大；
- 求解线性规划子问题，得到搜索方向 \(d^{(k)}\)；
- 更新 \(x^{(k+1)} = x^{(k)} + d^{(k)}\)，调整信任域半径 \(\delta^{(k)}\)。
2. 第一次迭代（\(k=0\)）
初始点 \(x^{(0)} = (0, 0)\)，设信任域半径 \(\delta^{(0)} = 0.5\)。
线性化计算：
- 目标函数梯度：\(\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)]\)，在 \(x^{(0)}\) 处：
\[ \nabla f(0,0) = [-4, -2], \quad f(0,0) = 4 + 1 = 5 \]
线性化：\(f(x) \approx f(0,0) + \nabla f(0,0)^T d = 5 - 4d_1 - 2d_2\)。
- 约束 \(g_1(x) = x_1^2 - x_2\)：
\[ \nabla g_1 = [2x_1, -1] \Rightarrow \nabla g_1(0,0) = [0, -1], \quad g_1(0,0) = 0 \]
线性化：\(g_1 \approx 0 + 0 \cdot d_1 - 1 \cdot d_2 = -d_2 \le 0\)。
- 约束 \(g_2(x) = x_1 + x_2 - 2\)：
\[ \nabla g_2 = [1, 1], \quad g_2(0,0) = -2 \le 0 \]
线性化：\(g_2 \approx -2 + d_1 + d_2 \le 0 \Rightarrow d_1 + d_2 \le 2\)（注意原约束已满足，线性化后仍有效）。
子问题（线性规划）：
\[\min_{d} -4d_1 - 2d_2 \]
满足：
\[-d_2 \le 0, \quad d_1 + d_2 \le 2, \quad \|d\|_\infty \le 0.5 \]
（使用无穷范数信任域：\(|d_1| \le 0.5, |d_2| \le 0.5\)）
求解：
目标函数系数全为负，需最大化 \(d_1, d_2\)。约束 \(-d_2 \le 0 \Rightarrow d_2 \ge 0\)；信任域限制 \(d_1 \le 0.5, d_2 \le 0.5\)。代入 \(d_1 = 0.5, d_2 = 0.5\)：
- 检查 \(d_1 + d_2 = 1 \le 2\)，满足。
最优解 \(d^{(0)} = (0.5, 0.5)\)，目标值 \(-4 \times 0.5 - 2 \times 0.5 = -3\)。
更新点：
\[x^{(1)} = (0, 0) + (0.5, 0.5) = (0.5, 0.5) \]
计算实际函数值：
\[f(0.5,0.5) = (0.5-2)^2 + (0.5-1)^2 = 2.25 + 0.25 = 2.5 \]
较初始值 \(f=5\) 下降，接受该点。
3. 第二次迭代（\(k=1\)）
当前点 \(x^{(1)} = (0.5, 0.5)\)，设 \(\delta^{(1)} = 0.5\)。
线性化计算：
- \(\nabla f(0.5,0.5) = [2(0.5-2), 2(0.5-1)] = [-3, -1]\)，
\(f(0.5,0.5) = 2.5\)，线性化：\(f \approx 2.5 - 3d_1 - d_2\)。 - \(g_1(0.5,0.5) = 0.25 - 0.5 = -0.25\)，\(\nabla g_1 = [1, -1]\)，
线性化：\(g_1 \approx -0.25 + d_1 - d_2 \le 0 \Rightarrow d_1 - d_2 \le 0.25\)。 - \(g_2(0.5,0.5) = 0.5 + 0.5 - 2 = -1\)，\(\nabla g_2 = [1, 1]\)，
线性化：\(g_2 \approx -1 + d_1 + d_2 \le 0 \Rightarrow d_1 + d_2 \le 1\)。
子问题：
\[\min_{d} -3d_1 - d_2 \]
满足：
\[d_1 - d_2 \le 0.25, \quad d_1 + d_2 \le 1, \quad |d_1| \le 0.5, \quad |d_2| \le 0.5 \]
求解：
目标函数系数为负，需取最大 \(d_1, d_2\)。约束 \(d_1 + d_2 \le 1\) 更紧于信任域（\(d_1 + d_2 \le 1\) vs \(d_1 \le 0.5, d_2 \le 0.5\)）。尝试顶点：
- 若 \(d_1 = 0.5, d_2 = 0.5\)，则 \(d_1 + d_2 = 1\) 满足，但 \(d_1 - d_2 = 0 \le 0.25\) 成立。
目标值 \(-3 \times 0.5 - 0.5 = -2\)。 - 验证无更优解：若 \(d_2 = 0.5\)，由 \(d_1 + 0.5 \le 1 \Rightarrow d_1 \le 0.5\)，已取最大值。
最优解 \(d^{(1)} = (0.5, 0.5)\)。
更新点：
\[x^{(2)} = (0.5, 0.5) + (0.5, 0.5) = (1, 1) \]
计算实际函数值：
\[f(1,1) = (1-2)^2 + (1-1)^2 = 1 + 0 = 1 \]
较 \(f=2.5\) 下降，接受该点。
4. 结论
两次迭代后，点从 \((0,0)\) 经 \((0.5,0.5)\) 移动到 \((1,1)\)，函数值从 \(5\) 降至 \(1\)。SLP 通过线性近似和信任域控制，逐步逼近最优解（本题最优解在 \(x=(1,1)\)，满足 \(g_1(1,1)=0, g_2(1,1)=0\)）。