如何检查是否存在满足一组线性不等式的解集?

How to check whether a solution set exists, which satisfies a set of linear inequalities?

是否有可能确定是否存在一组解决方案满足 Matlab 外部的一组线性不等式(以编程方式)只需 true/false 就足够了但是是否可以使用 JavaScript(最好是因为它只是一个小的工作原型)或者如果不是那么任何简单的 python 库?

我可以通过具有一些约束的自写函数来做到这一点,但该解决方案可能非常不稳定,因此在重新发明轮子之前需要一些专家的意见。

到目前为止,我对确定一组不等式的解集是否存在的理解如下:

假设不等式是:

y >= 2x + 1 
y <= 2x - 5
x >  1

在这里以 Y 为主题,我可以尝试将 X 的一些有限正值和 X 的一些有限负值(包括零)放在一起。

更简单地说,所有不等式的域是 [3,2,1,0,-1,-2,-3]

并将得到范围(每个不等式的 Y 值)

稍后将比较 Y 的所有值,并查看在给定的 X 值上是否存在某个交集区域。

例如:

   when X = 1 
   inequality 1 gives Y >= 3
   inequality 2 gives Y <= -3 
   inequality 3 says X >  1

所以 X = 1 没有找到任何共同点,我将移动到 X 的另一个值。

但我不太确定什么时候停止?每个方向上的一些值(正或负)是否会定义良好的约束并帮助我确定是否存在不等式的解决方案集?

因为不等式的重叠区域可以在图的一个角落,X域两边的几个初始值就可以证明它们是不相交的独立区域,但我们需要继续迭代可能是 X 的一个非常大的值,其中两个不等式都有一个重叠区域,有时即使这样它们也会不相交。

那么是否有已经编写的基本库或函数可以帮助我解决这个问题?或者如果不是,那么我解决这种情况的逻辑/理解是否正确?

不是 Matlab,而是 JavaScript 中的简单编程库。

后面的解会扩展到2个以上也可能是3个变量不等式

我的问题与 this question from past

我对求解数学方程式真的很陌生,因此我希望已经很好地解释了我的问题。

如果你有一组线性不等式,你只想知道它们是否可行,你可以形成一个简单的凸优化问题或简单的可行性问题。假设您有一个要检查解的变量向量 X = [x, y] 和一组线性不等式,每个形式的形式为 a1x + a2y <= b.

然后你基本上可以通过按行堆叠不等式来形成一个矩阵A和一个列向量B,这样A的每一行都有系数a1a2 对于每个不等式和 B 的相应行具有常量 b。请注意,最好对所有不等式使用 <=>=,因此相应地调整符号。

现在关注这个问题(假设所有不等式都是<=形式)。您想要解决以下优化问题,其中 objective 函数具有常数值 0。这也称为 feasibility 问题。

minimize    0
subject to  AX <= B

请注意,如果解(最小值)returns infinity,则表示不存在满足上述约束条件的X。如果求解器 returns 0(常量 objective 函数的值),则意味着至少有一个 X 满足约束条件。因此,您可以找到是否存在解决您的不平等问题的方法。

您可以为此使用 cvxpy 库。这是 python 中的一个不错的 tutorial。此外,cvxpy 库与 numpy 配合得很好,它会为您处理所有内部 solver 细节。您甚至可以限制您的变量 Xrealinteger 值,并根据线性不等式施加约束约束,例如 x + 0.y < = a