Lagrange Multipliers and KKT Conditions: Constrained Optimization and Duality

In physics, engineering, operations research, and machine learning (Support Vector Machines, Maximum Entropy models, portfolio optimization), optimization problems rarely occur without constraints. Resource bounds, energy limits, and regulatory boundaries restrict the space of allowable solutions.

The Method of Lagrange Multipliers and its generalization to inequality constraints—the Karush-Kuhn-Tucker (KKT) Conditions—provide the analytical foundation for solving non-linear constrained optimization problems.

1. Quick-Reference: Constrained Optimization Hierarchy

+-----------------------------------------------------------------------------------------------------------------------+
|                                           OPTIMIZATION PROBLEM TAXONOMY                                               |
+-----------------------------------------------------------------------------------------------------------------------+
| Problem Class          | Objective & Constraints                | First-Order Optimality     | Common Applications    |
+------------------------+----------------------------------------+----------------------------+------------------------+
| Unconstrained          | min f(x)                               | grad f(x) = 0              | Gradient Descent, OLS  |
| Equality Constrained   | min f(x) s.t. g(x) = 0                 | grad L(x, lambda) = 0      | Classical Mechanics    |
| General Non-Linear     | min f(x) s.t. g=0, h <= 0              | KKT Necessary Conditions   | SVMs, Optimal Control  |
| Convex Optimization    | Convex f, h + Affine g                 | KKT Necessary & Sufficient | Markowitz Portfolio Opt|
+-----------------------------------------------------------------------------------------------------------------------+

2. Geometric Intuition: Equality Constraints

Consider minimizing $f(x, y)$ subject to equality constraint $g(x, y) = c$ .

                 Level Curves of f(x, y) [f = 10, 20, 30]
                        /       /       /
                       /       /       /
           Constraint Curve g(x, y) = c
                     +--------*--------+
                              |
                    Tangency Point (x*, y*)
                    grad f = -lambda * grad g

At the optimal point $(x^*, y^*)$ , the level curve of the objective function $f$ must be tangent to the constraint contour $g = c$ . Their gradient vectors must be collinear:

abla f(x^*) + \lambda abla g(x^*) = 0

where $\lambda \in R$ is the Lagrange Multiplier.

3. The Karush-Kuhn-Tucker (KKT) Conditions

For a general non-linear optimization problem minimizing $f(x)$ subject to $g_i(x) = 0$ ( $i = 1, \dots, m$ ) and $h_j(x) \le 0$ ( $j = 1, \dots, p$ ), the Lagrangian Function is:

L(x, \lambda, \mu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \mu_j h_j(x)

The 4 KKT Invariants

Any local minimum $x^*$ must satisfy:

Stationarity: $abla_x L(x^*, \lambda^*, \mu^*) = 0$
Primal Feasibility: $g_i(x^*) = 0$ for all $i$ , and $h_j(x^*) \le 0$ for all $j$ .
Dual Feasibility: $\mu_j^* \ge 0$ for all $j$ .
Complementary Slackness: $\mu_j^* h_j(x^*) = 0$ for all $j$ .

References

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Kuhn, H. W., & Tucker, A. W. (1951). Nonlinear programming. Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.