待求解问题

目标函数

$$ \begin{aligned}\min_{\alpha} & \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j K(x_i,x_j)-\sum_{i=1}^N\alpha_i\\\text { s.t } & \sum_{i=1}^N \alpha_i y_i=0\\ &0\leq \alpha_i\leq C(\forall i=1,2, \ldots n)\end{aligned} $$

且由KKT对偶互补条件有

$$ \begin{gathered}\alpha_i^=0 \Rightarrow y_i\left(w^ \bullet \phi\left(x_i\right)+b^\right) \geq 1 \\0<\alpha_i^<C \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^\right)=1 \\\alpha_i^=C \Rightarrow y_i\left(w^* \bullet \phi\left(x_i\right)+b^*\right) \leq 1\end{gathered} $$

SMO算法基本思想

上式中有N个变量$\alpha_1,\alpha_2,\ldots,\alpha_N$需要在极小化的时候求出，直接优化很难。

SMO采用启发式的方法，每次只优化两个变量，而将其它变量视为常数。

由$\sum_{i=1}^N \alpha_i y_i=0$知，假如$\alpha_3,\ldots,\alpha_N$固定，那么$\alpha_1,\alpha_2$的关系就确定了，从而转化为了一个比较简单的两变量优化问题。

$$ \begin{gathered}\min_{\alpha_1, \alpha_1} \frac{1}{2} K_{11} \alpha_1^2+\frac{1}{2} K_{22} \alpha_2^2+y_1 y_2 K_{12} \alpha_1 \alpha_2-\left(\alpha_1+\alpha_2\right)\\+y_1 \alpha_1 \sum_{i=3}^N y_i \alpha_i K_{i 1}+y_2 \alpha_2 \sum_{i=3}^N y_i \alpha_i K_{i 2} \\\text { s.t. } \alpha_1 y_1+\alpha_2 y_2=-\sum_{i=3}^N y_i \alpha_i=\varsigma \\0 \leq \alpha_i \leq C \quad i=1,2\end{gathered} $$

两变量优化——>单变量约束优化

符号说明：上一轮迭代得到的解$\alpha_1^{old},\alpha_2^{old}$，沿着约束方向未经剪辑的$\alpha_2$表示为$\alpha_2^{new,unc}$，本轮迭代完成后的解$\alpha_1^{new},\alpha_2^{new}$

约束条件