# 卡鲁什-库恩-塔克条件

${\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}$分別為不等式約束和等式約束的數量。

## 必要條件

${\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}$

## 正則性條件或約束規範

• 線性獨立約束規範（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}$

## 充分條件

${\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,}$

## 註釋

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.

## 參考文獻

• 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).