Ngô Quốc Anh

June 29, 2009

Karush–Kuhn–Tucker conditions, the 1st order optimality condition

In mathematics, the Karush–Kuhn–Tucker conditions (also known as the Kuhn-Tucker or the KKT conditions) are necessary for a solution in nonlinear programming to be optimal, provided some regularity conditions are satisfied. It is a generalization of the method of Lagrange multipliers to inequality constraints. The conditions are named for William Karush, Harold W. Kuhn, and Albert W. Tucker.

Let us consider the following nonlinear optimization problem:

Minimize

f(x)

subject to

g_i(x) \le 0, \quad h_j(x) = 0

where f(x) is the function to be minimized, g_i (x) (i = 1,...,m) are the inequality constraints and h_j (x) (j = 1,...,l) are the equality constraints, and m and l are the number of inequality and equality constraints, respectively.

The necessary conditions for this general equality-inequality constrained problem were first published in the Masters thesis of William Karush, although they only became renowned after a seminal conference paper by Harold W. Kuhn and Albert W. Tucker.

Necessary conditions

Suppose that the objective function, i.e., the function to be minimized, is f : \mathbb{R}^n \rightarrow \mathbb{R} and the constraint functions are g_i : \mathbb{R}^n \rightarrow \mathbb{R} and h_j : \mathbb{R}^n \rightarrow \mathbb{R}. Further, suppose they are continuously differentiable at a point x^\star. If x^\star is a local minimum that satisfies some regularity conditions, then there exist constants \mu_i\ (i = 1,...,m) and \lambda_j (j = 1,...,l) such that

Stationarity:

\displaystyle\nabla f(x^\star) + \sum_{i=1}^m \mu_i \nabla g_i(x^\star) + \sum_{j=1}^l \lambda_j \nabla h_j(x^\star) = 0,

Primal feasibility:

\displaystyle g_i(x^\star) \le 0, \qquad\forall i = 1,..., m
\displaystyle h_j(x^\star) = 0, \qquad \forall j = 1,..., l.

Dual feasibility:

\displaystyle \mu_i \ge 0 (i = 1,...,m) .

Complementary slackness:

\displaystyle \mu_i g_i (x^\star) = 0 \qquad \forall i = 1,...,m.

Regularity conditions (or constraint qualifications)

In order for a minimum point x^\star be KKT, it should satisfy some regularity condition, the most used ones are listed below

  • Linear independence constraint qualification (LICQ): the gradients of the active inequality constraints and the gradients of the equality constraints are linearly independent at x^\star.
  • Mangasarian-Fromowitz constraint qualification (MFCQ): the gradients of the active inequality constraints and the gradients of the equality constraints are positive-linearly independent at x^\star.
  • 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^\star 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^\star then it is positive-linear dependent at a vicinity of x^\star (v_1,...,v_n) is positive-linear dependent if there exists a_1\geq 0,…,a_n\geq 0 not all zero such that a_1v_1+...+a_nv_n=0).
  • 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^\star with associated multipliers \lambda_i for equalities and \mu_j for inequalities than it doesn’t exist a sequence x_k\to x^\star such that \lambda_i \ne 0 therefore \lambda_i h_i(x_k)>0 and \mu_j \ne 0 thus \mu_j g_j(x_k)>0.
  • 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^\star.
  • Linearity constraints: If f and g are affine functions, then no other condition is needed to assure that the minimum point is KKT.

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

Sufficient conditions

In some cases, the necessary conditions are also sufficient for optimality. This is the case when the objective function f and the inequality constraints g_j are continuously differentiable convex functions and the equality constraints hi are affine functions. It was shown by Martin in 1985 that the broader class of functions in which KKT conditions guarantees global optimality are the so called invex functions. So if equality constraints are affine functions, inequality constraints and the objective function are continuously differentiable invex functions then KKT conditions are sufficient for global optimality.

Value function

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

Minimize

f(x)

subject to

g_i(x) \le a_i , \quad h_j(x) = 0

The value function is defined as

\displaystyle V(a_1, ..., a_n) = \sup\limits_{x} f(x)

subject to

\displaystyle g_i(x) \le a_i , \quad h_j(x) = 0 j \in \{1,...,l\}, i\in{1,...,m}.

(So the domain of V is

\displaystyle\{a \in \mathbb{R}^m | \mbox{for some }x\in X, g_i(x) \leq a_i, i \in \{1,...,m\}.)

Given this definition, each coefficient, \lambda_i, is the rate at which the value function increases as a_i increases. Thus if each 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 f. This interpretation is especially important in economics and is used, for instance, in utility maximization problems.

Source

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: