Consider the following standard form of an LP:
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.