# Lecture 13: Duality in Linear Programming Source: https://www.youtube.com/watch?v=oyVZ3rao6M4 Recap page: https://rapidrecap.app/video/oyVZ3rao6M4 Generated: 2025-12-17T16:37:12.838+00:00 --- ## 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 y_i = 0 or A_i x = b_i, and for all j, either x_j = 0 or A^T y_j = c_j. - 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 y_i) 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. ## Detailed Analysis The lecture begins by reiterating the canonical form for a primal LP (maximization, Ax <= b, x >= 0) and its dual (minimization, A^T y >= c, y >= 0), noting that weak duality holds: c^T x <= b^T y for any feasible solutions. Shor outlines the three possibilities for an LP: finite optimum, infeasible (e.g., x1 >= 5 and x1 <= 3), or unbounded. A direct consequence of weak duality is that unboundedness in one implies infeasibility in the other. The instructor then demonstrates deriving the dual for a non-canonical example, emphasizing a preferred method: first standardize constraints to match the primal maximization form (Ax <= b) or, if necessary, flip signs, which dictates the sign constraints on the dual variables (e.g., <= yields y >= 0, >= yields y <= 0, = yields y unconstrained). He then introduces complementary slackness: optimality is achieved if, for every constraint/variable pair, either the slack is zero or the corresponding dual variable is zero, which is proven for canonical forms. Finally, Shor provides a justification for strong duality by relating LP minimization to a physical system where a ball settles at the lowest point defined by hyperplanes; the forces exerted by the supporting hyperplanes (the dual variables y) must balance the force of gravity (the primal objective direction c), leading to A^T y = c and y >= 0. ### Canonical Duality - Primal max c^T x s.t. Ax <= b, x >= 0 yields Dual min b^T y s.t. A^T y >= c, y >= 0 - Weak duality states c^T x <= b^T y for feasible solutions - Unbounded primal implies infeasible dual. ### Deriving Duals for General Constraints - For maximization, <= constraint gives y_i >= 0 - >= constraint gives y_i <= 0 - = constraint gives y_i unconstrained - The preferred method involves first converting all primal constraints to <= form. ### Complementary Slackness Conditions - Primal x and dual y are optimal if for all i, either y_i = 0 or A_i x = b_i (equality in primal constraint) - and for all j, either x_j = 0 or A^T y_j = c_j (equality in dual constraint). ### Application of Complementary Slackness - If an optimal primal solution x is known (e.g., x1=4, x2=4, x3=0), non-zero x_j variables force corresponding dual constraints to be equalities, allowing the determination of the dual optimum. ### Justification for Strong Duality via Mechanics - Strong duality is justified by modeling the LP as a physical system where a ball settles under gravity (direction -c) against hyperplanes (constraints Ax >= b); the resulting forces y_i exerted by the hyperplanes must balance gravity, leading to summation y_i A_i = c, with y_i >= 0. ### Kőnig's Theorem Application - Kőnig's theorem (max matching size equals min vertex cover size in bipartite graphs) is shown to be a consequence of LP duality, where integer solutions exist for both the max matching primal LP and its dual LP.