Primer on Lagrangians

You typically have a function $f(\mathbf{x})$ to optimize (minimize or maximize), subject to constraints:

• Equality constraints: $g_i(\mathbf{x}) = 0$, for $i = 1, \dots, m$.
• Inequality constraints: $h_j(\mathbf{x}) \leq 0$, for $j = 1, \dots, n$.

The Idea

Lagrange multipliers introduce additional variables (multipliers) to incorporate constraints into the objective function. This creates a single "augmented" function, the Lagrangian:

$$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \lambda_i g_i(\mathbf{x}),$$

where $\lambda_i$ are the Lagrange multipliers for the equality constraints.

Procedure

1. Construct the Lagrangian: Combine $f(\mathbf{x})$ and $g_i(\mathbf{x})$ into $\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$.

2. Stationary Points: Find critical points by solving:

   $$\frac{\partial \mathcal{L}}{\partial \mathbf{x}} = 0 \quad \text{and} \quad \frac{\partial \mathcal{L}}{\partial \boldsymbol{\lambda}} = g_i(\mathbf{x}) = 0.$$

   This ensures gradients of the objective and constraints are aligned.

3. Solve: Solve the system of equations to find $\mathbf{x}$ and $\boldsymbol{\lambda}$.

Inequality Constraints (KKT Conditions)

For inequality constraints $h_j(\mathbf{x}) \leq 0$, introduce slackness conditions:

$$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = f(\mathbf{x}) + \sum_{i=1}^m \lambda_i g_i(\mathbf{x}) + \sum_{j=1}^n \mu_j h_j(\mathbf{x}),$$

where $\mu_j \geq 0$. The KKT conditions are:

1. $\nabla_\mathbf{x} \mathcal{L} = 0$,
2. $g_i(\mathbf{x}) = 0$,
3. $h_j(\mathbf{x}) \leq 0$,
4. $\mu_j h_j(\mathbf{x}) = 0$ (complementary slackness).

Geometric Insight

The Lagrange multiplier $\lambda_i$ measures the rate of change of the optimal $f(\mathbf{x})$ with respect to the constraint $g_i(\mathbf{x})$. Think of it as a "shadow price" or sensitivity factor.