Consider the following standard form of an LP:

s.t.

The decision problem associated with this LP is the following: does there exist an such that and . To certify a yes instance, we can simply give as our certificate a solution such that and . To certify a no instance we will use the dual LP. Recall the dual form of the above LP:

**Weak LP Duality: **Let denote the optimal value of the primal program and let denote the optimal value of the dual program. We claim that (if the optima exist).

**Proof: **Let be a feasible solution of the primal and let be a feasible solution to the dual. Then .

**Farkas’ Lemma: **Let and then exactly one of the following holds:

- such that
- such that while

**Proof:** Let be the cone generated by the columns of . In other words if are the columns of , then . Suppose there exists an such that , then clearly . Note that is a convex set – since if then for any , since . From the homework, if , then such that and , where is the all ‘s vector. Note that cannot be positive. Suppose . We may raise till there must be some subset of columns of such that where . But then for a large enough , and scaling every column of by we get . This contradicts the fact that for any . Thus we may raise till it is equal to .

**Strong LP Duality: **If the primal and dual are feasible, then .

**Proof: **Let . Suppose there exists an such that

In this case we would be done. Let and . Then by Farkas’ lemma, either:

- such that , in which case we have an such that and .
- such that and . In this case, choose a feasible for the primal program. Then which implies (if ) that which contradicts weak duality. If then while which implies while . This contradicts optimality of . Thus this option is not possible.