查看“︁卡鲁什-库恩-塔克条件”︁的源代码

{{noteTA
|1=zh-tw:最佳化;zh-cn:最优化;
|2=zh-tw:限制;zh-cn:约束;
|4=zh-tw:研討生;zh-cn:研究生;
}}

在[[數學]]中，'''卡鲁什-库恩-塔克条件'''（{{lang-en|Karush-Kuhn-Tucker Conditions}}，常見別名：Kuhn-Tucker，KKT條件，Karush-Kuhn-Tucker最優化條件，Karush-Kuhn-Tucker條件，Kuhn-Tucker最優化條件，Kuhn-Tucker條件）是在满足一些有规则的条件下，一個[[非線性規劃]]問題能有[[最優化]]解法的一個[[必要條件]]。這是一個使用[[廣義化|广义]][[拉格朗日乘數|拉格朗日函数]]的结果。

考慮以下非線式最優化問題：

:<math> \min\limits_{x}\;\; f(x) </math>

:<math> \mbox{Subject to: }\ </math>

::<math> g_i(x) \le 0 , h_j(x) = 0</math>

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

不等式約束問題的必要和充分條件初見於[[威廉·卡鲁什]]的硕士論文<ref>{{cite paper|author=W. Karush|title=Minima of Functions of Several Variables with Inequalities as Side Constraints
|version=M.Sc. Dissertation|publisher=Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois|date=1939}}.此論文可於以下網址得到：http://wwwlib.umi.com/dxweb/details?doc_no=7371591{{Dead link}} (需付費)</ref>，之後在一份由[[哈羅德·W·庫恩]]及[[阿爾伯特·W·塔克]]撰寫的研究生論文<ref>{{cite conference
| first = H. W.
| last = Kuhn
| coauthors = Tucker, A. W.
| booktitle = Proceedings of 2nd Berkeley Symposium
| pages = 481-492
| title=Nonlinear programming
| publisher = University of California Press
| date = 1951
| location = Berkeley
}}</ref>出現後受到重視。

== 必要條件 ==
假設有目標函數，即是要被最小化的函數<math>f : \mathbb{R}^n \rightarrow \mathbb{R}</math>，約束函數<math>g_i : \,\!\mathbb{R}^n \rightarrow \mathbb{R}</math>及<math>h_j : \,\!\mathbb{R}^n \rightarrow \mathbb{R}</math>。再者，假設他們都是於<math>x^*</math>這點是连续可微的，如果<math>x^*</math>是一局部极小值，那麼將會存在一组所谓乘子的常数<math>\lambda \ge 0</math>, <math>\mu_i \ge 0\ (i = 1,\ldots,m)</math>及<math>\nu_j\ (j = 1,...,l)</math>令到
: <math>\lambda + \sum_{i=1}^m \mu_i + \sum_{j=1}^l |\nu_j| > 0,</math>

: <math>\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,</math>

: <math>\mu_i g_i (x^*) = 0\; \mbox{for all}\; i = 1,\ldots,m</math>。

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

於上述必要和充分條件中，dual multiplier <math>\lambda</math>可能是零。當<math>\lambda</math>是零時，這個情況就是退化的或反常的。因此必要和充分條件會將約束的幾何特性而不是將函數自身的特點納入計算。

有一定數量的正則性條件能保證解法不是退化的（即<math>\lambda \ne 0</math>），它們包括：

*線性獨立約束規範（Linear independence constraint qualification，LICQ）：有效不等式約束的[[梯度]]和等式約束的梯度於<math>x^*</math>線性獨立。

* Mangasarian-Fromowitz約束規範（Mangasarian-Fromowitz constraint qualification，MFCQ）：有效不等式約束的梯度和等式約束的梯度於<math>x^*</math>正線性獨立。

*常秩約束規範（Constant rank constraint qualification、CRCQ）：考慮每個有效不等式約束的梯度子集和等式約束的梯度，於<math>x^*</math>的鄰近區域的秩（rank）不變。

*常正線性依賴約束規範（Constant positive linear dependence constraint qualification，CPLD）：考慮每個有效不等式約束的梯度子集和等式約束的梯度，如果它們於<math>x^*</math>是正線性依賴，那麼它們於<math>x^*</math>的鄰近區域也是正線性依賴。（如果存在<math>a_1\geq 0,\ldots,a_n\geq 0</math> not all zero令到<math>a_1v_1+\ldots+a_nv_n=0</math>，那麼<math>\{v_1,\ldots,v_n\}</math>是正線性依賴）

*斯萊特條件（Slater condition）：如果問題只包含不等式約束，那麼有一點<math>x</math>令到<math>g_i(x) < 0</math> for all <math>i = 1,\ldots,m</math>

雖然MFCQ不等同於CRCQ，但可證出LICQ⇒MFCQ⇒CPLD，LICQ⇒CRCQ⇒CPLD。於實際情況下，較弱的約束規範會被傾向使用，這是因為較弱的約束規範能提供較強的最優化條件。

== 充分條件 ==

假設目標函數<math>f: \mathbb{R}^n \rightarrow \mathbb{R}</math>及約束函數<math>g_i : \mathbb{R}^n \rightarrow \mathbb{R}</math>皆為
[[凸函數|'''凸'''函數]]，而<math>h_j : \mathbb{R}^n \rightarrow \mathbb{R}</math>是一[[仿射變換|'''仿射'''函數]]，假設有一[[可行點]]<math>x^*</math>，如果有常數<math>\mu_i \ge 0\ (i = 1,\ldots,m)</math>及<math>\nu_j\ (j = 1,\ldots,l)</math>令到

: <math>\nabla f(x^*) + \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \nu_j \nabla h_j(x^*) = 0 </math>

: <math>\mu_i g_i (x^*) = 0\; \mbox{for all}\; i = 1,\ldots,m,</math>

那麼<math>x^*</math>這點是一[[極值|全局极小值]]。

==註釋==
{{reflist}}

==參考文獻==
{{refbegin}}
* 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).
{{refend}}

[[Category:數學最佳化]]

[[de:Konvexe Optimierung#Karush-Kuhn-Tucker-Bedingungen]]