非线性规划中的序列线性整数规划法进阶题
题目描述：
考虑非线性整数规划问题：
\[\min f(x) = (x_1 - 1.5)^2 + (x_2 - 2.5)^2 + \sin(x_1 x_2) \]
满足约束：
\[g_1(x) = x_1^2 + x_2^2 - 5 \leq 0, \quad g_2(x) = -x_1 + 2x_2 - 3 = 0 \]
其中 \(x_1, x_2 \in \mathbb{Z}\) 为整数变量。要求通过序列线性整数规划法求解该问题。
解题过程：
-
问题分析
- 目标函数 \(f(x)\) 包含非线性项 \(\sin(x_1 x_2)\)，约束 \(g_1(x)\) 为非线性不等式，\(g_2(x)\) 为线性等式。
- 整数约束使问题为混合整数非线性规划（MINLP），直接求解困难。序列线性整数规划法通过迭代线性化处理非线性部分，并利用整数线性规划（ILP）子问题逐步逼近解。
-
线性化处理
- 在初始点 \(x^{(0)} = (1, 2)\)（满足整数约束）处，对 \(f(x)\) 和 \(g_1(x)\) 进行一阶泰勒展开：
\[ f(x) \approx f(x^{(0)}) + \nabla f(x^{(0)})^\top (x - x^{(0)}) \]
\[ g_1(x) \approx g_1(x^{(0)}) + \nabla g_1(x^{(0)})^\top (x - x^{(0)}) \]
其中梯度计算为：
\[ \nabla f(x) = \begin{bmatrix} 2(x_1 - 1.5) + x_2 \cos(x_1 x_2) \\ 2(x_2 - 2.5) + x_1 \cos(x_1 x_2) \end{bmatrix}, \quad \nabla g_1(x) = \begin{bmatrix} 2x_1 \\ 2x_2 \end{bmatrix} \]
在 $x^{(0)} = (1, 2)$ 处：
\[ \nabla f(x^{(0)}) = \begin{bmatrix} -1 + 2\cos(2) \\ -1 + \cos(2) \end{bmatrix} \approx \begin{bmatrix} -1.832 \\ -1.416 \end{bmatrix}, \quad \nabla g_1(x^{(0)}) = \begin{bmatrix} 2 \\ 4 \end{bmatrix} \]
\[ f(x^{(0)}) \approx 1.25, \quad g_1(x^{(0)}) = 0 \]
- 线性化后的子问题为：
\[ \min \tilde{f}(x) = 1.25 - 1.832(x_1 - 1) - 1.416(x_2 - 2) \]
约束为：
\[ \tilde{g}_1(x) = 2(x_1 - 1) + 4(x_2 - 2) \leq 0, \quad g_2(x) = -x_1 + 2x_2 = 3, \quad x_1, x_2 \in \mathbb{Z} \]
- 求解整数线性规划子问题
- 将等式约束 \(g_2(x)\) 代入目标函数和不等式约束，消去 \(x_1\)（由 \(x_1 = 2x_2 - 3\)）：
\[ \tilde{f}(x) = 1.25 - 1.832(2x_2 - 4) - 1.416(x_2 - 2) = -5.08x_2 + 13.61 \]
\[ \tilde{g}_1(x) = 2(2x_2 - 4) + 4(x_2 - 2) = 8x_2 - 16 \leq 0 \implies x_2 \leq 2 \]
- 结合整数约束 \(x_2 \in \mathbb{Z}\)，解得 \(x_2 = 2\)，代入得 \(x_1 = 1\)，即 \(x^{(1)} = (1, 2)\)，与初始点相同。
- 迭代更新与收敛判断
- 由于子问题解未更新，需调整线性化点。例如，尝试 \(x^{(0)} = (2, 2)\)（满足 \(g_2\)）：
\[ \nabla f(x^{(0)}) \approx \begin{bmatrix} 1 + 4\cos(4) \\ -1 + 2\cos(4) \end{bmatrix} \approx \begin{bmatrix} -0.653 \\ -2.347 \end{bmatrix}, \quad g_1(x^{(0)}) = 3 \]
线性化子问题为：
\[ \min \tilde{f}(x) = 2.25 - 0.653(x_1 - 2) - 2.347(x_2 - 2) \]
\[ \tilde{g}_1(x) = 3 + 4(x_1 - 2) + 4(x_2 - 2) \leq 0 \]
代入 $x_1 = 2x_2 - 3$，化简得：
\[ \tilde{f}(x) = -5.347x_2 + 16.291, \quad \tilde{g}_1(x) = 12x_2 - 21 \leq 0 \implies x_2 \leq 1.75 \]
整数解为 $x_2 = 1$，则 $x_1 = -1$，但需验证可行性：
\[ g_1(-1, 1) = 2 \leq 0, \quad g_2(-1, 1) = 1 \neq 3 \]
不满足等式约束，因此需在子问题中严格保留 $g_2$，并通过整数规划求解器（如分支定界法）直接求解子问题，得到可行整数解。
- 终止条件
- 设定容忍误差 \(\epsilon = 10^{-3}\)。若连续两次迭代解的相对变化 \(\|x^{(k)} - x^{(k-1)}\| / \|x^{(k)}\| < \epsilon\)，或目标函数变化小于 \(\epsilon\)，则终止。
- 实际应用中，需多次迭代线性化并求解子问题，直至收敛到局部最优整数解。
总结：序列线性整数规划法通过迭代构造线性化子问题，将原问题转化为一系列整数线性规划问题。关键步骤包括线性化非线性函数、求解子问题、更新迭代点，并验证收敛性。该方法适用于中等规模的MINLP问题，但可能陷入局部最优。