因为选择，所以喜欢！

Karush-Kuhn-Tucker 最优化条件

最近看书总是看到KKT条件，不是很理解，找了下资料，整理如下：

一般地，一个最优化数学模型能够表示成下列标准形式：

所谓 Karush-Kuhn-Tucker 最优化条件，就是指上式的最小点 x* 必须满足下面的条件：

    KKT最优化条件是Karush[1939]以及Kuhn和Tucker[1951]先后独立发表出來的。这组最优化条件在Kuhn和Tucker发表之后才逐渐受到重视，因此许多书只记载成「Kuhn-Tucker 最优化条件 (Kuhn-Tucker conditions)」。

有个有趣的典故：刚开始人们只知道Kuhn-Tucker的文章，后来发现Karush在1939年就发表了相关文章，所以就称为KKT.

    KKT条件第一项是说最优点必须满足所有等式及不等式限制条件，也就是说最优点必须是一个可行解，这一点自然是毋庸置疑的。第二项表明在最优点 x*， ?f 必須是 ?h_j和 ?g_k的线性組合，？和？都叫作拉格朗日乘子。所不同的是不等式限制条件有方向性，所以每一个？都必须大于或等于零，而等式限制条件没有方向性，所以？没有符号的限制，其符号要视等式限制条件的写法而定（此处有几个符号打不出来，是最后一行公式里面的乘子，可以查书 邓乃扬的书，P15）.

    从KKT的几何意义出发这个定理还是很神奇的：

    f’(x)代表了f在x点增加的方向，而要找f的最小值的那个点就要朝f减小的方向走，也就是f*v < 0的区域，成为下降域；同理，g’(x)代表了g在x增加的方向，而可行区域就是g*v < 0的区域，成为可行域；要取得最优解就要使某点的下降域与可行域交集为空，也就是f’是g_k’的线性组合了。而g_k必须是有效的，即g_k(x)=0，否则其拉氏乘数就要等于0使其其实不发挥作用。

Karush–Kuhn–Tucker conditions

From Wikipedia, the free encyclopedia

In mathematics, the Karush–Kuhn–Tucker conditions (also known as the Kuhn-Tucker or KKT conditions) are necessary for a solution in nonlinear programming to be optimal, provided that someregularity conditions are satisfied.

We consider the following nonlinear optimization problem:

where is the function to be minimized, where are the functions of the inequality constraints and are the functions of the equality constraints, and where m and l are the number of inequality and equality constraints, respectively.

Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which have allowed only equality constraints. The KKT conditions were originally named after Harold W. Kuhn, and Albert W. Tucker, who first published the conditions.^[1] Later scholars discovered that the necessary conditions for this problem had been stated by William Karush in his master’s thesis.^[2]

Contents

[hide]

• 1 Necessary conditions
• 2 Regularity conditions (or constraint qualifications)
• 3 Sufficient conditions
• 4 Value function
• 5 Generalizations
• 6 References
• 7 See also
• 8 Further reading

[edit]Necessary conditions

Suppose that the objective function, i.e., the function to be minimized, is and the constraint functions are and . Further, suppose they are continuously differentiable at a point x ^* . If x ^* is a local minimum that satisfies some regularity conditions, then there exist constants and , called KKT multipliers, such that

Stationarity

Primal feasibility

Dual feasibility

Complementary slackness

In a particular case m = 0, i.e., without inequality constraints, these KKT conditions turn into Lagrange conditions, and the KKT multipliers are called Lagrange multipliers.

[edit]Regularity conditions (or constraint qualifications)

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:

• 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 than it doesn’t exist a sequence such that: λi ≠ 0 ⇒ λi hi(xk)>0 and μj ≠ 0 ⇒ μj gj(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 ^* .
• Linearity constraints: If f and g are affine functions, then no other condition is needed to assure that the minimum point is KKT.

() 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. 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 g_j are continuously differentiable convex functions and the equality constraints h_i areaffine functions.

It was shown by Martin in 1985^[3] 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.

[edit]Value function

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

The value function is defined as:

(So the domain of V is )

Given this definition, each coefficient, λ_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.

[edit]Generalizations

With an extra constant multiplier μ₀, which may be zero, in front of the KKT stationarity conditions turn into

which are called the Fritz John conditions.

The KKT conditions belong to a wider class of the First Order Necessary Conditions (FONC), which allow for non-smooth functions using subderivative.

[edit]References

1. ^ Kuhn, H. W.; Tucker, A. W. (1951). "Nonlinear programming". Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press. pp. 481–492.
2. ^ W. Karush (1939). Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois.
3. ^ Martin, D. H. (1985). "The essence of invexity". J. Optim. Theory Appl., 47. pp. 65–76.

[edit]See also

Farkas’ lemma

[edit]Further reading

• R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of Optimization Theory and Applications, vol. 125, no2, pp. 473-485 (2005).
• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• J. Nocedal, S. J. Wright, Numerical Optimization. Springer Publishing. ISBN 978-0-387-30303-1.