Weak Duality Theorem (according to my course notes)

[Jamin2112]

Homework Statement

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

c^Tx ≤ y^TAx ≤ b^Ty.

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

Homework Equations

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

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

D: minimize b^Ty subject to A^Ty ≥ c, y ≥ 0.

The Attempt at a Solution

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

Let x ε ℝⁿ be feasible for P and y ε ℝ^m be feasible for D.

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.Could someone clear this up for me?

 

[HallsofIvy]

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.

 

[Jamin2112]

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.

From my course notes:

 

[Ray Vickson]

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.

From my course notes:

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.

RGV

 

[Jamin2112]

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.

RGV

Here's the logic of the first part of the theorem.

Premises:
(1) Ax ≤ b
(2) A^Ty ≤ c
Logical Consequence:
c^Tx ≤ b^Ty.

Here's the logic of the second part of the theorem:

Premises:
(1) For all M ε ℝ there exists an x ε ℝⁿ such that c^Tx > M.
Logical Consequence:
There exists no y ε ℝ^m such that A^Ty ≤ b.


Those seem like unrelated parts of the theorem, each requiring it's own proof. Maybe I'll need to look at it more closely.

 

[Ray Vickson]

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).

RGV