序

本次記錄：
原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系；
強(qiáng)對(duì)偶與弱對(duì)偶；
引入KKT的原因；

原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系

定義一個(gè)原問(wèn)題：

寫出拉格朗日：

對(duì)偶函數(shù) θ 產(chǎn)生了一個(gè)原問(wèn)題最優(yōu)值p* 的一個(gè)下界，也就是，對(duì)于任意的λ>=0 以及 μ 來(lái)說(shuō)，有：

好了，現(xiàn)在證明對(duì)偶問(wèn)題是原問(wèn)題的下界（假設(shè) x* 是在可行域內(nèi)）：

也就是說(shuō)我們找到了原問(wèn)題最優(yōu)值的一個(gè)下界。既然我們找到了一個(gè)下界，顯然我們要找到它最好的下界。什么是最好的下界的？顯然就是所有下界當(dāng)中最大的那一個(gè)。所以需要對(duì) θ 最大化，即：

以上的對(duì)偶性質(zhì)被稱作是弱對(duì)偶性。

強(qiáng)對(duì)偶

首先引入一個(gè)對(duì)偶間隙： p* - d*，也就是原問(wèn)題的最優(yōu)值與通過(guò)拉個(gè)郎日對(duì)偶函數(shù)獲得的其最好（最大）的下界之差。

那么有沒(méi)有可能在某種情況下，對(duì)偶間隙消失了呢？也就是說(shuō)對(duì)偶問(wèn)題的最優(yōu)值與原問(wèn)題的最優(yōu)值相等了呢？

答案是，如果不等式約束 g(x) 滿足嚴(yán)格的 < 0，那么可以使得 d* = p*。

上面這個(gè)被稱作slater條件，可以證明凸優(yōu)化問(wèn)題，如果slater條件滿足了，那么可以得到 d*=p*，slater同時(shí)也是原問(wèn)題可以等價(jià)為對(duì)偶問(wèn)題的一個(gè)充分條件，該條件確保了鞍點(diǎn)的存在。

上述的對(duì)偶被稱為強(qiáng)對(duì)偶。

如果對(duì)偶間隙消失，那么我們?cè)谧C明 θ <= p* 的過(guò)程就會(huì)變?yōu)椋?/p>

上圖中的等號(hào) 1 說(shuō)明原問(wèn)題的最優(yōu)點(diǎn) x* 是使得 L 取得最小值的點(diǎn)
等號(hào)2 說(shuō)明：

上式被稱作互補(bǔ)條件，也就是說(shuō)，只要一個(gè)不為0，另一個(gè)就必為0！

這個(gè)互補(bǔ)條件在SVM中起到很大的作用，當(dāng) g(x) < 0 時(shí)，x* 是在可行域內(nèi)的，這時(shí)不等式不起作用，此時(shí) λ = 0。
而λ > 0使的點(diǎn)肯定是可行域邊界的點(diǎn)，也就是g(x) = 0
也就是說(shuō)，只有積極約束才有不為0的對(duì)偶變量，而這在支持向量機(jī)中有重要作用，原因：
svm的約束為：

那么哪些不等式約束對(duì)應(yīng)著不為0的對(duì)偶變量呢？顯然只有當(dāng) d(wx+b) = 1時(shí)，這個(gè)約束對(duì)應(yīng)的對(duì)偶變量才可能不為0，而d(wx+b) = 1同時(shí)意味著樣本點(diǎn)x是在支持向量上的，也就是說(shuō)，只有支持向量上的點(diǎn)對(duì)應(yīng)的拉格朗日乘子不為0。

KKT

slater條件確保了鞍點(diǎn)的存在，但是無(wú)法確保鞍點(diǎn)一定是最優(yōu)解，所以KKT條件的作用便體現(xiàn)出來(lái)。
KKT條件的作用：KKT條件是確保鞍點(diǎn)是原函數(shù)最優(yōu)解的充分條件

KKT可以概括為以下三個(gè)條件：
1）最優(yōu)點(diǎn)x必須滿足所有等式及不等式限制條件, 也就是說(shuō)最優(yōu)點(diǎn)必須是一個(gè)可行解

2）在最優(yōu)點(diǎn)x, ?f 必須是 ?gi 和 ?hj 的線性組合（α和β是拉格朗日乘子）

轉(zhuǎn)載注明：http://www.itdecent.cn/p/c3e23bf233f8