1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jul 25, 2012 #1
    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. jcsd
  3. Jul 25, 2012 #2


    User Avatar
    Science Advisor

    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.
  4. Jul 25, 2012 #3
    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:

  5. Jul 25, 2012 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.

  6. Jul 25, 2012 #5
    Here's the logic of the first part of the theorem.

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

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

    (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.
  7. Jul 25, 2012 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

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

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook