Constrained Optimization and Lagrange Multipliers

Real optimization problems often come with constraints: minimize $f(\mathbf{x})$ subject to $g_i(\mathbf{x}) = 0$ (equality) or $h_j(\mathbf{x}) \leq 0$ (inequality). Constraints restrict the feasible region, and the unconstrained optimum may lie outside it. The minimum on the feasible set may be anywhere — interior, on the boundary of one constraint, or at the intersection of several.

For equality constraints $g(\mathbf{x}) = 0$, the Lagrange multiplier technique reduces the constrained problem to an unconstrained one. Form the Lagrangian $\mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) + \lambda\, g(\mathbf{x})$ and find stationary points: $\nabla_{\mathbf{x}} \mathcal{L} = \nabla f + \lambda \nabla g = \mathbf{0}$ and $g(\mathbf{x}) = 0$. Geometrically, at the optimum, $\nabla f$ is parallel to $\nabla g$ — you can't reduce $f$ without violating the constraint.

For inequality constraints $h(\mathbf{x}) \leq 0$, we get the Karush–Kuhn–Tucker (KKT) conditions: stationarity $\nabla f + \sum \mu_j \nabla h_j = \mathbf{0}$, primal feasibility $h_j \leq 0$, dual feasibility $\mu_j \geq 0$, and complementary slackness $\mu_j h_j = 0$ (each constraint is either tight ($h_j = 0$) or has zero multiplier). The multipliers have an interpretation as 'shadow prices' — the rate of change of the optimal value as the constraint is relaxed.

Every constrained problem has a dual problem: $\max_{\lambda, \mu \geq 0} \min_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \lambda, \mu)$. Weak duality holds always: the dual objective lower-bounds the primal. Strong duality — equality between primal and dual optima — holds for convex problems under mild conditions. The dual is often easier to solve, and it exposes beautiful structure in many problems (SVMs are the textbook example).

In ML, constrained optimization is everywhere. SVMs solve a quadratic program with margin constraints, and their dual is where the kernel trick appears. Trust region methods use inequality constraints on step size. Proximal methods and ADMM solve constrained variants of common losses. Even fairness-aware learning and safe RL cast requirements as constraints. Knowing Lagrangians is knowing how to reason about 'what I want, subject to what I must'.

Worked example — inequality via KKT: Minimize $f(x) = (x-3)^2$ subject to $x \le 2$. Without the constraint the optimum is $x^* = 3$, but that's infeasible. KKT: stationarity $2(x-3) + \mu = 0$, feasibility $x \le 2$, slackness $\mu(x-2) = 0$. Set $x = 2$ (active constraint), giving $\mu = 2$. The shadow price $\mu = 2$ says relaxing the bound by $\Delta$ improves the objective by $\approx 2\Delta$.