複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/卡羅需-庫恩-塔克條件/23121032
複製
複製成功

卡羅需-庫恩-塔克條件

（數學術語）

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

目錄

  1. 1 簡介
  2. 2 必要條件
  3. 3 正則性條件或約束規範
  4. 4 充分條件

卡羅需-庫恩-塔克條件簡介

在數學中，卡羅需-庫恩-塔克條件（英文原名：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）的碩士論文， [1]  之後在一份由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。於實際情況下，較弱的約束規範會被傾向使用，這是因為較弱的約束規範能提供較強的最優化條件。

卡羅需-庫恩-塔克條件充分條件

假設目標函數
及約束函數
皆為凸函數，而
是一仿射函數，假設有一可行點，如果有常數
及
令到
那麼
這點是一全局極小值。
參考資料
  • 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..