Let $E\subset{\mathbb R}^n$ be a set of the type $I\_1\times \dots \times I\_n$, where $I\_k$ are real intervals, and $X$ be and $n\times p$ real matrix. Suppose also that $rank(X)=p$ and $n>p$. Is there a quick way for checking whether the intersection between $E$ and the space generated by the columns of $X$ is empty or not?



Checking the intersection of two sets
[Emil Jeřábek posted a similar comment while I was writing this…]


Probably linear programming is the simplest way:


Let's say that $I\_i = [l\_i,u\_i]$. Now plug the following linear program into any linear programming solver:
$$
\min\_{x,y} 1\quad\text{such that}\quad l\_i\leq x\_i \leq u\_i,\quad \begin{bmatrix} X & -I\end{bmatrix}\begin{bmatrix} y\\x\end{bmatrix} = 0.
$$
If the solver reports infeasibility, then there is no $x$ in the range of $X$ that lies within the bounds given by the intervals, otherwise it should return some feasible vector.


Alternatively you also use alternating projections: Start with some vector $x$ and then perform projections onto $I\_1\times\cdots\times I\_n$ and the range of $X$ alternatively (the first is a simple clipping while the second is basic linear algebra). If the intersection is not empty, this will converge to something, otherwise, the method will end up alternating between two point that realize the distance of the two sets.


