Nonlinear Programming Basics: KKT Conditions Guide

Nonlinear programming (NLP) minimizes or maximizes a nonlinear objective subject to constraints that may also be nonlinear. Once anything curves, the corner-point logic of linear programming no longer applies, and optimality needs a more general test.

The Karush-Kuhn-Tucker (KKT) conditions are that test: equations and inequalities any local optimum must satisfy when the problem is smooth and a mild regularity condition holds. They generalize Lagrange multipliers from equality constraints to inequality constraints, where most real problems live.

Key Concepts

• Objective f(x) to minimize; inequality constraints g_i(x) ≤ 0; equality constraints h_j(x) = 0.
• Lagrangian: L(x, λ, μ) = f(x) + Σ λ_i g_i(x) + Σ μ_j h_j(x), folding constraints into the objective with multipliers λ (inequalities) and μ (equalities).
• Complementary slackness: λ_i · g_i(x) = 0, so a multiplier is positive only when its constraint is exactly binding; a slack constraint contributes nothing.
• Constraint qualification: a regularity condition, e.g. gradients of active constraints being linearly independent, needed for KKT to be valid.
• Necessary vs sufficient: KKT is necessary for a local optimum under a constraint qualification, and sufficient only when f and g_i are convex and each h_j is affine.

Formulas

For minimize f(x) subject to g_i(x) ≤ 0 and h_j(x) = 0, the KKT conditions at x* with multipliers λ, μ are: stationarity: ∇f(x*) + Σ λ_i ∇g_i(x*) + Σ μ_j ∇h_j(x*) = 0; primal feasibility: g_i(x*) ≤ 0, h_j(x*) = 0; dual feasibility: λ_i ≥ 0; complementary slackness: λ_i · g_i(x*) = 0. Equality multipliers μ_j are unrestricted in sign. Smoothness and a constraint qualification are assumed; without convexity these identify candidates, not guaranteed global optima.

Worked Example

Minimize x² + y² subject to x + y ≥ 2, i.e. g(x, y) = 2 − x − y ≤ 0. The Lagrangian is L = x² + y² + λ(2 − x − y). Stationarity: 2x − λ = 0 and 2y − λ = 0, so x = y = λ/2. Complementary slackness gives two cases. Case 1: λ = 0 forces x = y = 0, but g(0, 0) = 2 > 0 violates primal feasibility, so reject it. Case 2: the constraint binds, 2 − x − y = 0. Then λ/2 + λ/2 = 2 gives λ = 2, x = 1, y = 1. Check: λ = 2 ≥ 0 (dual feasibility), the constraint holds with equality, and ∇f = (2, 2) plus λ∇g = 2(−1, −1) sums to zero. The optimum is (1, 1) with value 2, the closest point on the line x + y = 2 to the origin.

Common Misconceptions

• Satisfying KKT guarantees an optimum. In non-convex problems KKT points can be saddle points; the conditions are necessary, not sufficient, without convexity.
• Inequality multipliers can be negative. For minimization with ≤ constraints, λ_i ≥ 0; the sign encodes that tightening a binding constraint cannot improve the objective.
• KKT is only about equalities. Lagrange multipliers handle equalities; the KKT extension to inequalities, via complementary slackness, is what makes it powerful.

Real-World Applications

KKT conditions underpin support vector machines, portfolio optimization with position limits, structural and aerodynamic design, economic models of constrained choice, and power-system dispatch. Every constrained nonlinear solver uses KKT as its stopping test.

The KKT conditions turn "is this point optimal?" into five checkable statements about gradients, feasibility, multiplier signs, and complementary slackness: the central optimality test of nonlinear optimization.