這套理論不僅適用于 SVM 的優(yōu)化問(wèn)題，而是對(duì)于所有帶約束的優(yōu)化問(wèn)題都適用的，是優(yōu)化理論中的一個(gè)重要部分。簡(jiǎn)單來(lái)說(shuō)，對(duì)于任意一個(gè)帶約束的優(yōu)化都可以寫(xiě)成這樣的形式：

mins.t.f0(x)fi(x)≤0,i=1,…,mhi(x)=0,i=1,…,p

形式統(tǒng)一能夠簡(jiǎn)化推導(dǎo)過(guò)程中不必要的復(fù)雜性。其他的形式都可以歸約到這樣的標(biāo)準(zhǔn)形式，例如一個(gè) maxf(x) 可以轉(zhuǎn)化為 min?f(x) 等。假如 f0,f1,…,fm 全都是凸函數(shù)，并且 h1,…,hp 全都是仿射函數(shù)（就是形如 Ax+b 的形式），那么這個(gè)問(wèn)題就叫做凸優(yōu)化（Convex Optimization）問(wèn)題。凸優(yōu)化問(wèn)題有許多優(yōu)良的性質(zhì)，例如它的極值是唯一的。不過(guò)，這里我們并沒(méi)有假定需要處理的優(yōu)化問(wèn)題是一個(gè)凸優(yōu)化問(wèn)題。

雖然約束條件能夠幫助我們減小搜索空間，但是如果約束條件本身就是比較復(fù)雜的形式的話(huà)，其實(shí)是一件很讓人頭痛的問(wèn)題，為此我們希望把帶約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束的優(yōu)化問(wèn)題。為此，我們定義 Lagrangian 如下：

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑i=1pνihi(x)

它通過(guò)一些系數(shù)把約束條件和目標(biāo)函數(shù)結(jié)合在了一起。當(dāng)然 Lagrangian 本身并不好玩，現(xiàn)在讓我們來(lái)讓他針對(duì) λ 和 ν 最大化，令：

z(x)=maxλ?0,νL(x,λ,ν)

這里 λ?0 理解為向量 λ 的每一個(gè)元素都非負(fù)即可。這個(gè)函數(shù) z(x) 對(duì)于滿(mǎn)足原始問(wèn)題約束條件的那些 x 來(lái)說(shuō)，其值等于 f0(x) ，這很容易驗(yàn)證，因?yàn)闈M(mǎn)足約束條件的 x 會(huì)使得 hi(x)=0 ，因此最后一項(xiàng)消掉了，而 fi(x)≤0 ，并且我們要求了 λ?0 ，因此 λifi(x)≤0 ，所以最大值只能在它們都取零的時(shí)候得到，這個(gè)時(shí)候就只剩下 f0(x) 了。因此，對(duì)于滿(mǎn)足約束條件的那些 x 來(lái)說(shuō)，f0(x)=z(x) 。這樣一來(lái)，原始的帶約束的優(yōu)化問(wèn)題其實(shí)等價(jià)于如下的無(wú)約束優(yōu)化問(wèn)題：

minxz(x)

因?yàn)槿绻紗?wèn)題有最優(yōu)值，那么肯定是在滿(mǎn)足約束條件的某個(gè) x? 取得，而對(duì)于所有滿(mǎn)足約束條件的 x ，z(x) 和 f0(x) 都是相等的。至于那些不滿(mǎn)足約束條件的 x ，原始問(wèn)題是無(wú)法取到的，否則極值問(wèn)題無(wú)解。很容易驗(yàn)證對(duì)于這些不滿(mǎn)足約束條件的 x 有 z(x)=∞，這也和原始問(wèn)題是一致的，因?yàn)榍笞钚≈档玫綗o(wú)窮大可以和“無(wú)解”看作是相容的。

到這里，我們成功把帶約束問(wèn)題轉(zhuǎn)化為了無(wú)約束問(wèn)題，不過(guò)這其實(shí)只是一個(gè)形式上的重寫(xiě)，并沒(méi)有什么本質(zhì)上的改變。我們只是把原來(lái)的問(wèn)題通過(guò) Lagrangian 寫(xiě)作了如下形式：

minx?maxλ?0,νL(x,λ,ν)

這個(gè)問(wèn)題（或者說(shuō)原始的帶約束的形式）稱(chēng)作 primal problem 。如果你看過(guò)之前關(guān)于 SVM 的推導(dǎo)，那么肯定就知道了，相對(duì)應(yīng)的還有一個(gè) dual problem ，其形式非常類(lèi)似，只是把 min 和 max 交換了一下：

maxλ?0,ν?minxL(x,λ,ν)

交換之后的 dual problem 和原來(lái)的 primal problem 并不相等，直觀(guān)地，我們可以這樣來(lái)理解：胖子中最瘦的那個(gè)都比瘦骨精中最胖的那個(gè)要胖。當(dāng)然這是很不嚴(yán)格的說(shuō)法，而且扣字眼的話(huà)可以糾纏不休，所以我們還是來(lái)看嚴(yán)格數(shù)學(xué)描述。和剛才的 z(x) 類(lèi)似，我們也用一個(gè)記號(hào)來(lái)表示內(nèi)層的這個(gè)函數(shù)，記：

g(λ,ν)=minxL(x,λ,ν)

并稱(chēng) g(λ,ν) 為 Lagrange dual function （不要和 L 的 Lagrangian 混淆了）。g 有一個(gè)很好的性質(zhì)就是它是 primal problem 的一個(gè)下界。換句話(huà)說(shuō)，如果 primal problem 的最小值記為 p? ，那么對(duì)于所有的 λ?0 和 ν ，我們有：

g(λ,ν)≤p?

因?yàn)閷?duì)于極值點(diǎn)（實(shí)際上包括所有滿(mǎn)足約束條件的點(diǎn)）x?，注意到 λ?0 ，我們總是有

∑i=1mλifi(x?)+∑i=1pνihi(x?)≤0

因此

L(x?,λ,ν)=f0(x?)+∑i=1mλifi(x?)+∑i=1pνihi(x?)≤f0(x?)

于是

g(λ,ν)=minxL(x,λ,ν)≤L(x?,λ,ν)≤f0(x?)=p?

這樣一來(lái)就確定了 g 的下界性質(zhì)，于是

maxλ?0,νg(λ,ν)

實(shí)際上就是最大的下界。這是很自然的，因?yàn)榈玫较陆缰?#xff0c;我們自然地就希望得到最好的下界，也就是最大的那一個(gè)——因?yàn)樗x我們要逼近的值最近呀。記 dual problem 的最優(yōu)值為 d? 的話(huà)，根據(jù)上面的推導(dǎo)，我們就得到了如下性質(zhì)：

d?≤p?

這個(gè)性質(zhì)叫做 weak duality ，對(duì)于所有的優(yōu)化問(wèn)題都成立。其中 p??d? 被稱(chēng)作 duality gap 。需要注意的是，無(wú)論 primal problem 是什么形式，dual problem 總是一個(gè) convex optimization 的問(wèn)題——它的極值是唯一的（如果存在的話(huà)），并且有現(xiàn)成的軟件包可以對(duì)凸優(yōu)化問(wèn)題進(jìn)行求解（雖然求解 general 的 convex optimization 實(shí)際上是很慢并且只能求解規(guī)模較小的問(wèn)題的）。這樣一來(lái)，對(duì)于那些難以求解的 primal problem （比如，甚至可以是 NP 問(wèn)題），我們可以通過(guò)找出它的 dual problem ，通過(guò)優(yōu)化這個(gè) dual problem 來(lái)得到原始問(wèn)題的一個(gè)下界估計(jì)。或者說(shuō)我們甚至都不用去優(yōu)化這個(gè) dual problem ，而是（通過(guò)某些方法，例如隨機(jī)）選取一些 λ?0 和 ν ，帶到 g(λ,ν) 中，這樣也會(huì)得到一些下界（只不過(guò)不一定是最大的那個(gè)下界而已）。當(dāng)然要選 λ 和 ν 也并不是總是“隨機(jī)選”那么容易，根據(jù)具體問(wèn)題，有時(shí)候選出來(lái)的 λ 和 ν 帶入 g 會(huì)得到 ?∞ ，這雖然是一個(gè)完全合法的下界，然而卻并沒(méi)有給我們帶來(lái)任何有用的信息。

故事到這里還沒(méi)有結(jié)束，既然有 weak duality ，顯然就會(huì)有 strong duality 。所謂 strong duality ，就是

d?=p?

這是一個(gè)很好的性質(zhì)，strong duality 成立的情況下，我們可以通過(guò)求解 dual problem 來(lái)優(yōu)化 primal problem ，在 SVM 中我們就是這樣做的。當(dāng)然并不是所有的問(wèn)題都能滿(mǎn)足 strong duality ，在講 SVM 的時(shí)候我們直接假定了 strong duality 的成立，這里我們就來(lái)提一下 strong duality 成立的條件。不過(guò)，這個(gè)問(wèn)題如果要講清楚，估計(jì)寫(xiě)一本書(shū)都不夠，應(yīng)該也有不少專(zhuān)門(mén)做優(yōu)化方面的人在研究這相關(guān)的問(wèn)題吧，我沒(méi)有興趣（當(dāng)然也沒(méi)有精力和能力）來(lái)做一個(gè)完整的介紹，相信大家也沒(méi)有興趣來(lái)看這樣的東西——否則你肯定是專(zhuān)門(mén)研究?jī)?yōu)化方面的問(wèn)題的了，此時(shí)你肯定比我懂得更多，也就不用看我寫(xiě)的介紹啦。

所以，這里我們就簡(jiǎn)要地介紹一下 Slater 條件和 KKT 條件。Slater 條件是指存在嚴(yán)格滿(mǎn)足約束條件的點(diǎn) x ，這里的“嚴(yán)格”是指 fi(x)≤0 中的“小于或等于號(hào)”要嚴(yán)格取到“小于號(hào)”，亦即，存在 x 滿(mǎn)足

fi(x)<0hi(x)=0i=1,…,mi=1,…,p 我們有：如果原始問(wèn)題是 Convex 的并且滿(mǎn)足 Slater 條件的話(huà)，那么 strong duality 成立。需要注意的是，這里只是指出了 strong duality 成立的一種情況，而并不是唯一情況。例如，對(duì)于某些非 convex optimization 的問(wèn)題，strong duality 也成立。這里我們不妨回顧一下 SVM 的 primal problem ，那是一個(gè) convex optimization 問(wèn)題（QP 是凸優(yōu)化問(wèn)題的一種特殊情況），而 Slater 條件實(shí)際上在這里就等價(jià)于是存在這樣的一個(gè)超平面將數(shù)據(jù)分隔開(kāi)來(lái)，亦即是“數(shù)據(jù)是可分的”。當(dāng)數(shù)據(jù)不可分是，strong duality 不能成立，不過(guò)，這個(gè)時(shí)候我們尋找分隔平面這個(gè)問(wèn)題本身也就是沒(méi)有意義的了，至于我們?nèi)绾瓮ㄟ^(guò)把數(shù)據(jù)映射到特征空間中來(lái)解決不可分的問(wèn)題，這個(gè)當(dāng)時(shí) 已經(jīng)介紹過(guò)了，這里就不多說(shuō)了。

讓我們回到 duality 的話(huà)題。來(lái)看看 strong duality 成立的時(shí)候的一些性質(zhì)。假設(shè) x? 和 (λ?,ν?) 分別是 primal problem 和 dual problem 的極值點(diǎn)，相應(yīng)的極值為 p? 和 d? ，首先 p?=d? ，此時(shí)我們可以得到

f0(x?)=g(λ?,ν?)=minx(f0(x)+∑i=1mλ?ifi(x)+∑i=1pν?ihi(x))≤f0(x?)+∑i=1mλ?ifi(x?)+∑i=1pν?ihi(x?)≤f0(x?)

由于兩頭是相等的，所以這一系列的式子里的不等號(hào)全部都可以換成等號(hào)。根據(jù)第一個(gè)不等號(hào)我們可以得到 x? 是 L(x,λ?,ν?) 的一個(gè)極值點(diǎn)，由此可以知道 L(x,λ?,ν?) 在 x? 處的梯度應(yīng)該等于 0 ，亦即：

?f0(x?)+∑i=1mλ?i?fi(x?)+∑i=1pν?i?hi(x?)=0

此外，由第二個(gè)不等式，又顯然 λ?ifi(x?) 都是非正的，因此我們可以得到

λ?ifi(x?)=0,i=1,…,m

