In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied. Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which allows only equality constraints. Similar to the Lagrange approach, the constrained maximization (minimization) problem is rewritten as a Lagrange function whose optimal point is a global maximum or minimum over the domain of the choice variables and a global minimum (maximum) over the multipliers. The Karush–Kuhn–Tucker theorem is sometimes referred to as the saddle-point theorem. The KKT conditions were originally named after Harold W. Kuhn and Albert W. Tucker, who first published the conditions in 1951. Later scholars discovered that the necessary conditions for this problem had been stated in an unpublished master's thesis by William Karush in 1939.
Nonlinear optimization problem Consider the following nonlinear optimization problem in standard form:
minimize f ( x ) {\displaystyle f(\mathbf {x} )}
subject to
g i ( x ) ≤ 0 , {\displaystyle g_{i}(\mathbf {x} )\leq 0,}
h j ( x ) = 0. {\displaystyle h_{j}(\mathbf {x} )=0.}
where x ∈ X {\displaystyle \mathbf {x} \in \mathbf {X} } is the optimization variable chosen from a convex subset of R n {\displaystyle \mathbb {R} ^{n}} , f {\displaystyle f} is the objective or utility function, g i ( i = 1 , … , m ) {\displaystyle g_{i}\ (i=1,\ldots ,m)} are the inequality constraint functions and h j ( j = 1 , … , ℓ ) {\displaystyle h_{j}\ (j=1,\ldots ,\ell )} are the equality constraint functions. The numbers of inequalities and equalities are denoted by m {\displaystyle m} and ℓ {\displaystyle \ell } respectively. Corresponding to the constrained optimization problem one can form the Lagrangian function
L ( x , μ , λ ) = f ( x ) + μ ⊤ g ( x ) + λ ⊤ h ( x ) = L ( x , α ) = f ( x ) + α ⊤ ( g ( x ) h ( x ) ) {\displaystyle {\mathcal {L}}(\mathbf {x} ,\mathbf {\mu } ,\mathbf {\lambda } )=f(\mathbf {x} )+\mathbf {\mu } ^{\top }\mathbf {g} (\mathbf {x} )+\mathbf {\lambda } ^{\top }\mathbf {h} (\mathbf {x} )=L(\mathbf {x} ,\mathbf {\alpha } )=f(\mathbf {x} )+\mathbf {\alpha } ^{\top }{\begin{pmatrix}\mathbf {g} (\mathbf {x} )\\\mathbf {h} (\mathbf {x} )\end{pmatrix}}}
where
… excerpt ends here. Continue reading the full article.
