如何高效去除优化中的冗余线性约束？

Question

我的优化问题涉及成千上万的线性约束。我想通过找到冗余的约束来简化我的问题，比如说，如果我已经有一个约束是 4 * x + 5 * y < 10，那么 3 * x + 4 * y < 10 就是多余的（而且 x 和 y 都是大于等于0的，这在我的问题中是成立的）。

所以，我有一个numpy数组，里面存放着所有的系数，举个例子，它看起来像这样：

[[0.1, 3.0, 4.8, 0.2],
 [1.0, 4.7, 5.3, 0.1],
 [2.2, 4.3, 5.2, 1.1]]

这些代表了约束条件：

0.1 * w + 3.0 * x + 4.8 * y + 0.2 * z < 10
1.0 * w + 4.7 * x + 5.3 * y + 0.1 * z < 10
2.2 * w + 4.3 * x + 5.2 * y + 1.1 * z < 10

我该如何高效地找出哪些是冗余的呢？

我的常识告诉我可以用一个循环（伪代码的方式）：

for i, row1 in enumerate(array):
    for j, row2 in enumerate(array):
        if j > i:
            if all(row1 > row2):
                delete row

但是对于成千上万的约束来说，这样做太慢了。有办法加快速度吗？

Answer 1

我觉得为了加快这个问题的解决速度，你可以使用一种叫做回溯法的技巧。比如说，你可以一个一个地检查数组里的系数！如果你发现某个位置的值比其他位置的值小，你就可以停止检查，并把那一行删掉！

Answer 2

你可以把每个约束条件想象成一个超平面，它在每个坐标轴上的交点是（约束常数的总和）除以该坐标轴的系数；如果系数是0，那么这个超平面就和那个坐标轴平行（也就是说，它的交点在无穷远的地方）。

简单来说，如果一个超平面的所有坐标轴交点都大于或等于另一个超平面的对应交点，那么这个超平面就是多余的。

为了尽早去掉尽可能多的约束条件，你应该先比较那些超平面，它们（a）离原点尽量近，（b）尽量少和坐标轴平行，因为它们只能去掉其他也和那个坐标轴平行的超平面。[一个不和某个坐标轴平行的超平面可能能去掉一个和那个坐标轴平行的超平面，但反过来就不成立。]

我建议你先按照（和坐标轴平行的数量）排序，然后再按照（非无穷远的坐标轴交点的总和）排序。