卡羅需-庫恩-塔克條件(卡羅需-庫恩-塔克條件)

在數學中，卡羅需-庫恩-塔克條件（英文原名：Karush-Kuhn-Tucker Conditions常見別名：Kuhn-Tucker，KKT條件，Karush-Kuhn-Tucker最最佳化條件，Karush-Kuhn-Tucker條件，Kuhn-Tucker最最佳化條件，Kuhn-Tucker條件）是在滿足一些有規則的條件下，一個非線性規劃（Nonlinear Programming）問題能有最最佳化解法的一個必要和充分條件。這是一個廣義化拉格朗日乘數的成果。

基本介紹

• 中文名：卡羅需-庫恩-塔克條件
• 外文名：Karush-Kuhn-Tucker Conditions
• 常見別名：KKT條件
• 屬於：廣義化拉格朗日乘數的成果
• 學科：數學
• 領域：數學

簡介

在數學中，卡羅需-庫恩-塔克條件（英文原名：Karush-Kuhn-Tucker Conditions常見別名：Kuhn-Tucker，KKT條件，Karush-Kuhn-Tucker最最佳化條件，Karush-Kuhn-Tucker條件，Kuhn-Tucker最最佳化條件，Kuhn-Tucker條件）是在滿足一些有規則的條件下，一個非線性規劃（Nonlinear Programming）問題能有最最佳化解法的一個必要和充分條件。這是一個廣義化拉格朗日乘數的成果。

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

f(x)是需要最小化的函式， 是不等式約束， 是等式約束，m和l分別為不等式約束和等式約束的數量。

不等式約束問題的必要和充分條件初見於卡羅需（William Karush）的碩士論文，之後在一份由W.庫恩（Harold W. Kuhn）及塔克（Albert W. Tucker）撰寫的研討生論文出現後受到重視。

必要條件

假設有目標函式，即是要被最小化的函式 ，約束函式 及 。再者，假設他們都是於 這點是連續可微的，如果 是一局部極小值，那么將會存在一組所謂乘子的常數 及 令到

正則性條件或約束規範

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

有一定數量的正則性條件能保證解法不是退化的（即），它們包括：

線性獨立約束規範（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^*的鄰近區域也是正線性依賴。（如果存在 not all zero令到，那么是正線性依賴）

斯萊特條件（Slater condition）：如果問題只包含不等式約束，那么有一點x令到。

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

充分條件

假設目標函式及約束函式皆為凸函式，而是一仿射函式，假設有一可行點，如果有常數及令到

那么這點是一全局極小值。