如何将二次规划转化为线性规划？

Question

如何将二次规划转化为线性规划？

mathematical-optimizationlinear-programminginteger-programmingquadratic-programming

17

我有一个优化问题，目标函数中有两个变量相乘，使得模型成为二次型。

我目前正在使用zimpl来解析该模型，并使用glpk来求解它。由于它们不支持二次规划，因此我需要将其转换为混合整数线性规划问题（MILP）。

第一个变量是实数，在[0,1]范围内，第二个变量是实数，在0到正无穷的范围内。这个变量可以很容易地转化为整数。

目标函数中关键部分的形式如下：

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

在约束条件方面我也遇到了类似的问题，但它们很容易解决。

我该如何解决目标函数中的这种问题呢？

- user4233758

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- josliber · Accepted Answer

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

考虑变量x和y，您希望在最大化问题的目标函数中使用x*y。如果我们假设x和y受到xL <= x <= xU和yL <= y <= yU的限制，则我们可以用以下约束条件（您可以在此处查看推导here）替换x*y为数量的上限w：

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

请注意，这些约束条件在决策变量中都是线性的。在 McCormick 包络中有相应的下界，但由于你正在最大化，它们在你的情况下不重要。

如果你想对 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包络需要对两个变量都设定边界。你应该设定边界、求解，如果最优值在边界上，则应该使用不同的边界重新求解。