Karush–Kuhn–Tucker conditions

The Karush–Kuhn–Tucker conditions, usually abbreviated KKT conditions, are first-order optimality conditions in mathematical optimization for problems with equality and inequality constraints. They extend the method of Lagrange multipliers to inequality-constrained problems. Under an appropriate regularity assumption, every local minimizer satisfies them. In convex optimization, a point satisfying the conditions is a global minimizer, although additional assumptions are generally needed to guarantee that optimal points possess suitable multipliers. (stanford.edu)

Mathematical formulation

Consider the problem

Here $f$ is the objective function, and the constraints determine the feasible set in Euclidean space. Assume that the functions are continuously differentiable. Define the optimization Lagrangian by

The coefficients $\lambda_i$ and $\nu_j$ are inequality and equality multipliers, respectively. (stanford.edu)

A triple $(x^*,\lambda^*,\nu^*)$ satisfies the KKT conditions when all four requirements hold:

1. Stationarity

   $$\nabla f(x^*)+ \sum_i\lambda_i^*\nabla g_i(x^*)+ \sum_j\nu_j^*\nabla h_j(x^*)=0.$$

2. Primal feasibility

   $$g_i(x^*)\leq0,\qquad h_j(x^*)=0.$$

3. Dual feasibility

   $$\lambda_i^*\geq0.$$

4. Complementary slackness

   $$\lambda_i^*g_i(x^*)=0\qquad\text{for every }i.$$

The gradient in stationarity is taken with respect to $x$. Equality multipliers are unrestricted in sign. The nonnegative sign convention for inequality multipliers corresponds specifically to minimization with constraints written as $g_i\leq0$. (stanford.edu)

Geometric meaning

An inequality is active at a feasible point when $g_i(x)=0$, and inactive when $g_i(x)<0$. Complementary slackness forces every inactive inequality to have zero multiplier. Conversely, a positive multiplier implies an active constraint, but an active constraint may still have zero multiplier. Thus activity and positive multiplier status are not equivalent. (s3.amazonaws.com)

Stationarity expresses a balance between the objective gradient and the gradients of constraints. The negative objective gradient is a linear combination of equality-constraint gradients and a nonnegative combination of active inequality-constraint gradients. Under suitable regularity, this expresses the absence of a feasible first-order direction that decreases the objective. When there are no active inequalities, the formula reduces to the familiar equality-constrained multiplier condition; without any constraints, it becomes $\nabla f(x^*)=0$. (s3.amazonaws.com)

Necessity and constraint qualifications

Differentiability alone does not ensure that a local minimizer satisfies KKT. A constraint qualification controls how well the linearized constraints represent feasible directions. One common sufficient assumption is the linear independence constraint qualification (LICQ): the gradients of all equality constraints and all active inequality constraints are linearly independent. At a local minimizer satisfying LICQ, KKT multipliers exist and are unique. (ocw.mit.edu)

A simple calculated example demonstrates the difficulty without regularity:

The only feasible point, $x=0$, is necessarily the global minimizer. Nevertheless, stationarity would require

which becomes $1=0$. No KKT multiplier exists because the constraint gradient vanishes at the feasible point.

For nonconvex problems, satisfying KKT does not by itself establish a local minimum. Even an unconstrained maximum can have zero gradient. Additional second-order tests examine the Hessian matrix of the Lagrangian along suitable feasible directions. (ocw.mit.edu)

Convexity and duality

Suppose $f$ and every $g_i$ are convex functions, while the equality constraints are affine. Then any KKT triple certifies global optimality: stationarity makes $x^*$ minimize the convex Lagrangian, and feasibility together with complementary slackness identifies its value with the primal objective value. This sufficiency result does not require a constraint qualification. (web.stanford.edu)

Necessity is a separate question. Slater’s condition provides a standard sufficient assumption: a point in the relative interior of the common domain satisfies the equalities and all inequalities strictly. Under the usual finite-optimum assumptions, it ensures strong Lagrangian duality and the existence of optimal multipliers. KKT then characterizes primal–dual optimal solutions and corresponds to a saddle point of the Lagrangian. (web.stanford.edu)

For another calculated example,

stationarity gives $2(x-2)+\lambda=0$. The solution is $x^*=1$, $\lambda^*=2$: the constraint is active and all four conditions hold.

Computation and applications

KKT systems underpin constrained optimization algorithms. Interior-point methods solve perturbed complementary-slackness equations, approaching the original conditions as the perturbation decreases. Equality-constrained quadratic problems yield block matrix systems commonly called KKT systems. (web.stanford.edu)

In machine learning, KKT conditions help derive and interpret support vector machine solutions. Complementary slackness relates nonzero margin-constraint multipliers to training observations whose constraints are tight. In sensitivity analysis, optimal multipliers can describe how the optimal value changes when constraint bounds are perturbed, subject to the relevant differentiability assumptions. (stat.cmu.edu)

Historical development

William Karush obtained an early version in his 1939 master’s thesis at the University of Chicago. Harold W. Kuhn and Albert W. Tucker independently developed the conditions and published “Nonlinear Programming” in 1951, following their presentation at the Second Berkeley Symposium in 1950. The expanded name recognizes Karush’s earlier contribution. (citeseerx.ist.psu.edu)