Lecture 13: Duality in Linear Programming

Quick Overview

The lecture establishes the duality relationship between a primal linear program (LP) in canonical form (maximization, Ax <= b, x >= 0) and its dual (minimization, A^T y >= c, y >= 0), proves weak duality, explores the relationship between unboundedness/infeasibility, details a systematic method for deriving duals for non-canonical forms, introduces complementary slackness conditions for optimality, and justifies strong duality using a mechanical analogy involving forces balancing gravity on hyperplanes.

Key Points: The dual of the canonical primal maximization problem (max c^T x s.t. Ax <= b, x >= 0) is the minimization problem (min b^T y s.t. A^T y >= c, y >= 0). Weak duality states that for any feasible x in the primal and feasible y in the dual, "c transpose x is less than or equal to b transpose y." If the primal is unbounded, the dual must be infeasible, and similarly, if the dual is unbounded, the primal is infeasible. For non-canonical LPs, the speaker prefers transforming constraints into the canonical maximization form (all Ax <= b) first, noting that less than or equal to signs yield positive dual variables, greater than or equal to yield negative variables, and equality yields unconstrained variables. Complementary slackness theorem states that x is optimal for the primal and y is optimal for the dual if for all i, either yi = 0 or Ai x = bi, and for all j, either xj = 0 or A^T yj = cj. The speaker justifies strong duality using mechanics: treating hyperplanes as solid surfaces and gravity acting in the objective function's direction, where the sum of forces exerted by hyperplanes (represented by dual variables yi) balances the force of gravity (c).

Context: This lecture, titled "Lecture 13: Duality in Linear Programming," delivered by Peter Shor, systematically explores the fundamental concepts of duality in linear programming, starting from the definition of canonical forms and weak duality. The discussion progresses to the possible outcomes of LPs (finite optimum, infeasible, unbounded), deriving duals for general constraints, and proving the conditions under which primal and dual solutions are optimal via complementary slackness.