支持向量機（原問題和對偶問題）

本文主要介紹原問題（PRIME PROBLEM）和對偶問題（DUAL PROBLEM），支持向量機優(yōu)化問題可通過原問題向?qū)ε紗栴}的轉(zhuǎn)化求解。

一、原問題的定義

原問題的定義為：

最小化：f(ω)；

限制條件：gi(ω)≤0，i=1~K；hi(ω)=0，i=1~M。

其中，ω為多維向量，限制條件中具有K個不等式（gi(ω)≤0），M個等式（hi(ω)=0）。

二、對偶問題的定義

首先定義函數(shù)：L(ω,α,β)=f(ω)+∑αigi(ω)+∑βihi(ω)；

該函數(shù)向量形式的定義：L(ω,α,β)=f(ω)+αTg(ω)+βTh(ω)；

該函數(shù)向量形式的定義中，α=[α1，α2,…,αK]T，β=[β1，β2,…,βM]T，g(ω)=[g1(ω)，g2(ω),…,gK(ω)]T，h(ω)=[h1(ω)，h2(ω),…,hM(ω)]T。

基于函數(shù)L(ω,α,β)的定義，原問題的對偶問題定義如下：

最大化：θ(α,β)=infL(ω,α,β)；

限制條件：αi≥0，i=1~K。

其中，infL(ω,α,β)為遍歷所有ω后，取值最小的L(ω,α,β)。

三、定理一

根據(jù)以上定義，可得出定理一：

如果ω*是原問題的解，(α*,β*)是對偶問題的解，則有： f(ω*)≥θ(α*,β*)

該定理的證明如下： θ(α*,β*)=infL(ω,α*,β*)（將α*、β*代入對偶函數(shù)的定義）

≤L(ω*,α*,β*)（此步推導(dǎo)由于infL(ω,α*,β*)的取值最小）

=f(ω*)+α*Tg(ω*)+β*Th(ω*)（此步推導(dǎo)根據(jù)L(ω,α,β)的定義）

≤f(ω*)（此步推導(dǎo)由于原問題的限制條件gi(ω)≤0，hi(ω)=0，對偶問題的限制條件αi≥0）

四、強對偶定理

將f(ω*)-θ(α*,β*)定義為對偶差距（DUALITY GAP），根據(jù)上述定理，對偶差距是大于等于零的函數(shù)。

如果g(ω)=Aω+b，h(ω)=Cω+d，f(ω)為凸函數(shù)，則有f(ω*)=θ(α*,β*)，此時對偶差距等于零。該定理為強對偶定理（STRONG DUALITY THEOREM）。

強對偶定理可更通俗地表述為：原問題的目標(biāo)函數(shù)（f(ω)）是凸函數(shù)，原問題的限制條件是線性函數(shù)，則原問題的解與對偶函數(shù)的解相等。

五、KKT條件

若f(ω*)=θ(α*,β*)，則有： f(ω*)+α*Tg(ω*)+β*Th(ω*)=f(ω*)； 即對于所有的i=1~K，要么αi=0，要么gi(ω*)=0（因為hi(ω)=0）。

該結(jié)論被稱為KKT條件，KKT分別代表先后獨立發(fā)現(xiàn)該結(jié)論的研究人員Karush、Kuhn、Tucker，該結(jié)論在Kuhn、Tucker發(fā)現(xiàn)后逐步被推廣。

審核編輯：劉清