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$
    – mathreadler
    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$
    – Tobia Marcucci
    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$
    – Tobia Marcucci
    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

Reset to default

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.