kReese.net

Karush的Kuhn - Tucker (KKT) 條件, 有時被稱為的Kuhn - Tucker條件, 是一個非線性規劃問題，需要滿足以最佳的條件. KKT條件不等式約束，從而擴展拉格朗日乘子法, 而不是只允許等式約束的拉格朗日乘子.

讓我們考慮一個非線性優化問題:

減少 $f(x)$
受: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

我們將讓 $x^{*}$ 代表了我們的問題相對最低點, 這也滿足了一些限制資格. 有了這個, 然後，我們可以假設，為每個元素存在向量 $\lambda_j \left ( j = 1, \ldots, l \right )$ , 其中升代表等式約束, 和 $\mu_i\left ( i = 1, \ldots, m \right )$ , 其中米不等式約束. 這些常數, $\lambda_j$ 和 $\mu_i$ , 是所謂的KKT乘法器.

為了在非線性規劃問題的KKT條件 (NLP), 然後必須滿足三個條件 [1-4]. 原始可行性重申了什麼問題，國, 不平等和平等的制約 $x^*$ 必須滿足的問題是最佳:

$\left.\begin{matrix} h\left ( x^* \right )=0\\ g\left ( x^* \right )\leq0 \end{matrix}\right\} \textrm{primal feasibility (PF)}$

第二個條件是被稱為雙可行性條件. 在這種情況下國家, 而冗長, 每一個元素 $\mu_i$ 必須大於零, 和問題的平穩必須等於 0.

$\left.\begin{matrix} \bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0\\ \lambda_i \in \mathbb{R}\\ \mu_i \geq 0 \end{matrix}\right\}\textrm{dual feasibility (DF)}$

問題的平穩:

$\bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0$

而其他兩個根本條件升和米必須為了滿足 $x^*$ 為最優.

必須滿足第三個條件是被稱為互補鬆弛. 這種情況只是國家，每個畝，其各自的不等式約束, 兩個產品應該導致零:

$\mu_i g_{i} \left ( x^* \right ) = 0$

當這三個條件是, 我們已與 KKT條件和我們的解決方案, $x^*$ , 為 NLP問題的最佳解決方案. 可能有多個 x 在符合條件的空間. 在問題空間中的任何一點，每一個元素升，並米, 這樣的元組 (x, 升, 米) 滿足 KKT條件是所謂的KKT點. 這些制約因素的推導中可以找到 [1,2]

約束資格

如前所述, 測試點，我們需要滿足一些要考慮的點，以便資格. 最知名的約束資格是線性獨立約束資格 (LICQ), 簡單地指出， $h_{j}(x^*)$ 和 $g_{i}(x^*)$ 是線性無關的，從其他點 $x^*$ . Mangasarian Fromovitz約束資格 (MFCQ) 同樣，除了積極 lineraly獨立 LICQ $x^*$ . [5]

但是其他的約束預選賽，放寬 LICQ. 斯萊特約束限定符可用於凸問題. 如果存在這樣一個點的x $h_{j}(x^*) =$ 和 $g_{i}(x^*) < 0$ 對所有的i,j活躍在 $x^*$ , 然後在石板條件成立. [5,6]

其他類型的約束預選賽確實存在, 但這些似乎是最常用的KKT資格.

[1] 庫恩, H. 和Tucker, A。, “非線性規劃” 第二伯克利的訴訟研討會 1951, 頁. 481-492.
[2] Karush, W。, “幾個變量的函數的極小值方面的制約因素的不平等”. M.鈧. 論文, 大學. of Chicago, 芝加哥, 該, 1939.
[3] 庫恩, M. “Karush -庫恩 - 塔克定理”, 互聯網: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM王國. 曼海姆, 2006.
[4]McCarl, 乙. 和Spreen, T., “非線性優化條件”, 總. 12, 應用數學編程使用代數系統. 互聯網: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, ř. 卡拉斯, é. 里貝羅和, 一. 非線性規劃約束的資格, 技術報告, 大學. 在巴拉那.
[6] 到達, ð. 和Zalinescu, 彗星. “在一些約束凸規劃資質條件的必要性”, 凸分析, 11 (1), 2004. 頁 95-110.

計算機科學與教學日誌

最近的帖子

Karush的Kuhn - Tucker條件

約束資格