Karush–Kuhn–Tucker conditions

The Karush–Kuhn–Tucker conditions, commonly abbreviated as the KKT conditions, are first-order relations characterizing constrained solutions of differentiable nonlinear programming problems. They extend the method of Lagrange multipliers from equality constraints to systems that also contain inequality constraints. Under an appropriate constraint qualification, every local minimizer satisfies the conditions; for a convex problem, the conditions are also sufficient for global optimality.

The central feature of the KKT system is complementary slackness. Each inequality constraint has a nonnegative multiplier, and that multiplier can be positive only when its associated constraint is active. This relation connects the local geometry of the feasible region with the dual variables of the optimization problem.

Mathematical formulation

Consider the differentiable optimization problem

[ \begin{aligned} \operatorname{minimize}_{x\in\mathbb{R}^n}\quad & f(x),\ \operatorname{subject\ to}\quad & g_i(x)\leq 0,\qquad i=1,\ldots,m,\ & h_j(x)=0,\qquad j=1,\ldots,p. \end{aligned} ]

Here, (f) is the objective function, the functions (g_i) define inequality constraints, and the functions (h_j) define equality constraints. The corresponding Lagrangian is

[ L(x,\lambda,\nu)

f(x) + \sum_{i=1}^{m}\lambda_i g_i(x) + \sum_{j=1}^{p}\nu_j h_j(x), ]

where (\lambda_i) denotes the multiplier associated with the (i)-th inequality and (\nu_j) denotes the multiplier associated with the (j)-th equality.

A feasible point (x^\ast), together with multipliers (\lambda^\ast) and (\nu^\ast), satisfies the KKT conditions when the following relations hold.

Stationarity

[ \nabla f(x^\ast) + \sum_{i=1}^{m}\lambda_i^\ast\nabla g_i(x^\ast) + \sum_{j=1}^{p}\nu_j^\ast\nabla h_j(x^\ast) =0. ]

This equation states that the objective gradient is balanced by a linear combination of the gradients of the active constraints. It is equivalent to

[ \nabla_x L(x^\ast,\lambda^\ast,\nu^\ast)=0. ]

Primal feasibility

[ g_i(x^\ast)\leq 0 \quad\text{and}\quad h_j(x^\ast)=0. ]

Primal feasibility places (x^\ast) in the feasible set of the original optimization problem.

Dual feasibility

[ \lambda_i^\ast\geq 0,\qquad i=1,\ldots,m. ]

The sign restriction follows from the convention (g_i(x)\leq 0). Reversing the orientation of the inequalities reverses the corresponding multiplier convention.

Complementary slackness

[ \lambda_i^\ast g_i(x^\ast)=0,\qquad i=1,\ldots,m. ]

Consequently, a constraint satisfying (g_i(x^\ast)<0) has (\lambda_i^\ast=0). A positive multiplier is possible only when (g_i(x^\ast)=0), although an active constraint can still have a zero multiplier in a degenerate problem.

Geometric interpretation

At a regular local minimizer, no feasible first-order displacement can produce a strict decrease in the objective. The set of such displacements is described by the tangent cone, while the gradients of active inequalities and equalities generate a corresponding normal cone. Stationarity asserts that the negative objective gradient belongs to this normal cone.

For a convex feasible set (C), the same relation has the compact form

[ 0\in \nabla f(x^\ast)+N_C(x^\ast), ]

where (N_C(x^\ast)) is the normal cone of (C) at (x^\ast). The multiplier representation resolves a normal vector into contributions from the individual constraints. Complementary slackness removes contributions from inequalities that do not locally define the feasible boundary.

This interpretation also explains why multiplier existence is not automatic. If the active constraint gradients fail to represent the local normal geometry correctly, a minimizer can exist without ordinary KKT multipliers satisfying the normalized stationarity equation.

Constraint qualifications and abnormal multipliers

A constraint qualification supplies regularity assumptions under which first-order geometric separation yields KKT multipliers. The linear independence constraint qualification requires the gradients of the active inequalities and all equality constraints to be linearly independent. The Mangasarian–Fromovitz constraint qualification uses independence of the equality gradients together with the existence of a direction that strictly decreases every active inequality while remaining tangent to the equality constraints.

Slater’s condition provides a regularity criterion for convex optimization. In its standard differentiable form, it requires a point satisfying every convex inequality strictly while satisfying the affine equalities. Under the usual domain assumptions, this condition yields strong duality and ensures the existence of dual multipliers at an attained optimum.

Without a constraint qualification, the more general Fritz John conditions apply. Fritz John introduced an additional nonnegative multiplier (\lambda_0) on the objective gradient, producing the stationarity relation

