如何将二次转换为线性程序？-Java 学习之路

我有一个优化问题，在目标函数2中有多个变量，使模型呈二次方 .

我目前正在使用zimpl来解析模型，并使用glpk来解决它 . 由于它们不支持二次规划，我需要将其转换为MILP .

. 第一个变量是实数，在[0,1]范围内，第二个变量是实数，范围从0到inf . 这个可以没有问题是整数 .

目标函数中的关键部分如下所示：

max ... + var1 * var2 + ...

我在约束中遇到了类似的问题，但它们很容易解决 .

我怎样才能在目标函数中解决这类问题？

1 回答

13
这种形式的模型实际上称为双线性优化问题 . 线性化双线性项的典型方法是通过称为McCormick包络的方法 .

考虑变量x和y，您希望在最大化问题的目标中使用 x*y . 如果我们假设x和y受 xL <= x <= xU 和 yL <= y <= yU 的限制，那么我们可以用数量的上限 w 替换 x*y ，具有以下约束（您可以看到派生here）：
```
w <= xU*y + x*yL - xU*yL
w <= x*yU + xL*y - xL*yU
xL <= x <= xU
yL <= y <= yL
```
请注意，这些约束在决策变量中都是线性的 . McCormick信封中有相应的下限，但由于你最大化它们在你的情况下并不重要 .

如果你想在 x*y 上有一个更严格的界限，你可以在其中一个变量上分割间隔（I 'll use x here) into ranges [xL1, xU1], [xL2, xU2], ..., [xLn, xUn], introducing auxiliary continuous variables {x1, x2, ..., xn} and {w1, w2, ..., wn} as well as auxiliary binary variables {z1, z2, ..., zn}, which will indicate which range of x values was selected. The constraints above could be replaced by (I' ll显示索引1的情况，但是对于所有n个索引你需要这些）：
```
w1 <= xU1*y + x1*yL - xU1*yL*z1
w1 <= x1*yU + xL1*y - xL1*yU*z1
xL*z1 <= x1 <= xU*z1
```
基本上，只要z1 = 0（也就是未选择范围的这一部分），你就会得到x1 = 0和w1 <= 0，如果z1 = 1，你将拥有正常的麦考密克包络（也就是这部分范围被选中） .

最后一步是从这些变量的范围特定版本生成x和w . 这可以通过以下方式完成：
```
x = x1 + x2 + ... + xn
w = w1 + w2 + ... + wn
```
你做出的n越大，你对双线性项的估计就越准确 . 但是，大的n值会影响求解模型的可追溯性 .

最后一个注意事项 - 你指出你的一个变量是无界的，但麦考密克包络需要两个变量的界限 . 您应该修复边界，求解，如果您的最佳值在边界处，那么您应该使用不同的边界重新求解 .
回复于 2024-05-03T03:58:06+08:00

如何将二次转换为线性程序？

1 回答

相关问题