Karush–Kuhn–Tucker conditions

Necessary conditions

Suppose that the objective function ${\displaystyle f:{\mathbb{R}}^n\to \mathbb{R}}$ and the constraint functions ${\displaystyle g_i:{\mathbb{R}}^n\to \mathbb{R}}$ and ${\displaystyle h_j:{\mathbb{R}}^n\to \mathbb{R}}$ have subderivatives at a point ${\displaystyle x^{\ast }\in {\mathbb{R}}^n}$. If ${\displaystyle x^{\ast }}$ is a local optimum and the optimization problem satisfies some regularity conditions (see below), then there exist constants ${\displaystyle {\mu }_i(i=1,\dots ,m)}$ and ${\displaystyle {\lambda }_j(j=1,\dots ,\ell )}$, called KKT multipliers, such that the following four groups of conditions hold:

Stationarity

For minimizing ${\displaystyle f(x)}$: ${\displaystyle \mathrm{\partial }f(x^{\ast })+\sum _{j=1}^{\ell }{\lambda }_j\mathrm{\partial }{h}_j(x^{\ast })+\sum _{i=1}^m{\mu }_i\mathrm{\partial }{g}_i(x^{\ast })\ni \mathbf{0}}$

For maximizing ${\displaystyle f(x)}$: ${\displaystyle -\mathrm{\partial }f(x^{\ast })+\sum _{j=1}^{\ell }{\lambda }_j\mathrm{\partial }{h}_j(x^{\ast })+\sum _{i=1}^m{\mu }_i\mathrm{\partial }{g}_i(x^{\ast })\ni \mathbf{0}}$

Primal feasibility

${\displaystyle h_j(x^{\ast })=0,\text{ for }j=1,\dots ,\ell }$

${\displaystyle g_i(x^{\ast })\le 0,\text{ for }i=1,\dots ,m}$

Dual feasibility

${\displaystyle {\mu }_i\ge 0,\text{ for }i=1,\dots ,m}$

Complementary slackness

${\displaystyle \sum _{i=1}^m{\mu }_i{g}_i(x^{\ast })=0.}$

The last condition is sometimes written in the equivalent form: ${\displaystyle {\mu }_i{g}_i(x^{\ast })=0,\text{ for }i=1,\dots ,m.}$

In the particular case ${\displaystyle m=0}$, i.e., when there are no inequality constraints, the KKT conditions turn into the Lagrange conditions, and the KKT multipliers are called Lagrange multipliers.

Interpretation: KKT conditions as balancing constraint-forces in state space

The primal problem can be interpreted as moving a particle in the space of ${\displaystyle x}$, and subjecting it to three kinds of force fields:

• ${\displaystyle f}$ is a potential field that the particle is minimizing. The force generated by ${\displaystyle f}$ is ${\displaystyle -\mathrm{\partial }f}$.
• ${\displaystyle g_i}$ are one-sided constraint surfaces. The particle is allowed to move inside ${\displaystyle g_i\le 0}$, but whenever it touches ${\displaystyle g_i=0}$, it is pushed inwards.
• ${\displaystyle h_j}$ are two-sided constraint surfaces. The particle is allowed to move only on the surface ${\displaystyle h_j}$.

Primal stationarity states that the "force" of ${\displaystyle \mathrm{\partial }f(x^{\ast })}$ is exactly balanced by a linear sum of forces ${\displaystyle \mathrm{\partial }{h}_j(x^{\ast })}$ and ${\displaystyle \mathrm{\partial }{g}_i(x^{\ast })}$.

Dual feasibility additionally states that all the ${\displaystyle \mathrm{\partial }{g}_i(x^{\ast })}$ forces must be one-sided, pointing inwards into the feasible set for ${\displaystyle x}$.

Complementary slackness states that if ${\displaystyle g_i(x^{\ast })<0}$, then the force coming from ${\displaystyle \mathrm{\partial }{g}_i(x^{\ast })}$ must be zero i.e., ${\displaystyle {\mu }_i(x^{\ast })=0}$, since the particle is not on the boundary, the one-sided constraint force cannot activate.

Matrix representation

The necessary conditions can be written with Jacobian matrices of the constraint functions. Let ${\displaystyle \mathbf{g}(x):{\mathbb{R}}^n\to {\mathbb{R}}^m}$ be defined as ${\displaystyle \mathbf{g}(x)={\left(g_1(x),\dots ,g_m(x)\right)}^{\mathrm{\top }}}$ and let ${\displaystyle \mathbf{h}(x):{\mathbb{R}}^n\to {\mathbb{R}}^{\ell }}$ be defined as ${\displaystyle \mathbf{h}(x)={\left(h_1(x),\dots ,h_{\ell }(x)\right)}^{\mathrm{\top }}}$. Let ${\displaystyle \mathit{\mu }={\left({\mu }_1,\dots ,{\mu }_m\right)}^{\mathrm{\top }}}$ and ${\displaystyle \mathit{\lambda }={\left({\lambda }_1,\dots ,{\lambda }_{\ell }\right)}^{\mathrm{\top }}}$. Then the necessary conditions can be written as:

