# Is this a valid strong polynomial 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 \geq 0 \\ \textbf{1}^T \cdot q \geq 1\\ \textbf{1}^T \cdot q \leq 2 \end{cases}$$ Let $$q^{\star}$$ be the solution to the above problem.

The constraints are explained as follows: $$q \succeq 0, B^T \cdot q \geq 0$$ are due to Farkas lemma, $$1^T \cdot q \geq 1$$ makes sure that $$q = 0$$ is not the solution and $$1^T \cdot q \leq 2$$ makes sure that the search space is bounded. We have two possible outcomes:

a) $$d^{\star} = 0$$ hence $$q^{\star} \cdot A = 0$$, $$B^T \cdot q^{\star} \geq 0$$ therefore the system is NOT (strictly) 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}{1^T \cdot 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? Indeed, I think, initialize the ellipsoid with the ball $$\mathcal{B}(0, 2\cdot \sqrt{m})$$, hence in a number of steps which does not depend on $$A,B$$ its volume will decrease below some $$\epsilon > 0$$. 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 ?

This question is also here