Necessary condition for a solution in nonlinear-programming to be optimal, provided that some regularity conditions are satisfied. In the particular case where 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.Assuming the following nonlinear optimization problem: Minimize f(x) Subject to g _{i}(x) ≤ 0, h_{j}(x)=0Where x is the optimization variable, f(.) is the objective or cost function, g _{i}(.) (i=1,..,m) are the inequality constraints and h_{j}(.) (j=1,..,l)are the equality constraints. m and l denote the number of inequality and equality constraints respectively.Necessary conditions: If f, g _{i}(.) (i=1,..,m) and h_{j}(.) (j=1,..,l) are continuously differentiable at point x^{*}. I If x^{*} is a local minimum that satisfies some regularity conditions (see below), then there exist constants μ_{i}(i=1,..,m) and λ_{j}(j=1,..,l) (called KKT multipliers), such that∇f(x*) + Σ _{i=1}^{m} μ_{i}∇g_{i}(x^{*}) + Σ_{j=1}^{l} λ_{j}∇h_{j}(x^{*}) = 0 (stationarity)g _{i}(x^{*}) ≤ 0, ∀i ∈ {1,..,m} (primal feasibility)h _{j}(x^{*}) = 0, ∀j ∈ {1,..,l} (primal feasibility)μ _{i} ≥ 0, ∀i ∈ {1,..,m} (dual feasibility)μ _{i}g_{i}(x^{*}) = 0, ∀i ∈ {1,..,m} (complementary slackness)Regularity Conditions In order for a minimum point - Linearity constraint qualification: If
*g*_{i}and*h*_{j}are affine functions, then no other condition is needed. - Linear independence constraint qualification (LICQ): the gradients of the active inequality constraints and the gradients of the equality constraints are linearly independent at
*x*^{*}. - Mangasarian–Fromovitz constraint qualification (MFCQ): the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly independent at
*x*^{*}. - Constant rank constraint qualification (CRCQ): for each subset of the gradients of the active inequality constraints and the gradients of the equality constraints the rank at a vicinity of
*x*^{*}is constant. - Constant positive linear dependence constraint qualification (CPLD): for each subset of the gradients of the active inequality constraints and the gradients of the equality constraints, if it is positive-linear dependent at
*x*^{*}then it is positive-linear dependent at a vicinity of*x*^{*}. - Quasi-normality constraint qualification (QNCQ): if the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly independent at
*x*^{*}with associated multipliers λ_{i}for equalities and μ_{j}for inequalities, then there is no sequence such that and . - Slater condition: for a convex problem, there exists a point
*x*such that*h*(*x*) = 0 and*g*_{i}(*x*) < 0 for all*i*active in*x*^{*}.
() is positive-linear dependent if there exists not all zero such that . It can be shown that LICQ⇒MFCQ⇒CPLD⇒QNCQ, LICQ⇒CRCQ⇒CPLD⇒QNCQ (and the converses are not true), although MFCQ is not equivalent to CRCQ ## [edit]Sufficient conditionsIn some cases, the necessary conditions are also sufficient for optimality. In general, the necessary conditions are not sufficient for optimality and additional information is necessary, 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 It was shown by Martin in 1985 ## [edit]Value functionIf we reconsider the optimization problem as a maximization problem with constant inequality constraints, The value function is defined as: (So the domain of Given this definition, each coefficient, μ |