在硬间隔支持向量机中，问题的求解可以转化为凸二次规划问题：
minw,b12||w||2s.t.yi(wTxi+b)≥1,i=1,2,⋯,m.(1)(2)(1)
(1)
(1)
min
w
,
b
1
2
|
|
w
|
|
2
(2)
s
.
t
.
y
i
(
w
T
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
⋯
,
m
.
<script type="math/tex; mode=display" id="MathJax-Element-1">\begin{align}
&\min_{\boldsymbol w, b}{\frac 1 2}||\boldsymbol w||^2\\
&s.t. y_i(\boldsymbol w^T\boldsymbol x_i+b)\geq1, i=1,2,\cdots,m.\\
\end{align} \tag{1}</script>
如何得到该式的可参考：
支持向量机
理解一
minw,bmaxαi≥0{12||w||2+∑i=1mαi(1−yi(wTxi+b))}(2)
(2)
min
w
,
b
max
α
i
≥
0
{
1
2
|
|
w
|
|
2
+
∑
i
=
1
m
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
}
<script type="math/tex; mode=display" id="MathJax-Element-18">\min_{\boldsymbol w, b} \max_{\alpha_i \geq 0} \left\{{\frac 1 2}||\boldsymbol w||^2 + \sum_{i=1}^m\alpha_i(1 - y_i(\boldsymbol w^T\boldsymbol x_i+b))\right\} \tag{2}</script>
上式等价于原问题，因为若满足(1)中不等式约束，则(2)式求max时，
αi(1−yi(wTxi+b))
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
<script type="math/tex" id="MathJax-Element-19">\alpha_i(1 - y_i(\boldsymbol w^T\boldsymbol x_i+b))</script>必须取0，与(1)等价；若不满足(1)中不等式约束，(2)中求max会得到无穷大。
交换min和max获得其对偶问题
maxαi≥0minw,b{12||w||2+∑i=1mαi(1−yi(wTxi+b))}
max
α
i
≥
0
min
w
,
b
{
1
2
|
|
w
|
|
2
+
∑
i
=
1
m
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
}
<script type="math/tex; mode=display" id="MathJax-Element-20">\max_{\alpha_i \geq 0} \min_{\boldsymbol w, b} \left\{{\frac 1 2}||\boldsymbol w||^2 + \sum_{i=1}^m\alpha_i(1 - y_i(\boldsymbol w^T\boldsymbol x_i+b))\right\} </script>
交换之后的对偶问题和原问题并不相等，直观地，我们可以这样来理解：胖子中最瘦的那个都比瘦子中最胖的那个要胖。故上式的解小于等于原问题的解。当然这是很不严格的说法，而且扣字眼的话可以纠缠不休，所以我们还是来看其他严格数学意义上的理解。
理解二
现在的问题是如何找到问题(1) 的最优值的一个最好的下界?
12||w||2<v1−yi(wTxi+b)≤0(3)
(3)
1
2
|
|
w
|
|
2
<
v
1
−
y
i
(
w
T
x
i
+
b
)
≤
0
<script type="math/tex; mode=display" id="MathJax-Element-5">{\frac 1 2}||\boldsymbol w||^2 < v\\
1 - y_i(\boldsymbol w^T\boldsymbol x_i+b) \leq 0\tag{3}</script>
若方程组(3)无解， 则v是问题(1)的一个下界。
若(3)有解， 则
∀α>0, minw,b{12||w||2+∑i=1mαi(1−yi(wTxi+b))}<v
∀
α
>
0
,
min
w
,
b
{
1
2
|
|
w
|
|
2
+
∑
i
=
1
m
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
}
<
v
<script type="math/tex; mode=display" id="MathJax-Element-6">\forall \boldsymbol \alpha > 0 , \ \min_{\boldsymbol w, b} \left\{{\frac 1 2}||\boldsymbol w||^2 + \sum_{i=1}^m\alpha_i(1 - y_i(\boldsymbol w^T\boldsymbol x_i+b))\right\} < v</script>
由逆否命题得：若
∃α>0, minw,b{12||w||2+∑i=1mαi(1−yi(wTxi+b))}≥v
∃
α
>
0
,
min
w
,
b
{
1
2
|
|
w
|
|
2
+
∑
i
=
1
m
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
}
≥
v
<script type="math/tex; mode=display" id="MathJax-Element-7">\exists \boldsymbol \alpha > 0 , \ \min_{\boldsymbol w, b} \left\{{\frac 1 2}||\boldsymbol w||^2 + \sum_{i=1}^m\alpha_i(1 - y_i(\boldsymbol w^T\boldsymbol x_i+b))\right\} \geq v</script>
则(3)无解。
那么v是问题(1)的一个下界。
要求得一个好的下界，取最大值即可
maxαi≥0minw,b{12||w||2+∑i=1mαi(1−yi(wTxi+b))}
max
α
i
≥
0
min
w
,
b
{
1
2
|
|
w
|
|
2
+
∑
i
=
1
m
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
}
<script type="math/tex; mode=display" id="MathJax-Element-8">\max_{\alpha_i \geq 0} \min_{\boldsymbol w, b} \left\{{\frac 1 2}||\boldsymbol w||^2 + \sum_{i=1}^m\alpha_i(1 - y_i(\boldsymbol w^T\boldsymbol x_i+b))\right\}</script>
理解三
令
L(w,b,a)=12||w||2+∑i=1mαi(1−yi(wTxi+b))
L
(
w
,
b
,
a
)
=
1
2
|
|
w
|
|
2
+
∑
i
=
1
m
α
i
(
1
−
y
i
(
w
T
x
i
+
b
)
)
<script type="math/tex; mode=display" id="MathJax-Element-9"> L(\boldsymbol w, b,\boldsymbol a) = {\frac 1 2}||\boldsymbol w||^2 + \sum_{i=1}^m\alpha_i(1 - y_i(\boldsymbol w^T\boldsymbol x_i+b))</script>
p∗
p
∗
<script type="math/tex" id="MathJax-Element-10">p^*</script>为原问题的最小值，对应的
w
w
<script type="math/tex" id="MathJax-Element-11">\boldsymbol w</script> b分别为
w∗
w
∗
<script type="math/tex" id="MathJax-Element-12">\boldsymbol w^*</script>和
b∗
b
∗
<script type="math/tex" id="MathJax-Element-13">b^*</script>，则对于任意的
a>0
a
>
0
<script type="math/tex" id="MathJax-Element-14">\boldsymbol a > 0</script>：
p∗=12||w∗||2≥L(w∗,b,a)≥minw,bL(w,b,a)
p
∗
=
1
2
|
|
w
∗
|
|
2
≥
L
(
w
∗
,
b
,
a
)
≥
min
w
,
b
L
(
w
,
b
,
a
)
<script type="math/tex; mode=display" id="MathJax-Element-15">p^* = {\frac 1 2}||\boldsymbol w^*||^2 \geq L(\boldsymbol w^*, b,\boldsymbol a) \geq \min_{\boldsymbol w, b} L(\boldsymbol w, b,\boldsymbol a)</script>
那么
minw,bL(w,b,a)
min
w
,
b
L
(
w
,
b
,
a
)
<script type="math/tex" id="MathJax-Element-16">\min_{\boldsymbol w, b} L(\boldsymbol w, b,\boldsymbol a)</script>是问题(1)的一个下界。
要求得一个好的下界，取最大值即可
maxαi≥0minw,bL(w,b,a)
max
α
i
≥
0
min
w
,
b
L
(
w
,
b
,
a
)
<script type="math/tex; mode=display" id="MathJax-Element-17">\max_{\alpha_i \geq 0} \min_{\boldsymbol w, b} L(\boldsymbol w, b,\boldsymbol a)</script>
参考：如何通俗地讲解对偶问题
1
0
已为社区贡献2条内容
所有评论(0)