這個(gè)條件叫做 complementary slackness 。顯然，如果 λ?i>0，那么必定有 fi(x?)=0 ；反過(guò)來(lái)，如果 fi(x?)<0 那么可以得到 λ?i=0 。這個(gè)條件正是我們?cè)诮榻B支持向量的文章末尾時(shí)用來(lái)證明那些非支持向量（對(duì)應(yīng)于 fi(x?)<0）所對(duì)應(yīng)的系數(shù) αi （在本文里對(duì)應(yīng) λi ）是為零的。 :) 再將其他一些顯而易見(jiàn)的條件寫(xiě)到一起，就是傳說(shuō)中的 KKT (Karush-Kuhn-Tucker) 條件：

fi(x?)≤0,hi(x?)=0,λ?i≥0,λ?ifi(x?)=0,?f0(x?)+∑mi=1λ?i?fi(x?)+∑pi=1ν?i?hi(x?)=0i=1,…,mi=1,…,pi=1,…,mi=1,…,m 任何滿(mǎn)足 strong duality （不一定要求是通過(guò) Slater 條件得到，也不一定要求是凸優(yōu)化問(wèn)題）的問(wèn)題都滿(mǎn)足 KKT 條件，換句話(huà)說(shuō)，這是 strong duality 的一個(gè)必要條件。不過(guò)，當(dāng)原始問(wèn)題是凸優(yōu)化問(wèn)題的時(shí)候（當(dāng)然還要求一應(yīng)函數(shù)是可微的，否則 KKT 條件的最后一個(gè)式子就沒(méi)有意義了），KKT 就可以升級(jí)為充要條件。換句話(huà)說(shuō)，如果 primal problem 是一個(gè)凸優(yōu)化問(wèn)題，且存在 x? 和 (λ?,ν?) 滿(mǎn)足 KKT 條件，那么它們分別是 primal problem 和 dual problem 的極值點(diǎn)并且 strong duality 成立。 其證明也比較簡(jiǎn)單，首先 primal problem 是凸優(yōu)化問(wèn)題的話(huà)， g(λ,ν)=minxL(x,λ,ν) 的求解對(duì)每一組固定的 (λ,ν) 來(lái)說(shuō)也是一個(gè)凸優(yōu)化問(wèn)題，由 KKT 條件的最后一個(gè)式子，知道 x? 是 minxL(x,λ?,ν?) 的極值點(diǎn)（如果不是凸優(yōu)化問(wèn)題，則不一定能推出來(lái)），亦即： g(λ?,ν?)=minxL(x,λ?,ν?)=L(x?,λ?,ν?)=f0(x?)+∑i=1mλ??ifi(x?)+∑i=1pνi??hi(x?)=f0(x?) 最后一個(gè)式子是根據(jù) KKT 條件的第二和第四個(gè)條件得到。由于 g 是 f0 的下界，這樣一來(lái)，就證明了 duality gap 為零，也就是說(shuō)，strong duality 成立。 到此為止，做一下總結(jié)。我們簡(jiǎn)要地介紹了 duality 的概念，基本上沒(méi)有給什么具體的例子。不過(guò)由于內(nèi)容比較多，為了避免文章超長(zhǎng)，就挑了一些重點(diǎn)講了一下。總的來(lái)說(shuō)，一個(gè)優(yōu)化問(wèn)題，通過(guò)求出它的 dual problem ，在只有 weak duality 成立的情況下，我們至少可以得到原始問(wèn)題的一個(gè)下界。而如果 strong duality 成立，則可以直接求解 dual problem 來(lái)解決原始問(wèn)題，就如同經(jīng)典的 SVM 的求解過(guò)程一樣。有可能 dual problem 比 primal problem 更容易求解，或者 dual problem 有一些優(yōu)良的結(jié)構(gòu)（例如 SVM 中通過(guò) dual problem 我們可以將問(wèn)題表示成數(shù)據(jù)的內(nèi)積形式從而使得 kernel trick 的應(yīng)用成為可能）。此外，還有一些情況會(huì)同時(shí)求解 dual 和 primal problem ，比如在迭代求解的過(guò)程中，通過(guò)判斷 duality gap 的大小，可以得出一個(gè)有效的迭代停止條件。

總結(jié)

以上是生活随笔為你收集整理的duality的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。