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 > 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 ?
