1

I have a system of inequalities of the form:

$$ X \cdot v_i \leq 0 $$

For some number of vectors $v_i$.

I need to determine if there exists at least one $X$ that can satisfy all of them at once (I don't need to find $X$ I just need to know if it exists).

I need to be able to do this computationally, so graphing the solution won't really work.

$X$ is a vector of the same dimension as $v_i$ for all $i$.

Makogan
  • 3,329
  • Can't you just feed the system to a linear solver and check if the solver finds a solution or not ? – Kuifje Aug 02 '23 at 08:53
  • Is $X$ a vector? a number? a matrix? Has fixed dimensions? – Exodd Aug 02 '23 at 08:59
  • @Kuifje This is an over constrained system of inequalities, there may be no solution to the equality while there being a solution to the inequalities. Moreover there's always the trivial solution of $X=0$ but that isn;t ssuper useful to me. – Makogan Aug 02 '23 at 18:20
  • @Exodd I edited the questio, yes $x$ has fixed dimension. – Makogan Aug 02 '23 at 18:20
  • 1
    Weeelll... $X=0$ is always a solution... – Exodd Aug 02 '23 at 20:54
  • @Exodd I did say that in my coment, as mentioned Ineed to know if there are more answer than the trivial one. – Makogan Aug 02 '23 at 22:58
  • You should explicitely mention this in your question. – Kuifje Aug 03 '23 at 08:49

1 Answers1

1

Let $X=\matrix(x_1,...,x_n)\in \mathbb{R}^+\times ... \times \mathbb{R}^+$ denote your variables and $V=\matrix(v_1,...,v_n)$ denote the parameters.

You want to know if the following system has a solution: \begin{align} \sum_{i=1}^nx_iv_i &\le 0 \tag{1}\\ \end{align}

You can feed this to any linear solver (see for example PuLP) with a dummy objective function (e.g. $0$), and the solver will either find a solution, or tell you that the system is not feasible. So calling the solver will give you your certificate.

If your variables are not restricted to non negative values, perform the change of variables ($x_i=x_i'-x_i{''}$) to have this restriction, as explained for example here.

If you want at least one non negative element, then add the constraint $$ \sum_{i=1}^n x_i \ge \epsilon $$ where $\epsilon$ is your tolerance value.

Kuifje
  • 9,584