Lagrange Multipliers

Constrained Optimization & The Lagrangian

Suppose you want to minimize loss $f(x)$ subject to equality constraint $g(x) = 0$:

$$\min_x f(x) \quad \text{subject to } g(x) = 0$$

   Objective Contours f(x) vs Constraint Surface g(x) = 0
   x2
    ▲         Constraint g(x) = 0
    │            \
    │      f=10   \   f=5    f=2
    │     .--------\---.----.---.
    │    /          \ (x*)   \   \
    │   (            *        )   )  <-- Tangent Point: ∇f(x*) = -λ ∇g(x*)!
    │    \          /        /   /
    └─────'────────/──'─────'───'────► x1
                  /

At the optimal constrained point $x^*$, contour lines of $f(x)$ are tangent to constraint curve $g(x) = 0$.

Their gradient vectors must point in the exact same (or opposite) direction:

$$\nabla f(x^) + \lambda \nabla g(x^) = 0$$

$$\text{Lagrangian Function: } \mathcal{L}(x, \lambda) = f(x) + \lambda g(x)$$

Setting $\nabla_{x, \lambda} \mathcal{L}(x, \lambda) = 0$ solves for optimal $x^*$ and multiplier $\lambda$ simultaneously!

Inequality Constraints & KKT Conditions

To handle inequality constraints $h_i(x) \le 0$:

$$\mathcal{L}(x, \lambda, \alpha) = f(x) + \sum_{j=1}^m \lambda_j g_j(x) + \sum_{i=1}^p \alpha_i h_i(x)$$

The Karush-Kuhn-Tucker (KKT) Conditions specify 4 mandatory requirements at optimum $x^*$:

1. Stationarity: $\nabla_x f(x^) + \sum \lambda_j \nabla g_j(x^) + \sum \alpha_i \nabla h_i(x^*) = 0$.
2. Primal Feasibility: $g_j(x^) = 0$ and $h_i(x^) \le 0$.
3. Dual Feasibility: $\alpha_i \ge 0$ for all inequality multipliers.
4. Complementary Slackness: $\alpha_i \cdot h_i(x^*) = 0$ for all $i$.

 Complementary Slackness α_i · h_i(x*) = 0:
 - If constraint is INACTIVE (h_i(x*) < 0 inside boundary) ──► Multiplier α_i MUST BE 0!
 - If Multiplier α_i > 0 ──► Constraint MUST BE ACTIVE (h_i(x*) = 0 directly on boundary!)

Application: Support Vector Machines (SVM)

SVM margin optimization uses KKT Complementary Slackness:

$$\alpha_i \left[ y_i (w^T x_i + b) - 1 \right] = 0$$

• For data points far away from the margin boundary ($y_i (w^T x_i + b) > 1$), multiplier $\alpha_i = 0$.
• Only data points lying directly on the margin boundary have non-zero multipliers $\alpha_i > 0$.

These non-zero points are the Support Vectors! The entire SVM decision boundary is defined exclusively by Support Vectors.

Say this out loud

Lagrange Multipliers solve constrained optimization by forming the Lagrangian L(x, λ) = f(x) + λ g(x). At optimal constrained points, ∇f is parallel to ∇g. For inequality constraints, the KKT conditions require stationarity, feasibility, and complementary slackness α_i h_i(x) = 0. In SVMs, complementary slackness proves that only Support Vectors lying on margin boundaries have non-zero multipliers α_i.

Follow-ups to expect

• What is Primal vs Dual Problem in SVMs? The Primal optimizes weights w in feature dimension d. The Dual optimizes Lagrange multipliers alpha_i in sample dimension N. When d >> N, solving the Dual formulation is faster and enables the Kernel Trick.
• What is the physical meaning of Lagrange Multiplier lambda? Lambda measures the sensitivity of optimal objective value f(x*) to changes in constraint limit c: lambda = - df*(c)/dc.