## Definition **Lagrangian multipliers** are auxiliary variables that convert constrained optimisation problems into unconstrained ones. For equality constraints, the technique extends to inequalities via the [[KKT Conditions]]. ## Classical (Equality-Constrained) Problem $ \min_x f(x) \quad \text{subject to} \quad h_j(x) = 0, \, j = 1, \dots, m $ Define the **Lagrangian**: $ \mathcal{L}(x, \lambda) = f(x) + \sum_{j=1}^m \lambda_j h_j(x) $ Each multiplier $\lambda_j$ "prices" the constraint $h_j$. ## First-Order Necessary Conditions At a local minimum $x^*$ (with constraint regularity), there exist $\lambda^*$ such that: $ \nabla_x \mathcal{L}(x^*, \lambda^*) = \nabla f(x^*) + \sum_j \lambda_j^* \nabla h_j(x^*) = 0 $ and $ h_j(x^*) = 0 \quad \forall j $ The constraint gradients are *parallel* to the objective gradient — pointing in the same direction as the objective's steepest-ascent. ## Geometric Intuition At an optimum, moving in any direction allowed by the constraints doesn't decrease the objective. This means the objective's gradient must be a linear combination of constraint gradients (orthogonal to the constraint manifold). ## Interpretation of $\lambda$ $\lambda_j^*$ is the **shadow price** of constraint $j$: how much the optimal objective value would change per unit relaxation of the constraint. The principle of sensitivity analysis. ## Worked Example Minimise $x^2 + y^2$ subject to $x + y = 1$. Lagrangian: $\mathcal{L} = x^2 + y^2 + \lambda(x + y - 1)$. Stationarity: $2x + \lambda = 0$, $2y + \lambda = 0$, $x + y = 1$. Solving: $x = y = 1/2$, $\lambda = -1$. Optimal value $= 1/2$. The shadow price $\lambda = -1$ tells you: relaxing the constraint from $x+y=1$ to $x+y=1.1$ would decrease the optimal value by ~0.1. ## Connection to Duality The Lagrangian dual function: $ g(\lambda) = \min_x \mathcal{L}(x, \lambda) $ is a lower bound on the primal optimum. Maximising $g$ over $\lambda$ gives the **dual problem**. For convex problems, the dual optimum equals the primal optimum (strong duality). See [[Duality]]. ## Extension to Inequalities For inequality constraints $g_i(x) \leq 0$, multipliers $\mu_i \geq 0$ and additional **complementary slackness** conditions ($\mu_i g_i(x) = 0$) yield the [[KKT Conditions]]. ## Modern Uses - **SVM dual formulation.** Lagrange multipliers become the $\alpha_i$ in the dual; non-zero $\alpha_i$ correspond to support vectors. - **Lagrangian relaxation** in combinatorial optimisation — relax hard constraints via multipliers; solve easier problem; iteratively update multipliers. - **Augmented Lagrangian methods** — combine Lagrangian with penalty for better numerical behaviour. - **ADMM** (Alternating Direction Method of Multipliers) — distributed optimisation via Lagrangian decomposition. ## Related - [[KKT Conditions]] - [[Duality]] - [[Convex Optimization]] - [[Support Vector Machine]]