# 支持向量机（2）：对偶支持向量机

| |

## 拉格朗日对偶问题

1. 任意violating的$(b,\mathbf w)$：$\max\limits_{\mbox{all } \alpha_n\geq 0}\left(\square+\sum_n\alpha_n(\mbox{some positive})\right)\rightarrow\infty$；
2. 任意feasible的$(b,\mathbf w)$：$\max\limits_{\mbox{all } \alpha_n\geq 0}\left(\square+\sum_n\alpha_n(\mbox{all non-positive})\right)=\square$。

## KKT条件

1. 原问题可行：$y_n(\mathbf w^T\mathbf z_n+b)\geq 1$；
2. 对偶问题可行：$\alpha_n\geq 0$；
3. 对偶问题内最优化：$\sum_{n=1}^N\alpha_ny_n=0;\mathbf w=\sum_{n=1}^N\alpha_ny_n\mathbf z_n$；
4. 原问题内最优化：$\alpha_n\left(1-y_n\left(\mathbf w^T\mathbf z_n+b\right)\right)=0$，这个条件也称为complementary slackness，其中至少一项为$0$。

## ####Example

For a single variable $w$, consider minimizing ${1\over 2}w^2$ subject to two linear constraints $w\geq 1$ and $w\leq 3$. We know that the Lagrange function $\mathcal L(w,\alpha)={1\over 2}w^2+\alpha_1(1-w)+\alpha_2(w-3)$. Which of the following equations that contain $\alpha$ are among the KKT conditions of the optimization problem?

1. $\alpha_1\geq 0$ and $\alpha_2\geq 0$
2. $w=\alpha_1-\alpha_2$
3. $\alpha_1(1-w)=0$ and $\alpha_2(w-3)=0$
4. all of the above

## 支持向量

$\alpha_n>0$对应的点一定在边界上，这些点称为支持向量。也有些在边界上的点，对应的$\alpha_n$不一定大于$0$。容易发现，计算$b$和$\mathbf w$只需要支持向量就够了。