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:
- $\exists X \in \mathbb{R}^n$ such that $A\cdot X + B \preceq 0$
- $\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
