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

Question

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

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

。第一个变量是实数，范围为 [0, 1]，第二个变量是实数，范围为 0 到 inf。毫无疑问，这个数可以是整数。

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

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

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

如何解决目标函数中的此类问题？

Answer 1

这种形式的模型实际上称为双线性优化问题。线性化双线性项的典型方法是通过称为麦考密克包络线的方法。

考虑变量 x 和 y，您想要的位置 x*y在最大化问题的目标中。如果我们假设 x 和 y 的边界为 xL <= x <= xU和yL <= y <= yU ，那么我们可以替换x*y与 w ，数量的上限，具有以下约束(您可以看到推导 here ):

w <= xU*y + x*yL - xU*yL
w <= x*yU + xL*y - xL*yU
xL <= x <= xU
yL <= y <= yL

请注意，这些约束在决策变量中都是线性的。麦考密克包络线中有相应的下限，但由于您正在最大化它们在您的情况下并不重要。

如果您想对 x*y 进行更严格的限制，您可以将其中一个变量(我将在此处使用 x)的区间拆分为范围 [xL1, xU1], [xL2, xU2], ..., [xLn, xUn]，引入辅助连续变量 {x1 , x2, ..., xn} 和 {w1, w2, ..., wn} 以及辅助二进制变量 {z1, z2, ..., zn}，它们将指示选择的 x 值范围。上面的约束可以替换为(我将显示索引 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(又称为范围的这部分)，您将获得正常的 McCormick 包络被选中)。

最后一步是生成 x 和 w 超出这些变量的特定范围版本。这可以通过以下方式完成:

x = x1 + x2 + ... + xn
w = w1 + w2 + ... + wn

n 越大，双线性项的估计就越准确。然而，较大的 n 值会影响求解模型的易处理性。

最后一点——您表明变量之一是无界的，但 McCormick 包络线要求两个变量都有界。您应该修复边界并求解，如果您的最佳值位于边界处，那么您应该使用不同的边界重新求解。