= Karush-Kuhn-Tucker conditions
{c}
{title2=$\nabla_x L=0,\quad\lambda_i g_i=0$}
{wiki}
= KKT
{c}
{synonym}
= KKT conditions
{c}
{synonym}
The <Karush-Kuhn-Tucker conditions> combine membership of the <feasible set> with a balance of <gradients> and <complementary slackness>. For a <minimization problem> with <differentiable functions> on an <open subset> of $\mathbb R^n$, write
$$
\min_x f(x),\qquad g_i(x)\leq0\ (1\leq i\leq m),\qquad h_j(x)=0\ (1\leq j\leq p),
$$
and use the <optimization Lagrangian>
$$
L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m\lambda_i g_i(x)+\sum_{j=1}^p\mu_j h_j(x).
$$
A candidate $(x_*,\lambda,\mu)$ satisfies the <KKT conditions> exactly when all four requirements hold:
* Primal feasibility: $g_i(x_*)\leq0$ and $h_j(x_*)=0$, so $x_*$ is a <feasible point>.
* Dual sign feasibility: $\lambda_i\geq0$. The equality <Lagrange multipliers> $\mu_j$ are unrestricted <real numbers>.
* Stationarity: the <gradient> of the <optimization Lagrangian> in the decision variables vanishes,
$$
\nabla_x L(x_*,\lambda,\mu)=\nabla f(x_*)+\sum_i\lambda_i\nabla g_i(x_*)+\sum_j\mu_j\nabla h_j(x_*)=0.
$$
* <Complementary slackness>: $\lambda_i g_i(x_*)=0$ for every inequality <optimization constraint>.<Nonlinear Optimization, MIT 6.7220 and 15.084, Spring 2025/Lecture 7: Lagrange Multipliers and KKT Conditions>[Lecture 7, §L7.1.1, Definition L7.1, printed p. 3: the four KKT requirements]{ref}
The sign of each inequality <Lagrange multiplier> follows the chosen convention $g_i\leq0$: on the <feasible set>, $\lambda_i g_i\leq0$ makes the <optimization Lagrangian> a lower bound on the <objective function>. An equality contributes zero on the <feasible set> for either sign of its <Lagrange multiplier>. <Complementary slackness> says an inequality with $g_i(x_*)<0$ must have $\lambda_i=0$, while $\lambda_i>0$ implies an <active constraint>. An <active constraint> can still have zero <Lagrange multiplier>; the <quadratic minimization with a moving upper bound> below gives an explicit example.
The name records <William Karush>'s 1939 master's thesis and the 1951 work of <Harold W. Kuhn> and <Albert W. Tucker>.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[Chapter 5 bibliography, printed p. 272, and bibliography entries KT51 and Kuh76]{ref}
Back to article page
