6.251/15.081 Homework 4
Due Wednesday 10/9/02

Comments:

• 4.1 is a dull drill and need not be turned in. Just make sure you know how to form the dual.

• 4.10 suggests that duality theory has a deep connection with two-person zero-sum games (one player chooses x, the other chooses p), involving a payoff L(x,p) from one player to another. Curiously enough, game theoretic results (existence of a Nash equilibrium) predate the development of linear programming duality

• To get some perspective into 4.13, read the result of 4.12 (primal nondegeneracy implies uniqueness for the dual). This is proved in the text when the primal is in standard form. The converse (uniqueness in dual implies nondegeneracy of optimal primal solution) is *not* always true. But nondegeneracy together with uniqueness together in one problem imply the same for the other.

• Hint for 4.21. Express the statement "the feasible set is bounded" as a property of the optimal cost of a suitably designed LP.