Farkas’ Lemma and Feasibility
At the end of lecture, we went over the discussion of infeasibility a bit fast. Here’s a longer discussion, which is particlarly useful in case you have not seen this before. Suppose we have an LP:
If this is feasible, I can prove this to you by giving you a feasible $x$. But what if this LP is not feasible? How do I prove it to you? Suppose I show you a vector $p \in \mathbb{R}^m$, such that $y \geq \mathbf{0}$, and
In this case I claim the LP is infeasible, there are no points $x$ that satisfy $Ax \geq b, x \geq 0$. Why? If there were, then left-multiplying by $p^\intercal$ would give
(Here we used that $p$ was non-negative, so multiplying by it did not flip the direction of the inequality.) But we know from $(\star)$ that $p^\intercal A \geq \mathbf{0}$, and $p^\intercal b > 0$, so this is impossible. Hence exhibiting such a vector $p \in \mathbb{R}^m$ shows that an LP is infeasible.
In fact, Farkas’ Lemma from 1894 says that this is an if-and-only-if statement. The above argument says that if there exists such a vector, the LP is infeasible. A more surprising fact is the converse: if the LP is infeasible, there always exists such a vector $p$ that is a witness of infeasibility. Equivalently, if there does not exist such a vector $p$, the LP must be feasible.
In fact, today’s discussion indicated another proof of this. Basically, suppose that for some vector $p^t$ produced by Hedge we could not find a solution to the “average LP” $(p^t)^\intercal A x \leq (p^t)^\intercal b$ we produced. Then the above argument shows that the LP must be infeasible. And conversely, suppose we could always find a solution $x^t$ to the “average” LP. Then we saw that for any $\varepsilon > 0$, there was a time $T$ after which $\hat{x} := \frac1T \sum_{t = 1}^t x^t$ gives a solution $\hat{x} \geq 0$ for which $A \hat{x} \geq b - \varepsilon \mathbf{1}$. We claim that when $\varepsilon$ is small enough, then we can “round” $\hat{x}$ to a bonafide solution $\bar{x}$, thereby showing that the LP is feasible, and proving the second part of Farkas’ lemma. (Details on this “rounding” to come some other day.)