# 卡羅需－庫恩－塔克條件

$\min\limits_{x}\;\; f(x)$
$\mbox{Subject to: }\$
$g_i(x) \le 0 , h_j(x) = 0$

$f(x)$是需要最小化的函數，$g_i (x)\ (i = 1, \ldots,m)$是不等式約束，$h_j (x)\ (j = 1,\ldots,l)$是等式約束，$m$$l$分別為不等式約束和等式約束的數量。

## 必要條件

$\lambda + \sum_{i=1}^m \mu_i + \sum_{j=1}^l |\nu_j| > 0,$
$\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,$
$\mu_i g_i (x^*) = 0\; \mbox{for all}\; i = 1,\ldots,m$

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

• 線性獨立約束規範（Linear independence constraint qualification，LICQ）：有效不等式約束的梯度（和等式約束的梯度於$x^*$線性獨立。
• Mangasarian-Fromowitz約束規範（Mangasarian-Fromowitz constraint qualification，MFCQ）：有效不等式約束的梯度和等式約束的梯度於$x^*$正線性獨立。
• 常秩約束規範（Constant rank constraint qualification、CRCQ）：考慮每個有效不等式約束的梯度子集和等式約束的梯度，於$x^*$的鄰近區域的秩（rank）不變。
• 常正線性依賴約束規範（Constant positive linear dependence constraint qualification，CPLD）：考慮每個有效不等式約束的梯度子集和等式約束的梯度，如果它們於$x^*$是正線性依賴，那麼它們於$x^*$的鄰近區域也是正線性依賴。（如果存在$a_1\geq 0,\ldots,a_n\geq 0$ not all zero令到$a_1v_1+\ldots+a_nv_n=0$，那麼$\{v_1,\ldots,v_n\}$是正線性依賴）
• 斯萊特條件（Slater condition）：如果問題只包含不等式約束，那麼有一點$x$令到$g_i(x) < 0$ for all $i = 1,\ldots,m$

## 充分條件

$\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0$
$\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. 1951: pp. 481-492.

## 參考文獻

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