15
$\begingroup$

What is the fastest way to check if there exists a solution to the inequality $A x \leq b$, with $A \in \mathbb R^{n \times m}$?

I know this can be checked through the phase 1 of a linear programming algorithm, but I would like to know if there exists a faster method. Please note that I do not actually need a feasible point, but I only need to know if there exists one.

If it helps, in my particular case, the set $\{ x : A x \leq b \}$ is a polytope (i.e. it is bounded) and $n > m$.

Thank you very much!

$\endgroup$
7
  • $\begingroup$ Maybe you could try $\displaystyle\min_x\|Ax-b-k1\|_2$ where 1 is the vector full of ones and $k$ is a real positive constant. I suppose if it would be faster than phase 1 of your linear programming method would depend a lot of how the matrix $A$ looks. $\endgroup$ Sep 29, 2017 at 18:53
  • $\begingroup$ Assuming for each line $A_i$ of $A$ the system $A_ix\leq b_i$ has a solution (i.e. whenever $A_i=0$ then $b_i\geq 0$), your question is equivalent to the following: check, whether or not the intersection of a given set of semi-spaces (the solutions of $A_ix\leq b_i$) is empty. are you searching for exact criteria or speed ups that only work in certain special cases? $\endgroup$
    – Max
    Sep 29, 2017 at 19:07
  • $\begingroup$ I'm not sure about the least squares approach: how am I supposed to understand if the polytope is empty from that? I get a zero residual only if there exists a point that is "distant $k$" from each facet, but this is a very particular case... $\endgroup$ Sep 29, 2017 at 20:22
  • 1
    $\begingroup$ Yes, I worked a lot on orthogonal projections of polytopes. But it's not clear to me how can I use Fourier-Motzkin here. Eliminating variables until I find a trivially unfeasible inequality? Thanks. $\endgroup$ Sep 30, 2017 at 14:28
  • $\begingroup$ @TobiaMarcucci Fourier-Motzkin is also how we (maths students) were introduced to linear optimization. We had to check whether a given polyhedron contains at least one point, and the solution was always Fourier-Motzkin. Of course, you can add a break for the contradiction case. $\endgroup$
    – Formyer
    Oct 9, 2017 at 3:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.