非线性规划中的序列线性整数规划法基础题

字数 1722 2025-11-01 09:19:09

非线性规划中的序列线性整数规划法基础题

题目描述
考虑非线性整数规划问题：

\[\min f(x) = (x_1 - 2)^2 + (x_2 - 1)^2 \]

满足约束：

\[g_1(x) = x_1 + x_2 - 2 \leq 0, \quad g_2(x) = -x_1 + x_2 - 1 \leq 0, \quad x \in \mathbb{Z}^2. \]

要求通过序列线性整数规划法（SLP结合整数约束）求解该问题。

解题步骤

初始化
选择初始整数点 $x^{(0)} = (0, 0)$，设定容忍误差 $\epsilon = 0.01$，迭代次数 $k=0$。
线性化非线性函数
在当前点 $x^{(k)}$ 处对目标函数和约束进行线性化：
- 目标函数线性近似：

\[ f(x) \approx f(x^{(k)}) + \nabla f(x^{(k)})^T (x - x^{(k)}) \]

 其中梯度 $\nabla f(x) = [2(x_1 - 2), 2(x_2 - 1)]^T$。

约束线性近似：

\[ g_1(x) \approx g_1(x^{(k)}) + \nabla g_1(x^{(k)})^T (x - x^{(k)}), \quad \nabla g_1 = [1, 1]^T \]

\[ g_2(x) \approx g_2(x^{(k)}) + \nabla g_2(x^{(k)})^T (x - x^{(k)}), \quad \nabla g_2 = [-1, 1]^T \]

构建线性整数规划子问题
在每次迭代中求解如下线性整数规划问题：

\[ \min \nabla f(x^{(k)})^T d \quad \text{（其中 $d = x - x^{(k)}$）} \]

满足线性化约束：

\[ g_1(x^{(k)}) + \nabla g_1^T d \leq 0, \quad g_2(x^{(k)}) + \nabla g_2^T d \leq 0, \quad d \in \mathbb{Z}^2. \]

为避免步长过大，添加信任域约束 $|d| \leq \delta$（初始 $\delta = 1$）。

求解子问题并更新
用整数规划求解器（如分支定界法）解子问题，得到位移 $d^{(k)}$。
- 若子问题无可行解，缩小信任域半径 $\delta$ 重新求解。
- 否则，更新 $x^{(k+1)} = x^{(k)} + d^{(k)}$。
收敛判断
若 $|x^{(k+1)} - x^{(k)}| < \epsilon$ 或目标函数改善量小于 $\epsilon$，停止迭代；否则令 $k = k+1$ 返回步骤2。
实例迭代演示
- 迭代1：$x^{(0)} = (0,0)$，梯度 $\nabla f(0,0) = [-4, -2]^T$，线性约束为 $g_1 = -2 \leq 0$（已满足），$g_2 = -1 \leq 0$（已满足）。子问题为 $\min -4d_1 - 2d_2$，信任域内整数解为 $d=(1,1)$，得 $x^{(1)} = (1,1)$。
- 迭代2：$x^{(1)} = (1,1)$，梯度 $\nabla f(1,1) = [-2, 0]^T$，约束仍满足。子问题解 $d=(1,0)$，得 $x^{(2)} = (2,1)$（最优解）。验证约束：$g_1(2,1)=1 \leq 0$（不满足！）需退回并调整信任域。
- 调整：在 $x^{(1)}$ 处缩小信任域，求解得 $d=(0,0)$，算法终止。最终解为 $x^* = (1,1)$，$f^* = 1$。

关键点

线性化需在整数点进行，信任域控制线性近似有效性。
整数约束使问题非凸，解可能为局部最优。
若线性化导致约束冲突，需缩小信任域重新求解。

非线性规划中的序列线性整数规划法基础题题目描述考虑非线性整数规划问题： \[ \min f(x) = (x_ 1 - 2)^2 + (x_ 2 - 1)^2 \] 满足约束： \[ g_ 1(x) = x_ 1 + x_ 2 - 2 \leq 0, \quad g_ 2(x) = -x_ 1 + x_ 2 - 1 \leq 0, \quad x \in \mathbb{Z}^2. \] 要求通过序列线性整数规划法（SLP结合整数约束）求解该问题。解题步骤初始化选择初始整数点 $ x^{(0)} = (0, 0) $，设定容忍误差 $\epsilon = 0.01$，迭代次数 $k=0$。线性化非线性函数在当前点 $x^{(k)}$ 处对目标函数和约束进行线性化：目标函数线性近似： \[ f(x) \approx f(x^{(k)}) + \nabla f(x^{(k)})^T (x - x^{(k)}) \] 其中梯度 $\nabla f(x) = [ 2(x_ 1 - 2), 2(x_ 2 - 1) ]^T$。约束线性近似： \[ g_ 1(x) \approx g_ 1(x^{(k)}) + \nabla g_ 1(x^{(k)})^T (x - x^{(k)}), \quad \nabla g_ 1 = [ 1, 1 ]^T \] \[ g_ 2(x) \approx g_ 2(x^{(k)}) + \nabla g_ 2(x^{(k)})^T (x - x^{(k)}), \quad \nabla g_ 2 = [ -1, 1 ]^T \] 构建线性整数规划子问题在每次迭代中求解如下线性整数规划问题： \[ \min \nabla f(x^{(k)})^T d \quad \text{（其中 $d = x - x^{(k)}$）} \] 满足线性化约束： \[ g_ 1(x^{(k)}) + \nabla g_ 1^T d \leq 0, \quad g_ 2(x^{(k)}) + \nabla g_ 2^T d \leq 0, \quad d \in \mathbb{Z}^2. \] 为避免步长过大，添加信任域约束 $|d| \leq \delta$（初始 $\delta = 1$）。求解子问题并更新用整数规划求解器（如分支定界法）解子问题，得到位移 $d^{(k)}$。若子问题无可行解，缩小信任域半径 $\delta$ 重新求解。否则，更新 $x^{(k+1)} = x^{(k)} + d^{(k)}$。收敛判断若 $|x^{(k+1)} - x^{(k)}| < \epsilon$ 或目标函数改善量小于 $\epsilon$，停止迭代；否则令 $k = k+1$ 返回步骤2。实例迭代演示迭代1 ：$x^{(0)} = (0,0)$，梯度 $\nabla f(0,0) = [ -4, -2]^T$，线性约束为 $g_ 1 = -2 \leq 0$（已满足），$g_ 2 = -1 \leq 0$（已满足）。子问题为 $\min -4d_ 1 - 2d_ 2$，信任域内整数解为 $d=(1,1)$，得 $x^{(1)} = (1,1)$。迭代2 ：$x^{(1)} = (1,1)$，梯度 $\nabla f(1,1) = [ -2, 0]^T$，约束仍满足。子问题解 $d=(1,0)$，得 $x^{(2)} = (2,1)$（最优解）。验证约束：$g_ 1(2,1)=1 \leq 0$（不满足！）需退回并调整信任域。调整：在 $x^{(1)}$ 处缩小信任域，求解得 $d=(0,0)$，算法终止。最终解为 $x^* = (1,1)$，$f^* = 1$。关键点线性化需在整数点进行，信任域控制线性近似有效性。整数约束使问题非凸，解可能为局部最优。若线性化导致约束冲突，需缩小信任域重新求解。