卡鲁什-库恩-塔克条件

在数学中，卡鲁什-库恩-塔克条件（英语：Karush-Kuhn-Tucker Conditions，常见别名：Kuhn-Tucker，KKT条件，Karush-Kuhn-Tucker最优化条件，Karush-Kuhn-Tucker条件，Kuhn-Tucker最优化条件，Kuhn-Tucker条件）是在满足一些有规则的条件下，一个非线性规划问题能有最优化解法的一个必要条件。这是一个使用广义拉格朗日函数的结果。

考虑以下非线式最优化问题：

${\displaystyle \min \limits _{x}\;\;f(x)}$

${\displaystyle {\mbox{Subject to: }}\ }$

${\displaystyle g_{i}(x)\leq 0,h_{j}(x)=0}$

${\displaystyle f(x)}$是需要最小化的函数，${\displaystyle g_{i}(x)\ (i=1,\ldots ,m)}$是不等式约束，${\displaystyle h_{j}(x)\ (j=1,\ldots ,l)}$是等式约束，${\displaystyle m}$和${\displaystyle l}$分别为不等式约束和等式约束的数量。

不等式约束问题的必要和充分条件初见于威廉·卡鲁什的硕士论文^[1]，之后在一份由哈罗德·W·库恩及阿尔伯特·W·塔克撰写的研究生论文^[2]出现后受到重视。

必要条件

假设有目标函数，即是要被最小化的函数${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$，约束函数${\displaystyle g_{i}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$及${\displaystyle h_{j}:\,\!\mathbb {R} ^{n}\rightarrow \mathbb {R} }$。再者，假设他们都是于${\displaystyle x^{*}}$这点是连续可微的，如果${\displaystyle x^{*}}$是一局部极小值，那么将会存在一组所谓乘子的常数${\displaystyle \lambda \geq 0}$, ${\displaystyle \mu _{i}\geq 0\ (i=1,\ldots ,m)}$及${\displaystyle \nu _{j}\ (j=1,...,l)}$令到

${\displaystyle \lambda +\sum _{i=1}^{m}\mu _{i}+\sum _{j=1}^{l}|\nu _{j}|>0,}$

${\displaystyle \lambda \nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}(x^{*})=0,}$

${\displaystyle \mu _{i}g_{i}(x^{*})=0\;{\mbox{for all}}\;i=1,\ldots ,m}$。

正则性条件或约束规范

于上述必要和充分条件中，dual multiplier ${\displaystyle \lambda }$可能是零。当${\displaystyle \lambda }$是零时，这个情况就是退化的或反常的。因此必要和充分条件会将约束的几何特性而不是将函数自身的特点纳入计算。

有一定数量的正则性条件能保证解法不是退化的（即${\displaystyle \lambda \neq 0}$），它们包括：

• 线性独立约束规范（Linear independence constraint qualification，LICQ）：有效不等式约束的梯度和等式约束的梯度于${\displaystyle x^{*}}$线性独立。

• Mangasarian-Fromowitz约束规范（Mangasarian-Fromowitz constraint qualification，MFCQ）：有效不等式约束的梯度和等式约束的梯度于${\displaystyle x^{*}}$正线性独立。

• 常秩约束规范（Constant rank constraint qualification、CRCQ）：考虑每个有效不等式约束的梯度子集和等式约束的梯度，于${\displaystyle x^{*}}$的邻近区域的秩（rank）不变。

• 常正线性依赖约束规范（Constant positive linear dependence constraint qualification，CPLD）：考虑每个有效不等式约束的梯度子集和等式约束的梯度，如果它们于${\displaystyle x^{*}}$是正线性依赖，那么它们于${\displaystyle x^{*}}$的邻近区域也是正线性依赖。（如果存在${\displaystyle a_{1}\geq 0,\ldots ,a_{n}\geq 0}$ not all zero令到${\displaystyle a_{1}v_{1}+\ldots +a_{n}v_{n}=0}$，那么${\displaystyle \{v_{1},\ldots ,v_{n}\}}$是正线性依赖）

• 斯莱特条件（Slater condition）：如果问题只包含不等式约束，那么有一点${\displaystyle x}$令到${\displaystyle g_{i}(x)<0}$ for all ${\displaystyle i=1,\ldots ,m}$

虽然MFCQ不等同于CRCQ，但可证出LICQ⇒MFCQ⇒CPLD，LICQ⇒CRCQ⇒CPLD。于实际情况下，较弱的约束规范会被倾向使用，这是因为较弱的约束规范能提供较强的最优化条件。

充分条件

假设目标函数${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$及约束函数${\displaystyle g_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$皆为 凸函数，而${\displaystyle h_{j}:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$是一仿射函数，假设有一可行点${\displaystyle x^{*}}$，如果有常数${\displaystyle \mu _{i}\geq 0\ (i=1,\ldots ,m)}$及${\displaystyle \nu _{j}\ (j=1,\ldots ,l)}$令到

${\displaystyle \nabla f(x^{*})+\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\nu _{j}\nabla h_{j}(x^{*})=0}$

${\displaystyle \mu _{i}g_{i}(x^{*})=0\;{\mbox{for all}}\;i=1,\ldots ,m,}$

那么${\displaystyle x^{*}}$这点是一全局极小值。

注释

1. W. Karush. Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois. 1939..此论文可于以下网址得到：http://wwwlib.umi.com/dxweb/details?doc_no=7371591^{[失效链接]} (需付费)
2. Kuhn, H. W.; Tucker, A. W. Nonlinear programming. Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press: 481–492. 1951. 引文使用过时参数coauthors (帮助)

参考文献

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• 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).