1. The problem statement, all variables and given/known data

Weak Duality Theorem. If x ε ℝ^{n} is feasible for P and x ε ℝ^{m} is feasible for D, then

c^{T}x ≤ y^{T}Ax ≤ b^{T}y.

Thus, if P is unbounded, then D is necessarily infeasible, and if D is unbounded, then P is necessarily infeasible. Moreover, if c^{T}x = b^{T}y with x feasible for P and y feasible for D, then x must solve for P and y must solve for D.

2. Relevant equations

c ε ℝ^{n}, b ε ℝ^{m} A ε ℝ^{m x n}

P: maximize c^{T}x subject to Ax ≤ b, 0 ≤ x, where the inequalities Ax ≤ b are to be interpreted componentwise.

D: minimize b^{T}y subject to A^{T}y ≥ c, y ≥ 0.

3. The attempt at a solution

So the "proof" that follows in my course notes starts with

Then it basically gives a simple verification of the inequality and says that the other results obviously follow.

I'm confused by the logic here. The theorem starts by choosing x and y feasible for P and D. Then it states that if P is unbounded, the inequality shows that there could be no feasible y ........................ which is strange because the inequality only works for a feasible x and y.

The hypothesis for the theorem asserts that there exist x which is feasible for P and there exists y which is feasible for D. By that hypothesis, it is impossible for either P or D to be infeasible.

Can that be gathered from looking at the inequality? My point is that the inequality is only relevant for feasible x and y; hence I don't see how it illustrates a point about the infeasibility of y.

Look at what the Theorem says: it says IF x is feasible for P and y is feasible for D, then cx ≤ by. OK, so think about it: if P is unbounded, there cannot be any y that is feasible for D (because a feasible y produces an upper bound on cx for all feasible x). Similarly for the other part of the statement.

BTW: it is possible for both P and D to be infeasible, as some examples show.

The second part is not part of the main theorem, but is a sole consequence of the theorem. It does not really need a formal proof, since it is just a logical consequence of the theorem itself. The theorem implies that IF P and are both feasible, we have an upper bound on cx and a lower bound on by. Thus, if it happens that cx is unbounded it MUST be the case that D is i feasible (for when we sat that cx is unbounded we are implicitly assuming that P is feasible).