I have a problem that I can formulate as a matrix inequality $c_{min}\leq Ax\leq c_{max}$:
- $c_{min}$ and $ c_{max}$ are non-negative column vectors of length $m$.
- $A$ is a matrix of dimensions $m\times n$ containing positive values
- $x$ is a non-negative column vector of length $n$.
For example ($n=m=3$):
$$\left( \begin{array}{r} \alpha_{min} \\\beta_{min} \\\gamma_{min} \\\end{array}\right) \leq \left( \begin{array}{rrr} a_1 & a_2 & a_3 \\b_1 & b_2 & b_3 \\c_1 & c_2 & c_3 \\\end{array}\right) \left( \begin{array}{r} x_1 \\x_2 \\x_3\\\end{array}\right) \leq \left( \begin{array}{r} \alpha_{max} \\\beta_{max} \\\gamma_{max} \\\end{array}\right) $$
I would like to find out an equation or inequality that allows me to check, whether there exists a vector $x$ that satisfies the inequalities, given a set of $c_{min}$ and $c_{max}$. So instead of running an algorithm to find a solution and thereby showing solvability, I would like to reformulate the problem so that I can check if there exists a solution in a simpler way. Ideally this should be possible to solve efficiently using a computer.
For $n=m=1$ the problem is trivial:
$$\alpha_{min}\leq a_1\cdot x_1 \leq \alpha_{max}$$
So the limits for the vector $x$ (in this case the scalar $x_1$) would be $$ \frac{\alpha_{min}}{a_1}\leq x_1\leq\frac{\alpha_{max}}{a_1}$$ The resulting condition for solvability is therefore $$\alpha_{min} \leq \alpha_{max}$$
For the case $n=1$, $m=2$ the inequality becomes $$\left( \begin{array}{r} \alpha_{min} \\\beta_{min} \\\end{array}\right) \leq \left( \begin{array}{rrr} a_1 \\b_1 \\\end{array}\right) x_1 \leq \left( \begin{array}{r} \alpha_{max} \\\beta_{max} \\\end{array}\right) $$ so the condition for the existence of a solution is $$ max\left(\frac{\alpha_{min}}{a_1}, \frac{\beta_{min}}{b_1}\right)\leq min\left(\frac{\alpha_{max}}{a_1}, \frac{\beta_{max}}{b_1}\right) $$
For $n=2$, $m=1$:
$$ \alpha_{min} \leq \left( \begin{array}{rr} a_1 & a_2\\\end{array}\right) \left( \begin{array}{rr} x_1 \\ x_2 \\\end{array}\right) \leq \alpha_{max} $$ the condition again becomes $$\alpha_{min}\leq\alpha_{max}$$
For $n=2$, $m=2$ I have $$\left( \begin{array}{r} \alpha_{min} \\\beta_{min} \\\end{array}\right) \leq \left( \begin{array}{rrr} a_1 & a_2 \\b_1 & b_2 \\\end{array}\right) \left( \begin{array}{r} x_1 \\x_2 \\\end{array}\right) \leq \left( \begin{array}{r} \alpha_{max} \\\beta_{max} \\\end{array}\right) $$ and the inequalities become $$\alpha_{min}\leq a_1x_1+a_2x_2\leq \alpha_{max}$$ $$\beta_{min}\leq b_1x_1+b_2x_2\leq \beta_{max}$$ The solution space here will be a plane bounded by four to six lines, namely $$\alpha_{min}= a_1x_1+a_2x_2$$ $$a_1x_1+a_2x_2= \alpha_{max}$$ $$\beta_{min}= b_1x_1+b_2x_2$$ $$b_1x_1+b_2x_2= \beta_{max}$$ and potentially $$x_1=0$$ $$x_2=0$$ Now I think the easiest solutions to check are where $x_1$ or $x_2$ are zero. So if $$ max\left(\frac{\alpha_{min}}{a_i}, \frac{\beta_{min}}{b_i}\right)\leq min\left(\frac{\alpha_{max}}{a_i}, \frac{\beta_{max}}{b_i}\right) $$ is satisfied for i=1 or i=2, then there exists a solution. If that is not the case, then I would check the intersection points by solving $$ \left( \begin{array}{rrr} a_1 & a_2 \\b_1 & b_2 \\\end{array}\right) \left( \begin{array}{r} x_1 \\x_2 \\\end{array}\right) = \left( \begin{array}{r} \alpha \\\beta \\\end{array}\right) $$ where $\alpha,\beta$ are all combinations of limits (in this case four). So $$\left( \begin{array}{r} x_1 \\ x_2 \\\end{array}\right) = \left( \begin{array}{r} \frac{\alpha}{a_1}-\frac{a_1a_2\beta-b_1a_2\alpha}{a_1 \cdot det(A)} \\\frac{a_1\beta-b_1\alpha}{det(A)} \\\end{array}\right) $$ This should be an inexpensive computation I think. For the special case where $det(A)=0$, the intersection with $x_i=0$ has to be calculated and the overlap checked.
Now if $m$ increases, then the same procedure as for the $2\times 2$-case has to be applied for all combinations of two inequalities and each solution candidate checked against all other inequalities until a solution is found. Since the number of times the procedure has to be performed grows with $m(m-1)/2$ this becomes computationally infeasible fairly quick.
Is there some other easier way to calculate the solvability of such a system? How could I utilize the problem structure to extend this to $n>2$?