上一講我們介紹了最優(yōu)化問題的兩種形式偿警，無約束的和等式約束條件下的蹋砚，這一講票摇，我們主要介紹不等式約束條件下的最優(yōu)化問題，并介紹一下我們的KKT條件珊擂。
1、不等式約束條件
設(shè)目標函數(shù)f(x)费变，不等式約束為g(x)摧扇，有的教程還會添加上等式約束條件h(x)。此時的約束優(yōu)化問題描述如下：
則我們定義不等式約束下的拉格朗日函數(shù)L挚歧，則L表達式為：
求解上面的問題扛稽，我們同樣可以使用等式約束條件的求解思路，對所有的參數(shù)進行求導滑负，但是對于求解出的最優(yōu)解在张，必須滿足KKT條件（Karush-Kuhn-Tucker ）：
1）L(a, b, x)對x求導為零；
2）h(x) =0;
3）a*g(x) = 0;
求取這些等式之后就能得到候選最優(yōu)值矮慕。其中第三個式子非常有趣帮匾，因為g(x)<=0，如果要滿足這個等式痴鳄，必須a=0或者g(x)=0. 這是SVM的很多重要性質(zhì)的來源瘟斜，如支持向量的概念。
2夏跷、KKT條件推導
2.1 對偶問題轉(zhuǎn)換
接下來我們介紹一下KKT條件的推導：首先讓我們針對針對 λ 和 ν 最大化哼转，令：
這里 λ?0 理解為向量 λ 的每一個元素都非負即可。這個函數(shù) z(x) 對于滿足原始問題約束條件的那些 x 來說槽华，其值等于 f0(x) 壹蔓，這很容易驗證，因為滿足約束條件的 x 會使得 hi(x)=0 猫态，因此最后一項消掉了佣蓉，而 fi(x)≤0 披摄，并且我們要求了 λ?0 ，因此 λifi(x)≤0 勇凭，所以最大值只能在它們都取零的時候得到疚膊，這個時候就只剩下 f0(x) 了。因此虾标，對于滿足約束條件的那些 x 來說寓盗，f0(x)=z(x) 。這樣一來璧函，原始的帶約束的優(yōu)化問題其實等價于如下的無約束優(yōu)化問題：
到這里傀蚌，我們成功把帶約束問題轉(zhuǎn)化為了無約束問題，不過這其實只是一個形式上的重寫蘸吓，并沒有什么本質(zhì)上的改變善炫。我們只是把原來的問題通過 拉格朗日寫作了如下形式：
我們把上面的形式稱為原始問題，之前了解過SVM的同學肯定知道库继，如果我們把min和max對換一下位置箩艺，就得到這個問題的對偶問題：
2.2 對偶問題的最優(yōu)解是原始問題最優(yōu)解的下界
交換之后的對偶問題與原始問題的解并不相等，直觀的可以這么理解宪萄，別墅中最便宜的房子的價格也要比普通樓房的最貴的價格高艺谆。當然這是很不嚴格的說法，我們需要嚴格的證明這一點雨膨，和剛才的z(x)類似擂涛，我們再定一個公式：
g 有一個很好的性質(zhì)就是它是 primal problem 的一個下界。換句話說聊记，如果 primal problem 的最小值記為 p? ，那么對于所有的 λ?0 和 ν 恢暖，我們有：
證明過程如下圖：
上面這個性質(zhì)叫做弱對偶性排监，對于所有的優(yōu)化問題都成立。既然有弱對偶性杰捂，那必然有強對偶性舆床，前對偶性指的原始問題和對偶問題的最優(yōu)解嚴格相等，即：
在強對偶性成立的情況下嫁佳，我們就可以通過對原始問題的對偶問題的求解來得到最優(yōu)解（SVM就是這么做的）挨队，但并不是所有情況下強對偶性都成立，它會有一定的前提蒿往。
2.3 Slater 條件
如果你不是專門研究規(guī)劃問題的同學盛垦，咱們還是直接看結(jié)論吧。首先我們介紹一下Slater 條件瓤漏，Slater 條件是指存在嚴格滿足約束條件的點 x 腾夯，這里的“嚴格”是指 fi(x)≤0 中的“小于或等于號”要嚴格取到“小于號”颊埃，亦即，存在 x 滿足：
我們有：如果原始問題是凸優(yōu)化問題（很慶幸蝶俱，SVM的規(guī)劃問題是一個凸優(yōu)化問題）的并且滿足 Slater 條件的話班利，那么 strong duality 成立。需要注意的是榨呆，這里只是指出了 strong duality 成立的一種情況罗标，而并不是唯一情況，不過研究SVM的話 积蜻，知道這種情況足夠了闯割。
2.4 KKT條件
讓我們回到 duality 的話題。來看看 strong duality 成立的時候的一些性質(zhì)浅侨。
假設(shè) x? 和 (λ?,ν?) 分別是 primal problem 和 dual problem 的極值點纽谒，相應的極值為 p? 和 d? ，首先 p?=d? 如输，此時我們可以得到：
因為左右兩端其實是相等的鼓黔，所以上面的小于等于號可以替換為等于號，我們一共替換了兩次不见，這兩次替換我們都能得到一個重要的性質(zhì)：
再將其他一些顯而易見的條件寫到一起澳化，就是傳說中的 KKT (Karush-Kuhn-Tucker) 條件：
任何滿足強對偶性（不一定要求是通過 Slater 條件得到，也不一定要求是凸優(yōu)化問題）的問題都滿足 KKT 條件稳吮，換句話說缎谷，這是 強對偶性 的一個必要條件。不過灶似，當原始問題是凸優(yōu)化問題的時候（當然還要求一應函數(shù)是可微的列林，否則 KKT 條件的最后一個式子就沒有意義了），KKT 就可以升級為充要條件酪惭。換句話說希痴，如果 原始問題是一個凸優(yōu)化問題，且存在 x? 和 (λ?,ν?) 滿足 KKT 條件春感，那么它們分別是 原始問題 和 對偶問題 的極值點并且強對偶性成立砌创。
