# Homework Help: Weak Duality Theorem (according to my course notes)

1. Jul 25, 2012

### Jamin2112

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

cTx ≤ yTAx ≤ bTy.

Thus, if P is unbounded, then D is necessarily infeasible, and if D is unbounded, then P is necessarily infeasible. Moreover, if cTx = bTy 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 cTx subject to Ax ≤ b, 0 ≤ x, where the inequalities Ax ≤ b are to be interpreted componentwise.

D: minimize bTy subject to ATy ≥ 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.

Could someone clear this up for me?

Last edited: Jul 25, 2012
2. Jul 25, 2012

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

3. Jul 25, 2012

### Jamin2112

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:

4. Jul 25, 2012

### Ray Vickson

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

5. Jul 25, 2012

### Jamin2112

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

Premises:
(1) Ax ≤ b
(2) ATy ≤ c
Logical Consequence:
cTx ≤ bTy.

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

Premises:
(1) For all M ε ℝ there exists an x ε ℝn such that cTx > M.
Logical Consequence:
There exists no y ε ℝm such that ATy ≤ 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.

6. Jul 25, 2012

### 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