Tuesday, 3 November 2015

Examples sheet 1 #4

There was some question in the class about a part of the argument. Consider \begin{align} \max\;\{\; & 0^T x:\,Ax=b,\, x\geq 0\;\} \tag{1} \\ \min\;\{\; & y^T b:\, y^T A\geq 0^T\;\} \tag{2} \end{align} If (1) is feasible then for feasible $x,y$ we have $y^T b= (y^T A) x\geq 0$, so (2) is bounded.

On the other hand, if (2) is bounded then it is feasible and bounded. The strong duality theorem for linear programming states that (1) is feasible and bounded if and only if (2) is feasible and bounded. So (1) is feasible. This is enough to answer the question.

But how do we prove strong duality for linear programming? One way to prove it is via Farkas Lemma, which in the context of this question would be cheating. Another way is by appeal to the supporting hyperplane theorem and the sufficient conditions (satisfied by linear programs) for $\phi(b)$ to be convex.

I now think (c) of this question would be better phrased as "The Strong Duality theorem for linear programming states that if a linear programming problem is both feasible and bounded, then so is its dual." Show that this implies Farkas Lemma."