Duality and Lagrangian Methods

Corresponds to Chapter 10, plus the LP-duality/separation material from the Appendix (A.4–A.6). The Lagrangian turns a constrained problem into an unconstrained one in an extra (“dual”) set of variables, and the resulting dual problem always lower-bounds the primal (weak duality); under convexity and a constraint qualification, the bound is tight (strong duality), and the first-order (KKT) conditions characterize an optimal primal-dual pair exactly. The quadratic penalty function is a cruder, non-dual alternative (just add a penalty for violating constraints) useful as a warm-up or when duality doesn’t apply cleanly. Covers the resulting family of dual algorithms — dual subgradient ascent, the augmented Lagrangian method (penalty plus a dual update, more numerically stable than either alone), and ADMM (splitting a problem into two parts solved alternately, widely used for distributed/consensus optimization) — with applications to consensus optimization, utility maximization (the same object underlying introduction-to-mechanism-design‘s market and auction theory), and linear/quadratic programming. The appendix’s LP duality, theorems of the alternative, and hyperplane separation results are the classical finite-dimensional special case of this same duality theory, closely related to convex-analysis-for-bandits‘s projection and Legendre-function machinery.

Outline (TODO — flesh out each)

• The quadratic penalty function
• Lagrangians and duality
• First-order (KKT) optimality conditions
• Strong duality
• Dual subgradient ascent
• The augmented Lagrangian method
• The alternating direction method of multipliers (ADMM)
• Applications — consensus optimization, utility maximization, LP/QP
• LP duality and theorems of the alternative (Appendix)
• Separation results; limiting feasible directions (Appendix)