本文轉(zhuǎn)自徐飛翔的“《SVM筆記系列之四》最優(yōu)化問題的對(duì)偶問題”

版權(quán)聲明：本文為博主原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明。

對(duì)偶問題

最優(yōu)化問題存在對(duì)偶問題，所謂對(duì)偶問題，源于這個(gè)思想：

原始問題比較難以求解，通過構(gòu)建其對(duì)偶問題，期望解決這個(gè)對(duì)偶問題得到其原問題的下界（在弱對(duì)偶情況下，對(duì)于最小化問題來說），或者得到原問題的解（強(qiáng)對(duì)偶情況下）。

在SVM中，因?yàn)槠鋵儆?strong>凸優(yōu)化問題，因此是強(qiáng)對(duì)偶問題，可以通過構(gòu)建對(duì)偶問題解決得到原問題的解。我們舉一個(gè)線性規(guī)劃中一個(gè)經(jīng)典問題，描述如下：

某工廠有兩種原料A、B，而且能用其生產(chǎn)兩種產(chǎn)品：

生產(chǎn)第一種產(chǎn)品需要2個(gè)A和4個(gè)B，能夠獲利6；生產(chǎn)第二種產(chǎn)品需要3個(gè)A和2個(gè)B，能夠獲利4；此時(shí)共有100個(gè)A和120個(gè)B，問該工廠最多獲利多少？可以簡(jiǎn)單得到其問題的數(shù)學(xué)表達(dá)式為：

當(dāng)然，得到這個(gè)式子的根據(jù)就是最大化其賣出去的產(chǎn)品的利潤(rùn)。但是，如果只問收益的話，明顯地，還可以考慮賣出原材料A和B的手段，前提就是賣出原材料的盈利會(huì)比生產(chǎn)商品盈利高，假設(shè)產(chǎn)品A和產(chǎn)品B的單價(jià)為和，從這個(gè)角度看，只要最小化購買原材料的價(jià)格，我們就可以得出另一個(gè)數(shù)學(xué)表達(dá)式：

其實(shí)，我們可以發(fā)現(xiàn)這其實(shí)是極大極小問題和其對(duì)偶問題，極小極大問題。

一些定義原始問題我們要討論原問題和對(duì)偶問題，就需要一些定義，我們給出原始問題的非拉格朗日函數(shù)表達(dá)形式如式子( 1.1 ) 所示，引進(jìn)其廣義拉格朗日函數(shù)：

其中，而和是拉格朗日乘子，其中由KKT條件有，考慮關(guān)于的函數(shù)：

這里下標(biāo)P 用以表示這個(gè)是原始問題。聯(lián)想到我們?cè)谖恼隆禨VM的拉格朗日函數(shù)表示以及其對(duì)偶問題》中一些關(guān)于對(duì)偶問題的討論，我們知道其實(shí)( 3.2 )中的其實(shí)就表示了( 1.1 ) 中的原問題的目標(biāo)函數(shù)和其約束條件，這里再探討一下：假設(shè)我們存在一個(gè)x，使得x違反原始問題的約束條件，從而有或者，那么我們可以推論出：

為什么呢？ 因?yàn)槿舸嬖谀硞€(gè)i使得， 那么就可以令使得取得無窮大這個(gè)“最大值”；同樣的，若存在一個(gè)j使得， 那么就總是可以使得讓， 而其他各個(gè)和均取為0（滿足約束條件的拉格朗日乘子取為0）。這樣，只有對(duì)于滿足約束條件的i和j，才會(huì)有成立。 于是我們有這個(gè)分段表達(dá)式：

所以，如果是最小化問題，我們有極小極大問題(3.5):

其與式子( 1.1 )是完全等價(jià)的，有著同樣的解。這樣一來，我們就把原始的最優(yōu)化問題轉(zhuǎn)換為了廣義拉格朗日函數(shù)的極小極大問題，為了后續(xù)討論方便，我們記：

其中 為問題的解。

極小極大問題的對(duì)偶， 極大極小問題我們定義：

在考慮極大化( 3.7 )有：

式子( 3.8 ) 稱為廣義拉格朗日函數(shù)的極大極小問題，將其變成約束形式，為：

式子(3.9) 被稱為原問題的對(duì)偶問題，定義其最優(yōu)解為：

實(shí)際上，通過這種方法我們可以將式子(2.1) 轉(zhuǎn)化為式子(2.2) ，也就是將原問題轉(zhuǎn)化為對(duì)偶問題，有興趣的朋友可以自行嘗試。

原始問題和對(duì)偶問題的關(guān)系正如前面所談到的，原始問題的解和對(duì)偶問題的解存在一定的關(guān)系，對(duì)于任意的，我們有：

等價(jià)于：

注意，式子(4.2) 對(duì)于所有的都成立，因?yàn)樵紗栴}和對(duì)偶問題均有最優(yōu)解，所以有：

容易得到：

由此我們得到了在最小化問題中的結(jié)論，這個(gè)稱為弱對(duì)偶。弱對(duì)偶指出，解決最小化問題的對(duì)偶問題可以得到原問題的解的下界。

既然有弱對(duì)偶就會(huì)存在強(qiáng)對(duì)偶。強(qiáng)對(duì)偶指的是的情況，在某些情況下，原始問題和對(duì)偶問題的解相同，這時(shí)可以用解決對(duì)偶問題來代替原始問題，下面以定理的方式給出強(qiáng)對(duì)偶成立的重要條件而不予以證明：

考慮原始問題(1.1) 和對(duì)偶問題(3.9)，假設(shè)和都是凸函數(shù)， 是仿射函數(shù)，并且不等式約束是嚴(yán)格可行的，既存在 X，對(duì)所有i有 ，則存在，使得 是原始問題的解， 是對(duì)偶問題的解（滿足這個(gè)條件的充分必要條件就是滿足KKT條件1），并且：

引用

1. 最優(yōu)化問題學(xué)習(xí)筆記1-對(duì)偶理論 CSDN
2. 《統(tǒng)計(jì)學(xué)習(xí)方法》 豆瓣
3. 如何理解對(duì)偶問題？ feng liu的回答
4. 《拉格朗日乘數(shù)法和KKT條件的直觀解釋》 CSDN
5. SVM的拉格朗日函數(shù)表示以及其對(duì)偶問題 CSDN

1. 見《拉格朗日乘數(shù)法和KKT條件的直觀解釋》