非线性规划中的序列线性整数规划法基础题
题目描述
考虑一个非线性整数规划问题：
\[\min f(x) = (x_1 - 2)^2 + (x_2 - 1)^2 \]
满足约束：
\[\begin{cases} x_1 + x_2 \leq 2 \\ x_1 - x_2 \geq 0 \\ x_1, x_2 \in \mathbb{Z}^+ \cup \{0\} \end{cases} \]
其中 \(x_1, x_2\) 为非负整数。要求使用序列线性整数规划法（SLP-IP）求解该问题。
解题过程
步骤1：理解序列线性整数规划法（SLP-IP）的核心思想
SLP-IP 是一种迭代算法，用于解决非线性整数规划问题。其基本思路是：
- 在每次迭代中，将非线性目标函数和约束在当前点处线性化（通过一阶泰勒展开）；
- 求解得到的线性整数规划子问题；
- 更新当前解，并重复直到收敛。
步骤2：初始化
选择一个初始整数可行解。例如，取 \(x^{(0)} = (0, 0)\)，满足约束：
- \(0 + 0 = 0 \leq 2\)
- \(0 - 0 = 0 \geq 0\)
- 非负整数条件成立。
计算目标函数值：\(f(0,0) = (0-2)^2 + (0-1)^2 = 5\)。
步骤3：第一次迭代（在 \(x^{(0)} = (0,0)\) 处线性化）
对目标函数 \(f(x)\) 在 \(x^{(0)}\) 处进行一阶泰勒展开：
\[f(x) \approx f(x^{(0)}) + \nabla f(x^{(0)})^T (x - x^{(0)}) \]
其中梯度：
\[\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)] \implies \nabla f(0,0) = [-4, -2] \]
常数项 \(f(0,0)=5\) 在优化中可以忽略（因为线性规划只关心线性部分）。因此，线性化后的目标为：
\[\min -4x_1 - 2x_2 \]
约束条件保持不变（已经是线性）：
\[\begin{cases} x_1 + x_2 \leq 2 \\ x_1 - x_2 \geq 0 \\ x_1, x_2 \in \mathbb{Z}^+ \cup \{0\} \end{cases} \]
求解该线性整数规划问题：
- 目标函数是线性递减，需在可行域内使 \(x_1, x_2\) 尽可能大，但受 \(x_1 + x_2 \leq 2\) 和 \(x_1 \geq x_2\) 限制。
- 枚举可行整数解：
- \((0,0)\)：目标值 \(0\)
- \((1,0)\)：目标值 \(-4\)
- \((1,1)\)：目标值 \(-6\)
- \((2,0)\)：目标值 \(-8\)（但 \(2+0=2 \leq 2\)，且 \(2 \geq 0\)，可行）
- \((2,1)\)：不可行（因 \(2+1=3 > 2\)）
- 最优解为 \((2,0)\)，目标值 \(-8\)。
更新当前解：\(x^{(1)} = (2, 0)\)。
步骤4：第二次迭代（在 \(x^{(1)} = (2,0)\) 处线性化）
计算梯度：
\[\nabla f(2,0) = [2(2-2), 2(0-1)] = [0, -2] \]
线性化目标：\(\min 0 \cdot x_1 - 2 x_2 = -2x_2\)。
约束同上。
求解线性整数规划：
- 目标函数只与 \(x_2\) 相关，需最大化 \(x_2\)，但受约束限制。
- 在 \(x_1 + x_2 \leq 2\) 和 \(x_1 \geq x_2\) 下，最大 \(x_2\) 为 1（对应 \(x_1=1\) 或 \(x_1=2\)，但 \(x_1=2\) 时 \(x_2=1\) 不可行，因 \(2+1=3>2\)；取 \(x_1=1, x_2=1\) 可行）。
- 最优解为 \((1,1)\)，目标值 \(-2\)。
更新当前解：\(x^{(2)} = (1, 1)\)。
步骤5：第三次迭代（在 \(x^{(2)} = (1,1)\) 处线性化）
计算梯度：
\[\nabla f(1,1) = [2(1-2), 2(1-1)] = [-2, 0] \]
线性化目标：\(\min -2x_1\)。
约束同上。
求解线性整数规划：
- 需最大化 \(x_1\)，但受 \(x_1 + x_2 \leq 2\) 和 \(x_1 \geq x_2\) 限制。
- 最大 \(x_1=2\)（此时 \(x_2=0\)，可行）。
- 最优解为 \((2,0)\)，目标值 \(-4\)。
更新当前解：\(x^{(3)} = (2, 0)\)。
步骤6：检查收敛
发现 \(x^{(3)} = x^{(1)}\)，算法陷入循环（在两个整数解 \((2,0)\) 和 \((1,1)\) 之间振荡）。
- 计算实际目标函数值：
- \(f(2,0) = (2-2)^2 + (0-1)^2 = 1\)
- \(f(1,1) = (1-2)^2 + (1-1)^2 = 1\)
两者目标值相同，均为最优解（验证：枚举所有可行整数解，\((0,0)\)、\((1,0)\)、\((1,1)\)、\((2,0)\) 中，最小值为 1）。
最终结论
SLP-IP 算法找到两个最优解 \((2,0)\) 和 \((1,1)\)，目标值均为 1。由于线性化逼近的局限性，算法在最优解间振荡，但实际已收敛到最优值。在实际应用中，需设置终止条件（如目标值变化小于阈值或重复解出现）。