QxRed

SVM的对偶问题为
min 1/2 a'Qa - a'e
s.t. 0<= a <= C e
     a' y = 0
其中a=[a1,...,an]', Q_{ij}=Kijyiyj, e=[1,...,1]', y=[y1,...,yn]'

记P=[x1y1,...,xnyn] (一个m*n的矩阵)
则上式可以化为标准形式：
min 1/2 a'P'Pa - a'e
s.t. -a<=0
     a-C e<=0
     a'y=0

对3个约束分别引入拉格朗日乘子μ,λ,b，则其对偶问题为
max_{μ,λ,b} min_a L(μ,λ,b,a) = 1/2 a'P'Pa - a'e - μ'a + λ'(a-C e) + b a'y
s.t. μ>=0 λ>=0

dL/da=0
=>
P'Pa-e-μ+λ+by=0
=>(-e-μ+λ+by)'a=-a'P'Pa
代入原目标函数，得
max_{μ,λ,b} -1/2 aP'Pa -  C λ'e
s.t. μ>=0 λ>=0
     P'Pa-e-μ+λ+by=0

记w=Pa则上式化为
min_{w,b,μ,λ} 1/2 w'w + C λ'e
s.t. P'w=e+μ-λ-by
     μ>=0 λ>=0           (1)

由P'w=e+μ-λ-by得
P'w+by-e+λ=μ>=0
=>
P'w+by>=e-λ
=>
(P'w)_i+(by)_i>=(e-λ)_i
=>
(xiyi)'w + b yi >= 1-λi
=>
yi(w'xi + b) >= 1-λi

因此(1)化为
min_{w,b} 1/2 w'w + C λ'e
s.t. yi(w'xi + b)>=1-λi    \forall i
     λ>=0
这就是SVM的原问题