1
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ What can be said about $E$? If it is just an arbitrary set, it will be hard to say if the intersection is empty. $\endgroup$ Sep 11, 2014 at 11:44
  • $\begingroup$ @MoritzFirsching $E$ is actually a square of the type $I_1\times \dots \times I_n$, where $I_k$ are real intervals. $\endgroup$
    – Linger
    Sep 11, 2014 at 11:51
  • $\begingroup$ This can be solved by linear programming. $\endgroup$ Sep 11, 2014 at 12:06
  • $\begingroup$ This is a convex feasibility problem and could be solved, e.g. by alternating projections. $\endgroup$
    – Dirk
    Sep 11, 2014 at 12:06
  • $\begingroup$ @EmilJeřábek Any chances of getting some details on this? It sounds interesting. $\endgroup$
    – Linger
    Sep 11, 2014 at 12:06

1 Answer 1

3
$\begingroup$

[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.

$\endgroup$
2
  • $\begingroup$ Of course, you could also use @EmilJeřábek's formulation and use the constraints $l\leq Xy\leq u$. $\endgroup$
    – Dirk
    Sep 11, 2014 at 12:32
  • $\begingroup$ Indeed, I will consider both (excellent) suggestions. $\endgroup$
    – Linger
    Sep 11, 2014 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.