Stationarity

For maximizing ${\displaystyle f(x)}$: ${\displaystyle \mathrm{\partial }f(x^{\ast })-D\mathbf{g}(x^{\ast }{)}^{\mathrm{\top }}\mathit{\mu }-D\mathbf{h}(x^{\ast }{)}^{\mathrm{\top }}\mathit{\lambda }=\mathbf{0}}$

For minimizing ${\displaystyle f(x)}$: ${\displaystyle \mathrm{\partial }f(x^{\ast })+D\mathbf{g}(x^{\ast }{)}^{\mathrm{\top }}\mathit{\mu }+D\mathbf{h}(x^{\ast }{)}^{\mathrm{\top }}\mathit{\lambda }=\mathbf{0}}$

Primal feasibility

${\displaystyle \mathbf{g}(x^{\ast })\le \mathbf{0}}$

${\displaystyle \mathbf{h}(x^{\ast })=\mathbf{0}}$

Dual feasibility

${\displaystyle \mathit{\mu }\ge \mathbf{0}}$

Complementary slackness

${\displaystyle {\mathit{\mu }}^{\mathrm{\top }}\mathbf{g}(x^{\ast })=0.}$

Regularity conditions (or constraint qualifications)

One can ask whether a minimizer point ${\displaystyle x^{\ast }}$ of the original, constrained optimization problem (assuming one exists) has to satisfy the above KKT conditions. This is similar to asking under what conditions the minimizer ${\displaystyle x^{\ast }}$ of a function ${\displaystyle f(x)}$ in an unconstrained problem has to satisfy the condition ${\displaystyle \mathrm{\nabla }f(x^{\ast })=0}$. For the constrained case, the situation is more complicated, and one can state a variety of (increasingly complicated) "regularity" conditions under which a constrained minimizer also satisfies the KKT conditions. Some common examples for conditions that guarantee this are tabulated in the following, with the LICQ the most frequently used one:

The strict implications can be shown

LICQ ⇒ MFCQ ⇒ CPLD ⇒ QNCQ

and

LICQ ⇒ CRCQ ⇒ CPLD ⇒ QNCQ

In practice weaker constraint qualifications are preferred since they apply to a broader selection of problems.

Sufficient conditions

In some cases, the necessary conditions are also sufficient for optimality. In general, the necessary conditions are not sufficient for optimality and additional information is required, such as the Second Order Sufficient Conditions (SOSC). For smooth functions, SOSC involve the second derivatives, which explains its name.

The necessary conditions are sufficient for optimality if the objective function ${\displaystyle f}$ of a maximization problem is a differentiable concave function, the inequality constraints ${\displaystyle g_j}$ are differentiable convex functions, the equality constraints ${\displaystyle h_i}$ are affine functions, and Slater's condition holds. Similarly, if the objective function ${\displaystyle f}$ of a minimization problem is a differentiable convex function, the necessary conditions are also sufficient for optimality.

It was shown by Martin in 1985 that the broader class of functions in which KKT conditions guarantees global optimality are the so-called Type 1 invex functions.

Second-order sufficient conditions

For smooth, non-linear optimization problems, a second order sufficient condition is given as follows.

The solution ${\displaystyle x^{\ast },{\lambda }^{\ast },{\mu }^{\ast }}$ found in the above section is a constrained local minimum if for the Lagrangian,

${\displaystyle L(x,\lambda ,\mu )=f(x)+\sum _{i=1}^m{\mu }_i{g}_i(x)+\sum _{j=1}^{\ell }{\lambda }_j{h}_j(x)}$

then,

${\displaystyle s^T{\mathrm{\nabla }}_{xx}^{2}L(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast })s\ge 0}$

where ${\displaystyle s\ne 0}$ is a vector satisfying the following,

${\displaystyle {\left[{\mathrm{\nabla }}_x{g}_i(x^{\ast }),{\mathrm{\nabla }}_x{h}_j(x^{\ast })\right]}^{T}s=0_{{\mathbb{R}}^2}}$

where only those active inequality constraints ${\displaystyle g_i(x)}$ corresponding to strict complementarity (i.e. where ${\displaystyle {\mu }_i>0}$) are applied. The solution is a strict constrained local minimum in the case the inequality is also strict.

If ${\displaystyle s^T{\mathrm{\nabla }}_{xx}^{2}L(x^{\ast },{\lambda }^{\ast },{\mu }^{\ast })s=0}$, the third order Taylor expansion of the Lagrangian should be used to verify if ${\displaystyle x^{\ast }}$ is a local minimum. The minimization of ${\displaystyle f(x_1,x_2)=(x_2-x_1^2)(x_2-3x_1^2)}$ is a good counter-example, see also Peano surface.

