# Strong polynomial time algorithm for deciding LP feasibility

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $$X \in \mathbb{R}^n$$ $$A\in \mathbb{R}^{m\times n}$$ and $$B \in \mathbb{R}^m$$ where $$m \geq n$$. According to Farkas lemma, exactly one of the following two is true:

1. $$\exists X \in \mathbb{R}^n$$ such that $$A\cdot X + B \preceq 0$$
2. $$\exists y \in \mathbb{R}^m_+$$ such that $$y^T \cdot A = 0$$ and $$y^T \cdot B > 0$$

Then lets define the convex optimization problem: $$d^{\star} = \min q^T \cdot A \cdot A^T \cdot q \\ s.t \begin{cases} q \succeq 0\\ B^T \cdot q > 0\\ \| q\| \leq 1 \end{cases}$$ Let $$q^{\star}$$ be the solution to the above problem.

We have two possible outcomes:

a) $$d^{\star} = 0$$ hence $$q^{\star} \cdot A = 0$$, $$B^T \cdot q^{\star} > 0$$ therefore the system is NOT feasible

b) $$d^{\star} > 0$$ hence $$\not \exists q \succeq 0$$ with $$q^T \cdot B > 0$$ and $$q^T \cdot A = 0$$ otherwise $$\frac{q}{\| q \|}$$ would vanish the above function, therefore yielding a smaller value than $$d^{\star}$$. It follows that the linear system HAS a solution

## Question

The above optimization problem can be solved with ellipsoid algorithm without dependency on the problem data, right? Of course, this does not yield the solution (to LP) but can decide if the LP is feasible or not, in polynomial complexity for real coefficients LP ?! What am I missing ?

## Update

In the above optimization problem we have $$B^T\cdot q > 0$$ generating an open set. It is obviously, not possible to ask just $$B^T \cdot q \geq 0$$ since this would automatically generate the trivial solution $$q = 0$$. Instead, I think that $$d^{\star} = \min q^T \cdot A \cdot A^T \cdot q \\ s.t \begin{cases} q \succeq 0\\ B^T \cdot q \geq 0 \\ \textbf{1}^T \cdot q \geq 1\\ \|q\| \leq \sqrt{m} \end{cases}$$ should solve some of the complaints. This prevents the solution $$q = 0$$ and has closed contraints set. However, here take $$\frac{q}{1^T \cdot q}$$ instead of $$\frac{q}{\|q\|}$$ in the interpretation of $$d^{\star} > 0$$. Am I missing something ?

• 1) If $B = 0$ the LP is trivial $X = 0$ is a solution, so I am assuming $\| B \| > 0$ Further more I think non-feasibility of the system of constraints (regarding $q$) will have the same consequence: the LP is feasible – C Marius Oct 22 '20 at 17:22
• We usually only deal with closed constraints, but $B^T \cdot q > 0$ isn't. – Yuval Filmus Oct 22 '20 at 17:29
• @yuvalFilmus can you please expand on that? The constrained set should be closed, alright! But, that will not matter if the solution will not be on the frontier of the constrained set. Furthermore, will asking $B^T \cdot q > \epsilon$ help? – C Marius Oct 22 '20 at 17:36
• How small is $\epsilon$? – Yuval Filmus Oct 22 '20 at 17:36
• Well I am thinking, that if $\exists q_0^T \cdot A = 0$ and $q_0^T \cdot B > 0$ follows that $\epsilon < q_0^T \cdot B$, which of course will make $\epsilon$ dependent of the problem data! That is the reason for which I ask for strict inequality ... – C Marius Oct 22 '20 at 17:42