如何解决多变量欠定不等式系统

Question

我正在尝试找到解决线性不等式系统的方法，例如：

c>0
y+c<0
x+c>0
x+y+c<0
w+c>0
w+y+c>0
w+x+c>0
w+x+y+c<0

我没能找到一种快速的计算方法来解决它们。我试过使用 wolfram alpha。它适用于某些集合但不适用于其他集合。此外，我还尝试使用 matlab 的 solve 函数解决此类系统，但没有成功。非常感谢有关此事的任何帮助。

Answer 1

一般来说，欠定系统有无限解。但是，您可以搜索适应问题的最小解决方案。在这种情况下，您可以按以下步骤操作：

你首先向量化你的问题

x = [c y x w].';
M = [1 0 0 0
     1 1 0 0
     1 1 1 0
     1 0 0 1
     1 1 0 1
     1 0 1 1
     1 1 1 1];
y = [ 1 -1 1 -1 1 1 1 -1].';

您可以根据需要设置 y 的值。它们只需要满足不等式的条件（即 y(1)>0、y(2)<0、...）。现在你解决了under determined system Mx=y.

利用M的伪逆可以找到该系统的最小解。

x = M.'(M*M.')^(-1)*y;

如果您根据自己的限制选择了y，则该问题的解决方案也是您问题的解决方案。

如果您想要问题的最小解决方案，只需给 y 一个 epsilon 房间（但您应该对其进行解析计算）。

how to solve under-determined system of inequalities with multiply variables