## Definition **Duality** is the systematic association of every optimisation problem (the **primal**) with another problem (the **dual**) whose optimal value bounds the primal optimum. For convex problems with constraint qualifications, primal and dual optima coincide — yielding deep insights and practical algorithms. ## LP Duality For the primal LP: $ \min \, c^\top x \quad \text{s.t.} \quad A x \geq b, \, x \geq 0 $ the dual is: $ \max \, b^\top y \quad \text{s.t.} \quad A^\top y \leq c, \, y \geq 0 $ Each primal constraint → dual variable; each primal variable → dual constraint. ## Key Theorems ### Weak Duality For any feasible primal $x$ and dual $y$: $ c^\top x \geq b^\top y $ The primal min is bounded below by the dual max. Any feasible dual gives a *certificate* of how good the primal can be. ### Strong Duality For LP and convex problems with constraint qualifications: $ c^\top x^* = b^\top y^* $ The optima are equal. No duality gap. ### Complementary Slackness For optimal primal $x^*$ and dual $y^*$: - If a primal constraint is *slack* (not tight), the corresponding dual variable is zero. - If a dual constraint is slack, the corresponding primal variable is zero. This characterises optimality and underlies many algorithms. ## Lagrangian Duality (General Convex Problems) For a general problem: $ \min f(x) \quad \text{s.t.} \, g_i(x) \leq 0, \, h_j(x) = 0 $ The Lagrangian dual function: $ g(\mu, \lambda) = \min_x \mathcal{L}(x, \mu, \lambda) = \min_x f(x) + \sum_i \mu_i g_i(x) + \sum_j \lambda_j h_j(x) $ with $\mu \geq 0$. The dual problem: $ \max_{\mu \geq 0, \lambda} g(\mu, \lambda) $ Always *concave* (even when primal is not convex). Maximising gives a lower bound on primal. ## Why Duality Matters ### Bounds The dual gives a *certifiable* bound on the primal — useful when the primal is hard. ### Sensitivity Analysis Dual variables = **shadow prices**: marginal change in objective per unit change in constraint. Essential for understanding which constraints "matter". ### Algorithms - **Dual Simplex.** Solve the dual; convert back. Sometimes faster. - **Primal-dual interior-point methods.** Simultaneously update primal and dual variables. - **Lagrangian relaxation.** Move hard constraints into the objective; solve easier subproblems iteratively. - **ADMM.** Distributed optimisation via dual decomposition. ### SVM The SVM dual problem (Lagrangian dual of the margin-maximisation primal) is what gets solved in practice. Dual variables become the $\alpha_i$ coefficients — non-zero ones correspond to support vectors. ### Game Theory Zero-sum games' minimax equals maximin — a form of duality. ## When Duality Helps Most - Primal is hard, dual is easy — solve dual, recover primal. - Need bounds during branch-and-bound for integer programs. - Understanding sensitivity of optimum to constraints. ## Related - [[Linear Programming]] - [[Simplex Method]] - [[Lagrangian Multipliers]] - [[KKT Conditions]] - [[Convex Optimization]]