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

June 29, 2009

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

Filed under: Giải tích 9 (MA5265), Linh Tinh, Nghiên Cứu Khoa Học — Tags: Karush–Kuhn–Tucker conditions — Ngô Quốc Anh @ 16:28

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

M	T	W	T	F	S	S
« May				Jul »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

	Ngô Quốc Anh on Existence results for the Eins…
	Ngô Quốc Anh on A note on the Sobolev trace…
	doanchi on A note on the Sobolev trace…
	Vuminhtri on MuPAD
	duong on MuPAD
	duong on MuPAD
	duong on MuPAD
	duong on MuPAD
	Ngô Quốc Anh on MuPAD
	duong on MuPAD

Ngô Quốc Anh

June 29, 2009