Economics

Often in mathematical economics the KKT approach is used in theoretical models in order to obtain qualitative results. For example, consider a firm that maximizes its sales revenue subject to a minimum profit constraint. Letting ${\displaystyle Q}$ be the quantity of output produced (to be chosen), ${\displaystyle R(Q)}$ be sales revenue with a positive first derivative and with a zero value at zero output, ${\displaystyle C(Q)}$ be production costs with a positive first derivative and with a non-negative value at zero output, and ${\displaystyle G_{min}}$ be the positive minimal acceptable level of profit, then the problem is a meaningful one if the revenue function levels off so it eventually is less steep than the cost function. The problem expressed in the previously given minimization form is

Minimize ${\displaystyle -R(Q)}$

subject to

${\displaystyle G_{min}\le R(Q)-C(Q)}$

${\displaystyle Q\ge 0,}$

and the KKT conditions are

${\displaystyle \begin{array}{cc}& \left(\frac{\text{d}R}{\text{d}Q}\right)(1+\mu )-\mu \left(\frac{\text{d}C}{\text{d}Q}\right)\le 0,\\ & Q\ge 0,\\ & Q\left[\left(\frac{\text{d}R}{\text{d}Q}\right)(1+\mu )-\mu \left(\frac{\text{d}C}{\text{d}Q}\right)\right]=0,\\ & R(Q)-C(Q)-G_{min}\ge 0,\\ & \mu \ge 0,\\ & \mu [R(Q)-C(Q)-G_{min}]=0.\end{array}}$

Since ${\displaystyle Q=0}$ would violate the minimum profit constraint, we have ${\displaystyle Q>0}$ and hence the third condition implies that the first condition holds with equality. Solving that equality gives

${\displaystyle \frac{\text{d}R}{\text{d}Q}=\frac{\mu }{1+\mu }\left(\frac{\text{d}C}{\text{d}Q}\right).}$

Because it was given that ${\displaystyle \text{d}R/\text{d}Q}$ and ${\displaystyle \text{d}C/\text{d}Q}$ are strictly positive, this inequality along with the non-negativity condition on ${\displaystyle \mu }$ guarantees that ${\displaystyle \mu }$ is positive and so the revenue-maximizing firm operates at a level of output at which marginal revenue ${\displaystyle \text{d}R/\text{d}Q}$ is less than marginal cost ${\displaystyle \text{d}C/\text{d}Q}$ — a result that is of interest because it contrasts with the behavior of a profit maximizing firm, which operates at a level at which they are equal.

Value function

If we reconsider the optimization problem as a maximization problem with constant inequality constraints:

${\displaystyle \text{Maximize }f(x)}$

${\displaystyle \text{subject to }}$

${\displaystyle g_i(x)\le a_i,h_j(x)=0.}$

The value function is defined as

${\displaystyle V(a_1,\dots ,a_n)=\underset{x}{sup}f(x)}$

${\displaystyle \text{subject to }}$

${\displaystyle g_i(x)\le a_i,h_j(x)=0}$

${\displaystyle j\in \{1,\dots ,\ell \},i\in \{1,\dots ,m\},}$

so the domain of ${\displaystyle V}$ is ${\displaystyle \{a\in {\mathbb{R}}^m\mid \text{for some }x\in X,g_i(x)\le a_i,i\in \{1,\dots ,m\}\}.}$

Given this definition, each coefficient ${\displaystyle {\mu }_i}$ is the rate at which the value function increases as ${\displaystyle a_i}$ increases. Thus if each ${\displaystyle a_i}$ is interpreted as a resource constraint, the coefficients tell you how much increasing a resource will increase the optimum value of our function ${\displaystyle f}$. This interpretation is especially important in economics and is used, for instance, in utility maximization problems.

Generalizations

With an extra multiplier ${\displaystyle {\mu }_0\ge 0}$, which may be zero (as long as ${\displaystyle ({\mu }_0,\mu ,\lambda )\ne 0}$), in front of ${\displaystyle \mathrm{\nabla }f(x^{\ast })}$ the KKT stationarity conditions turn into

${\displaystyle \begin{array}{cc}& {\mu }_0\mathrm{\nabla }f(x^{\ast })+\sum _{i=1}^m{\mu }_i\mathrm{\nabla }{g}_i(x^{\ast })+\sum _{j=1}^{\ell }{\lambda }_j\mathrm{\nabla }{h}_j(x^{\ast })=0,\\ & {\mu }_j{g}_i(x^{\ast })=0,i=1,\dots ,m,\end{array}}$

which are called the Fritz John conditions. This optimality conditions holds without constraint qualifications and it is equivalent to the optimality condition KKT or (not-MFCQ).

The KKT conditions belong to a wider class of the first-order necessary conditions (FONC), which allow for non-smooth functions using subderivatives.