# 第7章 序列最小最优化算法

SMO，sequential minimal optimization

## SMO的使用场景

SMO用于解决非线性支持向量机的对偶问题：

$$
\begin{aligned}
\min\_a \quad \sum\_{i=1}^N\sum\_{j=1}^Na\_ia\_jy\_iy\_jK(x\_i, x\_j) - \sum\_{i=1}^Na\_i  \\
s.t. \quad \sum\_{i=1}^Na\_iy\_i=0
\quad \quad 0 \le a\_i \le C, i=1,2,\cdots,N   && {1}
\end{aligned}
$$

## SMO的原理

如果所有变量$$a\_i$$都满足此问题的KKT条件。\
否则，选两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。\
由于这两个变量是互相制约的，可以用一个变量来表示另一个变量，因此只有一个自变量。\
解二次规划问题并更新变量。

## SMO的过程

1. 选择两个变量[link](https://windmising.gitbook.io/lihang-tongjixuexifangfa/smo/16)，假设两个变量为$$a\_1$$和$$a\_2$$  
2. 把公式（1）中的变量$$a\_1$$、$$a\_2$$和常量分开来写[link](https://windmising.gitbook.io/lihang-tongjixuexifangfa/smo/17)，成为公式（2）  

   $$
   \begin{aligned}
   L(a\_1, a\_2) = f(1,1)+2f(1,2)+f(2,2) \\
   +2\sum\_{j=3}^Nf(1,j) +2\sum\_{j=3}^Nf(2,j) \\
   -a\_1 - a\_2 + \text{常数项}&& {2}
   \end{aligned}
   $$

其中：

$$
f(i, j) = a\_ia\_jy\_iy\_jK(x\_i,x\_j)
$$

1. 根据$$a\_1$$和$$a\_2$$的关系，消息公式（2）中的变量$$a\_1$$，留下变量$$a\_2$$，得到公式（3）[link](https://windmising.gitbook.io/lihang-tongjixuexifangfa/smo/18)  
2. 公式（3）对$$a\_2$$求导，并令导数为0，得到$$a\_2$$的值[link](https://windmising.gitbook.io/lihang-tongjixuexifangfa/smo/19)。  
3. 第4步得到的$$a\_2$$没有考虑到公式（1）的限制条件，需要对$$a\_2$$做一些修剪[link](https://windmising.gitbook.io/lihang-tongjixuexifangfa/smo/20)  
4. 根据$$a\_2$$得到$$a\_1$$  

   $$
   a\_1 = \frac {-\xi - a\_2y\_2}{y\_1}
   $$
5. 根据新的$$a\_1$$和$$a\_2$$更新b[link](https://windmising.gitbook.io/lihang-tongjixuexifangfa/smo/21)  
6. 回到第1步，直至没有a可以更新