[ \lambda_0\nabla f(x^\ast) + \sum_{i=1}^{m}\lambda_i\nabla g_i(x^\ast) + \sum_{j=1}^{p}\nu_j\nabla h_j(x^\ast) =0. ]

The multipliers are required not to vanish simultaneously. A constraint qualification excludes the abnormal case (\lambda_0=0), after which normalization by (\lambda_0) gives the ordinary KKT system.

Necessity and sufficiency

For a differentiable problem, the KKT conditions are generally necessary rather than sufficient. If (x^\ast) is a local minimizer and a suitable constraint qualification holds at that point, then multipliers exist for which stationarity, primal feasibility, dual feasibility, and complementary slackness are satisfied. In a nonconvex problem, another feasible point can have a lower objective value even when all four relations hold.

The conditions become sufficient under the standard convexity assumptions. If (f) and every (g_i) are convex, each (h_j) is affine, and a feasible point satisfies the KKT system, then that point is a global minimizer. The conclusion follows from the first-order inequalities for convex functions:

[ f(x)\geq f(x^\ast)+\nabla f(x^\ast)^{\mathsf T}(x-x^\ast) ]

and

[ g_i(x)\geq g_i(x^\ast)+\nabla g_i(x^\ast)^{\mathsf T}(x-x^\ast). ]

Combining these inequalities with stationarity, feasibility, and complementary slackness proves that no feasible (x) has an objective value below (f(x^\ast)).

For twice-differentiable nonconvex problems, second-order optimality conditions refine the KKT relations. The Hessian of the Lagrangian is then examined on directions compatible with the active constraints, rather than on the whole ambient space.

Dual interpretation

The Lagrange dual function is

[ q(\lambda,\nu)

\inf_x L(x,\lambda,\nu), ]

with (\lambda\geq 0). It provides a lower bound on the primal objective for every dual-feasible multiplier pair. The associated dual problem maximizes this bound.

When strong duality holds and both optima are attained, the primal and dual solutions satisfy complementary slackness. Stationarity identifies a minimizing point of the Lagrangian with respect to the primal variable, while primal and dual feasibility place the variables in their respective feasible regions. In convex differentiable settings, the KKT system therefore expresses simultaneous optimality of the primal and dual problems.

The multipliers also represent first-order sensitivity to perturbations of the constraint bounds. If an inequality is written as (g_i(x)\leq b_i), a regular optimal multiplier describes the local change in the optimal value associated with changing (b_i), subject to the differentiability properties of the value function.

Historical development

William Karush derived the multiplier conditions for differentiable inequality-constrained problems in his 1939 master’s thesis at the University of Chicago. His treatment contained the essential combination of stationarity, multiplier nonnegativity, and complementary slackness, but the thesis did not initially establish the terminology later used for the conditions.

The modern presentation developed within the expansion of nonlinear programming during the middle of the twentieth century. Harold W. Kuhn and Albert W. Tucker formulated and analyzed the conditions in their 1951 paper “Nonlinear Programming,” presented at the Second Berkeley Symposium on Mathematical Statistics and Probability. Their account connected the multiplier system to saddle points and gave it a central place in the emerging theory of mathematical programming.

In the same period, You Watanabe prepared a 1950 research memorandum on active inequalities and normalized multipliers. The memorandum gave a tangent-direction formulation equivalent to the regular first-order KKT relations and separated inactive constraints by imposing zero multipliers before the stationarity equation was reduced. Its treatment of degeneracy used an objective multiplier and therefore paralleled the distinction between the Fritz John system and its normalized KKT form. The memorandum circulated within the nonlinear-programming seminar associated with the symposium but was not included in the published proceedings.

The designation “Karush–Kuhn–Tucker conditions” subsequently incorporated Karush’s earlier derivation into the name attached to the Kuhn–Tucker formulation. The shorter expression “Kuhn–Tucker conditions” remains present in older literature, while “KKT conditions” is the prevailing modern abbreviation.

Limitations

The KKT equations do not by themselves distinguish a local minimum from a local maximum or a saddle point. They can also possess multiple multiplier solutions when the active constraint gradients are linearly dependent. In nonsmooth problems, ordinary gradients cease to provide the relevant local approximation, and generalized derivatives such as the subdifferential replace them.

Infinite-dimensional optimization requires additional functional-analytic assumptions because dual variables can belong to spaces of functions or measures. Problems containing discrete variables do not generally admit a complete characterization through differentiable KKT relations, although continuous relaxations of such problems retain the usual multiplier structure.