python - 如何高效去除冗余线性约束进行优化？

Question

我的优化问题涉及数千个线性约束。我想通过找到冗余约束来降低问题的复杂性，例如3 * x + 4 * y < 10如果我已经有了 4 * x + 5 * 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

您可以将每个约束视为一个超平面，在(和约束常数)/(该轴的系数)处截取每个轴；如果系数为 0，则超平面平行于该轴(==“无穷远截距”)。

通常，如果一个超平面的轴截距都等于或大于另一个超平面的相应截距，则该超平面是多余的。

为了尽早剔除尽可能多的约束，您希望首先与超平面 (a) 尽可能靠近原点并且 (b) 平行于尽可能少的轴的超平面进行比较，因为它只能剔除也平行于该轴的其他超平面。 [不平行于给定轴的超平面可能能够剔除一个平行于该轴的超平面，但反之永远不会成立。]

我建议您按(轴平行轴的数量)然后(非无限轴截距的总和)对列表进行排序。