0
$\begingroup$

This sounds like a famous and straightforward question, but I do not know how exactly to solve it, although I have some rather half-baked ideas. I have already looked at these two answers, this and this, which are nice, but do not exactly answer my question.

I have a linear system of inequalities that I can probably rearrange to $ \mathbf{Ax} > \mathbf{b} $, and I am only interested to know the feasibility of the system, that is, yes or no.

In my particular problem, $ \mathbf{A} $ is a square matrix of reals ($ 8 \times 8 $). And there are no sign constraints on the elements of the vector $ \mathbf{x} $. And $ \mathbf{b} = \mathbf{0} $.

I am interested to know how exactly I need to reformulate the problem to be able to feed it to a Linear Programming solver to check for the feasibility of the system.

The issue with LP solvers is that they need an objective function. I know from the answers linked above that this feasibility problem can be converted to an optimization problem by replacing, for instance, the first element of $ \mathbf{b} $ (which is 0) by $ b_1 $, and then maximizing $ b_1 $ under the same constraints.

Now I have an objective function. If a nonnegative $ b_1$ was found, that is, $ b_1 \geqslant 0 $, then the system is feasible. Otherwise, it is not.

Any help, comment, or reference work about my analysis would be appreciated. Look at my specific problem.

$\endgroup$
  • $\begingroup$ You can always use the zero objective function. $\endgroup$ – Yuval Filmus Jun 9 '18 at 21:01
  • $\begingroup$ @YuvalFilmus I set objective function to zero and the solver gives me the trivial solution zero which is not even correct. because half of my constraints are strictly less than zero. (I used the R package lpSolve (originally lp_solve)) $\endgroup$ – Pooya Jun 9 '18 at 23:00
  • $\begingroup$ You cannot express strict constraints using linear programming. $\endgroup$ – Yuval Filmus Jun 9 '18 at 23:02
  • $\begingroup$ The solver found out that your program were feasible. It did its job. $\endgroup$ – Yuval Filmus Jun 9 '18 at 23:02
  • $\begingroup$ @YuvalFilmus I understand that you are saying theoretically strict constraints are not allowed. But the software allows for strict signs, < and >, in its documentation and throws no error when I use them. Yet again, the zero solution does not satisfy half of my constraints that are strictly less than zero (see problem picture at the bottom of question). $\endgroup$ – Pooya Jun 9 '18 at 23:20
1
$\begingroup$

Farkas' Lemma gives a criterion for the feasibility of the system $A\mathbf{x} = \mathbf{b}$, $\mathbf{x} \geq \mathbf{0}$, which is an equivalent problem to yours by adding slack variables. It states that such a solution exists if and only if the linear program \begin{align*} min. \, &\mathbf{b}^T\mathbf{y} \\ subject\,to\, &A^T\mathbf{y} \geq \mathbf{0}\end{align*} has a nonnegative optimum. See https://en.wikipedia.org/wiki/Farkas%27_lemma.

$\endgroup$
  • $\begingroup$ I think this worked. To transform my system of inequalities to the equivalent system of equations $ A \mathbf{x} = \mathbf{b}, \ \mathbf{x} \geqslant \mathbf{0} $, I needed to use slack and excess variables, fake strict constraints using a small $ \epsilon $, and substitute all unconstrained in sign variables $ \alpha_i $ with $ \alpha_i = \alpha'_i - \alpha''_i, \ \alpha'_i, \alpha''_i \geqslant 0 $. Thanks to Joshua and @YuvalFilmus. $\endgroup$ – Pooya Jun 12 '18 at 1:47

Your Answer

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

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