1) The theorem proves weak duality, which states that for any feasible primal solution x* and dual solution y*, the objective value of the primal c·x* is less than or equal to the objective value of the dual b·y*.
2) The proof shows that the primal objective xTc is less than or equal to the dual objective yTb by manipulating inequalities involving the primal and dual constraints and objectives.
3) Weak duality is of independent interest and can be applied to other optimization problems where strong duality may not hold.
1) The theorem proves weak duality, which states that for any feasible primal solution x* and dual solution y*, the objective value of the primal c·x* is less than or equal to the objective value of the dual b·y*.
2) The proof shows that the primal objective xTc is less than or equal to the dual objective yTb by manipulating inequalities involving the primal and dual constraints and objectives.
3) Weak duality is of independent interest and can be applied to other optimization problems where strong duality may not hold.
1) The theorem proves weak duality, which states that for any feasible primal solution x* and dual solution y*, the objective value of the primal c·x* is less than or equal to the objective value of the dual b·y*.
2) The proof shows that the primal objective xTc is less than or equal to the dual objective yTb by manipulating inequalities involving the primal and dual constraints and objectives.
3) Weak duality is of independent interest and can be applied to other optimization problems where strong duality may not hold.
1) The theorem proves weak duality, which states that for any feasible primal solution x* and dual solution y*, the objective value of the primal c·x* is less than or equal to the objective value of the dual b·y*.
2) The proof shows that the primal objective xTc is less than or equal to the dual objective yTb by manipulating inequalities involving the primal and dual constraints and objectives.
3) Weak duality is of independent interest and can be applied to other optimization problems where strong duality may not hold.
Theorem (Weak Duality) Let x∗ be a feasible solution to the primal and let y∗ be a feasible solution to the dual where max c·x min b·y T primal Ax ≤ b dual A y ≥ c. x≥0 y≥0
Then c · x∗ ≤ b · y∗ . Proof: We note that AT y ≥ c and x ≥ 0 yields xT AT y ≥ xT c which we write as c · x = xT c ≤ xT AT y. Similarly Ax ≤ b and y ≥ 0 yields yT Ax ≤ yT b which we write as yT Ax ≤ yT b = b · y. T T T Now xT AT y is a 1×1 matrix and so xT AT y = xT AT y = yT AT ( xT = yT Ax. We obtain
c · x = xT c ≤ xT AT y = yT Ax ≤ yT b = b · y.
We read off c · x ≤ b · y.
The case of equality is of course of great interest and Strong Duality and Complementary Slackness deal with equality. Nonetheless, Weak Duality is of independent interest and is a model for other optimization problems for which we have no Strong Duality.
