拉格朗日對偶

2拉格朗日對偶(Lagrangeduality)先拋開上面的二次規(guī)劃問題，先來看看存在等式約束的極值問題求法，比如下面的最優(yōu)化問題：mi%/(w)s.t.h^w)=0,電=L…，I,目標函數(shù)是f(w)，下面是等式約束。通常解法是引入拉格朗日算子，這里使用來表示算子，得到拉格朗日公式為1=/(w)-￡月冼加)L是等式約束的個數(shù)。然后分別對w和求偏導，使得偏導數(shù)等于0，然后解出w和六。至于為什么引入拉格朗日算子可以求出極值，原因是f(w)的dw變化方向受其他不等式的約束，dw的變化方向與f(w)的梯度垂直時才能獲得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關系。(參考《最優(yōu)化與KKT條件》)然后我們探討有不等式約束的極值問題求法，問題如下：mi%f(w)s.t.(w)<0,i—1,...,fc=0.2=1,.—,/,我們定義一般化的拉格朗日公式kI￡(wq目)=f(w)+￡o■攻(u，)+￡/Jihi(w').i=1i=l這里的Q和阡都是拉格朗日算子。如果按這個公式求解，會出現(xiàn)問題，因為我們求解的是最小值，而這里的必"、‘已經(jīng)不是0了，我們可以將Q調整成很大的正值，來使最后的函數(shù)結果是負無窮。因此我們需要排除這種情況，我們定義下面的函數(shù)：Hp(ic)=maxC(w.a,/3).:Qi>0這里的P代表primal。假設或者'='-，那么我們總是可以調整心和「'?：來使得有最大值為正無窮。而只有g和h滿足約束時，「‘??雄以為f(w)。這個函數(shù)的精妙之處在于""，而且求極大值。因此我們可以寫作/(w)ifwsatisfiesprimalconstraintsocotherwise.這樣我們原來要求的minf(w)可以轉換成求□二二了。minHp(ic)=minmaxC(w./?),我們使用'來表示二。如果直接求解，首先面對的是兩個參數(shù)，而，?:也是不等式約束，然后再在w上求最小值。這個過程不容易做，那么怎么辦呢？目)=血11￡(叫皿8).我們先考慮另外一個問題--D的意思是對偶，'項"將問題轉化為先求拉格朗日關于w的最小值，將和看%(%0)作是固定值。之后在-求最大值的話：maxff)=maxmin￡(w,a.3).a.,(3:Qj>0:ctj>0w這個問題是原問題的對偶問題，相對于原問題只是更換了min和max的順序，而一般更換順序的結果是MaxMin(X)<=MinMax(X)。然而在這里兩者相等。用…來表示對偶問題如下：d*—maxnii)ia./3)<minmax饑=p*,:ctj>0'—ii1口歸：cti>0下面解釋在什么條件下兩者會等價。假設f和g都是凸函數(shù)，h是仿射的(affine，11，-T1?：.：.*?：」-■■■：■■■：=■■■.'-：■：)。并且存在w使得對于所有的i，：：‘。在這種假設下，一定存在''"‘『使得如是原問題的解，?是對偶問題的解。還有：二::=另外;""”『滿足庫恩-塔克條件（Karush-Kuhn-Tucker,KKTcondition），該條件如下：二￡0儼）OWj=o,1…=0,4=1-=o,0=1…⑸佛伽*）<0,0=1…a>0,1=1^⑦所以如果"'戶'滿足了庫恩-塔克條件，那么他們就是原問題和對偶問題的解。讓我們再次審視公式（5），這個條件稱作是KKTdualcomplementarity條件。這個條件隱含了如果n七那么,"「'■='。也就是說；'，'='時，w處于可行域的邊界上，這時才是起作用的約束。而其他位于可行域內部（.”?"：」的）點都是不起作用的約束，其='。這個KKT雙重補足條件會用來解釋支持向量和SMO的收斂測試。這部分內容思路比較凌亂，還需要先研究下《非線性規(guī)劃》中的約束極值問題，再回頭看看。KKT的總體思想是將極值會在可行域邊界上取得，也就是不等式為0或等式約束里取得，而最優(yōu)下降方向一般是這些等式的線性組合，其中每個元素要么是不等式為0的約束，要么是等式約束。對于在可行域邊界內的點，對最優(yōu)解不起作用，因此前面的系數(shù)為0。最優(yōu)間隔分類器（optimalmarginclassifier）重新回到SVM的優(yōu)化問題：（w丁富⑴+6）>1,i=lm我們將約束條件改寫為：步愆）=—夕⑴（it，工⑴-F6）+1<0.從KKT條件得知只有函數(shù)間隔是1（離超平面最近的點）的線性約束式前面的系數(shù)=*。，也就是說這些約束式七對于其他的不在線上的點『技"：'），極值不會在他們所在的范圍內取得，因此前面的系數(shù)N='.注意每一個約束式實際就是一個訓練樣本?？聪旅娴膱D：實線是最大間隔超平面，假設X號的是正例，圓圈的是負例。在虛線上的點就是函數(shù)間隔是1的點，那么他們前面的系數(shù)"；"氣其他點都是='。這三個點稱作支持向量。構造拉格朗日函數(shù)如下：1m=弓|壯『一￡皿⑴+b)—I.i=l注意到這里只有心沒有是因為原問題中沒有等式約束，只有不等式約束。下面我們按照對偶問題的求解步驟來一步步進行，(T=maxminct,/3)皿日：皿蘭。w首先求解Z''的最小值，對于固定的"?：，’'’’—的最小值只與w和b有關。對w和b分別求偏導數(shù)。m6.Q)=邸一口謂⑴技司=01=11=1并得到mW=皿舟W⑴.i=t將上式帶回到拉格朗日函數(shù)中得到，此時得到的是該函數(shù)的最小值（目標函數(shù)是凸函數(shù)）代入后，化簡過程如下：1以w,b,oc)=云||w||2-2ci][y①(w「必+b)-1]i=lTOC\o"1-5"\h\z1mmm=-wrw—￡aiy^wrx^—｝a(y^b+>%:=1i=li=：l1mmmm=^w「>—2佐尹板丁工①—aty^b+｝缶i=lz=li=li=lmmmm=§w「.時⑴；t?—的y?W—｝aty^b+>缶i=li=li=l1mmm=-5>%y｛。耕)—￡a^y^b+>恥Z=1t=lt=l1mmm=—-WT2ff.y(OxW—b>WiV⑥+2(Ie

i=li=li=l/m\Tmi=l=-!(Y叫并或))Y叫W")-b弋時①+￡㈤^i=l/t=li=li=lmmmm=-江")(x"))T｝叫y①;t“)一&>住")+>產(chǎn)i=li=li=li=l1mmm=-5>%y｛。耕)—￡a^y^b+>恥Z=1t=lt=l1mmm=—-WT2ff.y(OxW—b>WiV⑥+2(Ie

i=li=li=l/m\Tm最后得到TOC\o"1-5"\h\zmimm￡（叫*）=Qt--舟護）皿的（弒司）71那）一i=l\o"CurrentDocument"i=]ij=\i=l由于最后一項是0,因此簡化為T71j771bq）=^2皿一弓V"W皿。JW）「工⑴\o"CurrentDocument"i=lij=1這里我們將向量內積表示為'此時的拉格朗日函數(shù)只包含了變量心。然而我們求出了”；才能得到w和b。（T=maxinin￡（w,a.B）接著是極大化的過程?二上：=冬匚"''-m十mmax^W(q)=皿—5$2小心W、i=1.ij=1s.t.ctj>07i—L...,mm/】mg—j1=1前面提到過對偶問題和原問題滿足的幾個條件，首先由于目標函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對于所有的i，?，:"'*'氣因此，一定存在”使得如是原問題的解，淇是對偶問題的解。在這里，求E就是求疽了。w—』/'盤1如果求出了：【，根據(jù)"即可求出w（也是，原問題的解）。然后max^.y（0=_1-min^.y（0=iw*Tx{t}b=2即可求出b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負的函數(shù)間隔。關于上面的對偶問題如何求解，將留給下一篇中的SMO算法來闡明。這里考慮另外一個問題，由于前面求解中得到mW=￡理少每掃日[=1我們通篇考慮問題的出發(fā)點是:?,根據(jù)求解得到的心，我們代入前式得到也就是說，以前新來的要分類的樣本首先根據(jù)w和b做一次線性運算，然后看求的結果是大于0還是小于0,來判斷正例還是負例?，F(xiàn)