非线性规划中的序列线性化方法(SLM)基础题
题目描述
考虑非线性规划问题：
最小化 \(f(x) = (x_1 - 2)^4 + (x_1 - 2x_2)^2\)
满足约束 \(h(x) = x_1^2 - x_2 = 0\)。
使用序列线性化方法（SLM）求解该问题，初始点选为 \(x^{(0)} = (2, 1)\)，迭代2步，并分析约束线性化后的可行性。
解题过程
1. 方法原理
序列线性化方法通过逐次线性化非线性约束和目标函数，将原问题转化为一系列线性规划子问题。对于问题：
\[\min f(x) \quad \text{s.t.} \quad h(x) = 0, \]
在迭代点 \(x^{(k)}\) 处，对 \(f(x)\) 和 \(h(x)\) 做一阶泰勒展开：
- 目标函数线性化：\(f(x) \approx f(x^{(k)}) + \nabla f(x^{(k)})^T (x - x^{(k)})\)。
- 约束线性化：\(h(x) \approx h(x^{(k)}) + \nabla h(x^{(k)})^T (x - x^{(k)}) = 0\)。
子问题为线性规划：
\[\min \nabla f(x^{(k)})^T d \quad \text{s.t.} \quad \nabla h(x^{(k)})^T d = -h(x^{(k)}), \]
其中 \(d = x - x^{(k)}\)。解出 \(d^{(k)}\) 后更新 \(x^{(k+1)} = x^{(k)} + d^{(k)}\)。
2. 初始点计算
给定 \(x^{(0)} = (2, 1)\)：
- 目标函数值：\(f(x^{(0)}) = (2-2)^4 + (2 - 2 \times 1)^2 = 0 + 0 = 0\)。
- 约束值：\(h(x^{(0)}) = 2^2 - 1 = 3 \neq 0\)（初始点不满足约束）。
- 梯度计算：
- \(\nabla f(x) = \left[ 4(x_1 - 2)^3 + 2(x_1 - 2x_2), \ -4(x_1 - 2x_2) \right]\)，
代入 \(x^{(0)}\) 得 \(\nabla f(x^{(0)}) = [0 + 0, \ 0] = (0, 0)\)。 - \(\nabla h(x) = [2x_1, \ -1]\)，代入得 \(\nabla h(x^{(0)}) = (4, -1)\)。
- \(\nabla f(x) = \left[ 4(x_1 - 2)^3 + 2(x_1 - 2x_2), \ -4(x_1 - 2x_2) \right]\)，
3. 第一步迭代（k=0）
子问题关于 \(d = (d_1, d_2)\)：
- 目标：最小化 \(\nabla f(x^{(0)})^T d = 0 \cdot d_1 + 0 \cdot d_2 = 0\)（常函数，任意 \(d\) 均最优）。
- 约束：\(\nabla h(x^{(0)})^T d = -h(x^{(0)}) \Rightarrow 4d_1 - d_2 = -3\)。
由于目标函数为常数，需额外规则确定 \(d\)。通常添加范数约束 \(\|d\| \leq \Delta\) 避免无界解，但本题未指定，故直接解约束方程。
令 \(d_2 = 4d_1 + 3\)（由约束变形），代入目标函数仍为常数。需选择最小范数解：最小化 \(\|d\|^2 = d_1^2 + (4d_1 + 3)^2\)。
求导得 \(2d_1 + 8(4d_1 + 3) = 34d_1 + 24 = 0 \Rightarrow d_1 = -12/17\)，
\(d_2 = 4 \times (-12/17) + 3 = -48/17 + 51/17 = 3/17\)。
更新点：\(x^{(1)} = x^{(0)} + d = (2 - 12/17, \ 1 + 3/17) = (22/17, \ 20/17) \approx (1.294, \ 1.176)\)。
4. 第二步迭代（k=1）
计算 \(x^{(1)}\) 处信息：
- \(f(x^{(1)}) = (22/17 - 2)^4 + (22/17 - 2 \times 20/17)^2 = (-12/17)^4 + (-18/17)^2 \approx 0.219 + 1.121 = 1.34\)。
- \(h(x^{(1)}) = (22/17)^2 - 20/17 = 484/289 - 380/289 = 104/289 \approx 0.36\)。
- 梯度：
- \(\nabla f(x^{(1)}) = \left[ 4(-12/17)^3 + 2(-18/17), \ -4(-18/17) \right] \approx [-0.244 - 2.118, \ 4.235] = (-2.362, \ 4.235)\)。
- \(\nabla h(x^{(1)}) = [2 \times 22/17, \ -1] = (44/17, \ -1) \approx (2.588, \ -1)\)。
子问题：
- 目标：最小化 \(\nabla f(x^{(1)})^T d = -2.362 d_1 + 4.235 d_2\)。
- 约束：\(2.588 d_1 - d_2 = -0.36\)。
令 \(d_2 = 2.588 d_1 + 0.36\)，代入目标得：
\[-2.362 d_1 + 4.235 (2.588 d_1 + 0.36) = (-2.362 + 10.96) d_1 + 1.524 = 8.598 d_1 + 1.524。 \]
目标函数随 \(d_1\) 减小而减小（系数正），但需约束 \(\|d\|\) 有界。若不加范数约束，解无界。实际SLM中需控制步长（如信赖域）。此处假设最大步长 \(\Delta = 0.5\)，解约束下的线性规划：
添加约束 \(d_1^2 + d_2^2 \leq 0.25\)，结合线性约束求解。简化计算：取 \(d_1 = -0.3\)（满足范数约束），则 \(d_2 = 2.588 \times (-0.3) + 0.36 = -0.416\)，
\(\|d\| \approx 0.52 > 0.5\)，调整至 \(d_1 = -0.28\)，\(d_2 \approx -0.365\)，\(\|d\| \approx 0.45\)。
更新点：\(x^{(2)} \approx (1.294 - 0.28, \ 1.176 - 0.365) = (1.014, \ 0.811)\)。
5. 结果分析
- 经过两步迭代，约束值从 \(3\) 降至 \(0.36\)（第一步）和 \(h(x^{(2)}) \approx 1.014^2 - 0.811 = 0.216\)（第二步），约束 violation 减小。
- SLM 的挑战：线性化可能导致子问题不可行或无界，需结合步长控制。本例中初始点梯度为零，第一步依赖约束推动移动；第二步目标梯度出现，引导优化方向。
- 最终点 \(x^{(2)}\) 接近可行域 \(x_1^2 = x_2\)，但需更多迭代收敛至最优解（理论最优在 \(x = (2, 4)\) 处 \(f = 0\)）。