KKT Conditions



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
gi(x) ≤ 0, hj(x)=0

Where x is the optimization variable, f(.) is the objective or cost function, gi(.) (i=1,..,m) are the inequality constraints and hj(.) (j=1,..,l)are the equality constraints. m and l denote the number of inequality and equality constraints respectively.

Necessary conditions:
If f, gi(.) (i=1,..,m) and hj(.) (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=1m μi∇gi(x*) + Σj=1l λj∇hj(x*) = 0  (stationarity)
gi(x*) ≤ 0, ∀i ∈ {1,..,m}  (primal feasibility)
hj(x*) = 0, ∀j ∈ {1,..,l}  (primal feasibility)
μi ≥ 0, ∀i ∈ {1,..,m}   (dual feasibility)
μigi(x*) = 0, ∀i ∈ {1,..,m}  (complementary slackness)



Regularity Conditions


In order for a minimum point x * to satisfy the above KKT conditions, it should satisfy some regularity condition, the most used ones are listed below:

(v_1,\ldots,v_n) is positive-linear dependent if there exists a_1\geq 0,\ldots,a_n\geq 0 not all zero such that a_1v_1+\ldots+a_nv_n=0.

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[4] . In practice weaker constraint qualifications are preferred since they provide stronger optimality conditions.

[edit]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 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 f and the inequality constraints gj are continuously differentiable convex functions and the equality constraints hi are affine functions.

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

[edit]Value function

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

 \text{Maximize }\; f(x)
 \text{subject to: }\
 g_i(x) \le a_i , h_j(x) = 0.

The value function is defined as:

V(a_1, \ldots a_n) = \sup\limits_x f(x)
 \text{subject to: }\
 g_i(x) \le a_i , h_j(x) = 0
 j\in\{1,\ldots l\}, i\in\{1,\ldots,m\}.

(So the domain of V is \{a \in \mathbb{R}^m | \text{for some }x\in X, g_i(x) \leq a_i, i \in \{1,\ldots,m\}.)

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












Comments