機器學習數學：拉格朗日對偶問題

02-27

對偶問題是利用拉格朗日對偶性將原始問題轉換為對偶問題，通過解對偶問題得到原始問題的解。優點是：

對偶問題往往更易於求解
自然引入核函數，推廣到非線性分類問題的求解

原始問題

我們以硬間隔svm的原始問題為例，求解一個約束最優化問題： $min_{w,b} quad frac{1}{2}|w|^2 \ s.t.quad y_i(wx_i+b)-1geq 0\ i=1,2..N$

（註：這個問題用二次規劃求解時複雜度與x的維度有關）

我們將這個問題一般化： $min_{xin R^n} quad f(x) \ s.t.quad c_i(x)leq 0 quad i=1,2..k\ quad quad quad h_j(x)= 0 quad j=1,2..l\$

極小極大問題

引入拉格朗日函數，由於約束條件有k+l個，所以我們有：

$L(x,alpha,eta)=f(x)+sum_{i=1}^{k}{alpha_ic_i(x)}+sum_{j=1}^{l}{eta_jh_j(x)}$

(求對x有限制條件的f(x)的最優化問題轉為對 $x,alpha,eta$ 沒有限制條件的 $L(x,alpha,eta)$ 極值問題)

其中 $alpha_i,eta_j$ 是拉格朗日乘子， $alpha_igeq 0$ ，我們再定義一個函數： $heta_p(x)=max_{alpha,eta,alpha_igeq0}L(x,alpha,eta)$

（註：在 $alpha，eta，alpha_igeq 0$ 條件下的最大值）

我們來研究這個函數： $heta_p(x)=max_{{alpha,eta,alpha_igeq0}}(f(x)+sum_{i=1}^{k}{alpha_ic_i(x)}+sum_{j=1}^{l}{eta_jh_j(x)})$

假設有一個x，使得不滿足原始問題的約束條件，即有c(x)>0或者h(x)!=0，那麼上式求max的解為無窮大，因為可以取 $alpha_i=infty,eta_jh_j(x)=infty$
相反，假設x滿足原始問題的約束條件，則上式最大值一定是 $alpha =0$ ，同時h(x)=0，所以上式的最大值的條件不存在了，即最大值就是一個定值f(x)
所以在x滿足原始問題約束的條件下， $heta_p(x)=f(x)$

所以，我們可以把原始問題中的s.t.條件去掉，得到原始問題的等價問題： $minlimits_{x}f(x)=minlimits_{x} heta_p(x)=minlimits_{x}max_{alpha,eta,alphageq0}L(x,alpha,eta)$

如果沒看懂，沒關係，現在來證明這個等式，即： $min_{xin R^n}f(x) quad s.t.quad c_i(x)leq 0(i=1,2..k), h_j(x)= 0(j=1,2..l)\ Updownarrow \ min_xmax_{{alpha,eta,alpha_igeq0}}(f(x)+sum_{i=1}^{k}{alpha_ic_i(x)}+sum_{j=1}^{l}{eta_jh_j(x)})=minlimits_{x} heta_p(x)$

$max_{{alpha,eta,alpha_igeq0}}(....)$ ：在x是常數的前提下，在取值範圍是max下標的條件下的，某個 $alpha，eta$ 使得後面括弧中取最大值。
$min_xmax_{{alpha,eta,alpha_igeq0}}(....)$ ：在上一步對x取值全部遍歷之後，得到的所有的最大值中的一個最小值。
將 $max_{{alpha,eta,alpha_igeq0}}(f(x)+sum_{i=1}^{k}{alpha_ic_i(x)}+sum_{j=1}^{l}{eta_jh_j(x)})$ 記做 $P(x)$
如果x滿足 $c_i(x)> 0或者h_j(x) e 0$ ，則 $P(x)$ 值無限大，則第一步就無解
如果x滿足 $c_i(x)leq 0或者h_j(x)= 0$ ，又有max下標的條件限制，則一定是 $sum_{i=1}^{k}{alpha_ic_i(x)}=0$ ， $sum_{j=1}^{l}{eta_jh_j(x)}=0$ ，則有： $max_{{alpha,eta,alpha_igeq0}}(f(x)+sum_{i=1}^{k}{alpha_ic_i(x)}+sum_{j=1}^{l}{eta_jh_j(x)})=max_{{alpha,eta,alpha_igeq0}}(f(x))=f(x)$
上式兩邊加 $min$ ，即證明得等價

綜上，我們得到原始問題等價於 $minlimits_{x}max_{alpha,eta,alphageq0}L(x,alpha,eta)$

對偶問題

（我可能是好多年沒碰高數了，上面一節要啰啰嗦嗦這麼多。。）

我們直接給出以下定理：

若原始問題和對偶問題都有最優值，則對偶問題最優值d? $leq$ 原始問題最優值p?：

（通俗點就是寧做鳳尾不做雞頭，鳳尾（右）是原始問題，雞頭（左）是對偶問題）

定理1易證明，參考統計學習方法或技法視頻，此處證明略。

即我們如果把對偶問題解決了，那就能得到原始問題的下限。

為什麼求解對偶問題

對於對偶問題來說，我們求解最小化部分時沒有任何限制條件，而沒有限制條件的最小化問題的解一定是在求得x的偏導數=0這處，那我們就能得到一些等式，將這些等式代入拉格朗日函數中就可以簡化計算（svm中可以最終把min消去，且得到一個只與 $alpha$ 有關的最大化問題）

KKT條件

推論1：設x?和α?,β?分別是原始問題和對偶問題的可行解，並且d?=p?，則x?和α?,β?分別是原始問題和對偶問題的最優解。

【即：如果某個解使得最優值相等，則這個解同時是原始和對偶問題的最優解】

定理2：考慮原始問題和對偶問題，假設函數f(x)和ci(x)是凸函數，hj(x)是仿射函數；並且假設不等式約束ci(x)是嚴格可行的，即存在x，對所有i有c_i(x)<0，則存在x?和α?,β?，使x?是原始問題的解，α?,β?是對偶問題的解，並且有p?=d?=L(x?,α?,β?).

【即：滿足某些條件下，最優解存在且使得最優值相等】

定理3： $x^?,α^?,β^?$ 分別是原始問題和對偶問題的解的充分必要條件是， $x^?,α^?,β^?$ 滿足下面的KKT條件：

$?_xL(x^?,α^?,β^?)=0\?_αL(x^?,α^?,β^?)=0\?_βL(x^?,α^?,β^?)=0quad(1)\α^?_ic_i(x^?)=0,i=1,2,?,kquad(2)\c_i(x^?)≤0,i=1,2,?,kquad(3)\α^?_i≥0,i=1,2,?,kquad(4)\h_j(x^?)=0,j=1,2,?,lquad(5)$

上式條件中1和2是最重要的，3、4、5都是將原始問題表示成拉格朗日函數時的條件。2稱為對偶互補條件，根據此條件，當 $α^?_i>0則c_i(x^?)=0$ 。

【即：在滿足KKT條件下，原始問題的求解可以轉換成對偶問題來求解，強對偶成立（等號成立），而強對偶成立，又一定滿足kkt條件】

兩天了，基本理解並寫完。

既然都看到這兒了，少年點個贊可好？感謝！

done 2017年11月23日16:51:58