Ayanna Trujillo

2022-06-26

Test if a system of linear inequalities has a solution.
system of linear inequalities $Ax>0$ where $A$ is a $m×n$ matrix with $m\ge n$. Is there a simple way to check whether it has a solution?
What if one of the columns of $A$ is parametrized? In a more general case, I have one of the columns of $A\left(t\right)$ as $a\left(t\right)=tv+w$, where $t\in \left[0,1\right]$. Is there a way to check whether all of the systems
$A\left(t\right)x>0,t\in \left[0,1\right]$
have a solution?

humbast2

Expert

Numerically solving the following linear program
$\begin{array}{ll}\text{minimize}& 0\\ \text{subject to}& \mathrm{A}\mathrm{x}\ge \epsilon {1}_{m}\end{array}$
should produce a solution or tell you that none exists. Pick a small $\epsilon >0$. If $m$ and $n$ are small enough, you could even use quantifier elimination.

Do you have a similar question?