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


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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.