《SVM筆記系列之四》最優(yōu)化問(wèn)題的對(duì)偶問(wèn)題

徐土豆 2022-04-01 09:49 234 閱讀 2 贊 1 收藏 0 評(píng)論

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

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

對(duì)偶問(wèn)題

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

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

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

某工廠有兩種原料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，問(wèn)該工廠最多獲利多少？可以簡(jiǎn)單得到其問(wèn)題的數(shù)學(xué)表達(dá)式為：

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

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

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

其中 $x=(x^{(1)}, x^{(2)}, \cdots, x^{(n)})^T \in R^n$ ，而 $\alpha_i$ 和 $\beta_j$ 是拉格朗日乘子，其中由KKT條件有 $\alpha_i \geq 0$ ，考慮關(guān)于的函數(shù)：

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

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

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

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

其中為問(wèn)題的解。

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

在考慮極大化( 3.7 )有：

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

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

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

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

等價(jià)于：

注意，式子(4.2) 對(duì)于所有的 $x, \alpha, \beta$ 都成立，因?yàn)樵紗?wèn)題和對(duì)偶問(wèn)題均有最優(yōu)解，所以有：

容易得到：

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

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

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