\[\bigtriangledown_wL(w,b,\xi,\alpha,u)=w-\sum_{i=1}^{N}\alpha_iy_ix_i=0\\
\bigtriangledown_bL(w,b,\xi,\alpha,u)=-\sum_{i=1}^{N}\alpha_iy_i=0\\
\bigtriangledown_{\xi}L(w,b,\xi,\alpha,u)=C-\alpha_i-u_i=0\]
上面都代入$L(w,b,\xi,\alpha,u)$，因此得到
\[\underset{w,b,\xi}{min}L(w,b,\xi,\alpha,u)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i\]
再对$\alpha_i$求极大，就是求下面极小
\[\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i\\
s.t.\quad \sum_{i=1}^{N}\alpha_iy_i=0\\
C-\alpha_i-u_i=0\\
\alpha_i\geq 0,u_i> 0\]
利用$C-\alpha_i=u_i$，$\alpha_i\geq 0$，$u_i> 0$可以写成
\[\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i\\
s.t.\quad \sum_{i=1}^{N}\alpha_iy_i=0\\
C\geq \alpha_i\geq 0,i=1,2,\cdots,N\]
定理：若存在一个分量$0\leq \alpha_j^*\leq C$，原始问题的解为
\[w^*=\sum_{i=1}^{N}a_i^*y_ix_i\\
b^*=y_j-(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)\]
证明：由KKT条件
\[\bigtriangledown_wL(w,b,\xi,\alpha,u)=w-\sum_{i=1}^{N}\alpha_iy_ix_i=0\\
\bigtriangledown_bL(w,b,\xi,\alpha,u)=-\sum_{i=1}^{N}\alpha_iy_i=0\\
\bigtriangledown_{\xi}L(w,b,\xi,\alpha,u)=C-\alpha_i-u_i=0\\
\alpha_i[y_i(w^{\mathrm{T}}x_i+b)-1+\xi_i]=0\\
u_i\xi_i=0\\
y_i(w^{\mathrm{T}}x_i+b)-1+\xi_i\geq 0\\
\alpha_i\geq 0,u_i> 0,\xi_i\geq 0\]
若存在一个分量$0\leq \alpha_j\leq C$，则
\[(C-\alpha_i)\xi_i=0\Rightarrow \xi_i=0\]
那么
\[\alpha_i[y_i(w^{\mathrm{T}}x_i+b)-1]=0\]
得到
\[y_i(w^{\mathrm{T}}x_i+b)-1=0\]
即
\[b^*=y_j-(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)\\
w=\sum_{i=1}^{N}\alpha_iy_ix_i\]
支持向量：在线性不可分的情况下，对偶问题中对应$0\leq \alpha_j^*\leq C$的样本点$(x_i,x_j)$称为软间隔的支持向量。情况更加复杂，分割平面是实线，边界是虚线。
这些支持向量或者在边界上，或者在边界内或外
若$0\leq \alpha_j^*\leq C$，$\xi_i=0$，则正好在边界上，称为支持向量，
若$\alpha_j^*=C$，$0< \xi_i<1$, 此时分类正确，在边界之间，
若$\alpha_j^*=C$，$\xi_i=1$, 此时在超平面上
若$\alpha_j^*=C$，$\xi_i>1$, 此时位于超平面的另一侧，误分的一侧
合页损失（hinge loss）函数：上面解释的线性支持向量机，学习策略是软间隔最大化，分离超平面是$y_i(w^{\mathrm{T}}x_i+b)=1$，学习算法是凸二次规划。
线性支持向量机另外一个解释就是最小化目标函数
\[\sum_{i=1}^{N}[y_i(w^{\mathrm{T}}x_i+b)-1]_+ +\lambda||w||^2\]
第一项是经验风险函数，又称为合页损失函数，下标+表示取正值
\[[z]_+=\left\{\begin{matrix}
z,z>0\\
0,z\leq 0
\end{matrix}\right.\]
也就是说当样本点$(x_i,y_i)$被正确分类，且函数间隔$y_i(w^{\mathrm{T}}x_i+b)>1$时，损失为0，否则损失就是$1-y_i(w^{\mathrm{T}}x_i+b)$。而第二项就是正则化项。
定理：线性支持向量机优化问题
\[\underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i\\
s.t.\quad y_j(w^*x_j+b^*)\geq 1-\xi_i,i=1,2,\cdots,N\\
\quad \quad \quad\xi_i\geq 0\]
等价于
\[\underset{w,b,\xi}{min}\sum_{i=1}^{N} [y_i(w^{\mathrm{T}}x_i+b)-1]_++\lambda||w||^2\]
证明：令
\[[1-y_j(w^*x_j+b^*)]_+=\xi_i\geq 0\]
因此当$1-y_j(w^*x_j+b^*)>0$
\[1-y_j(w^*x_j+b^*)=\xi_j\]
当$1-y_j(w^*x_j+b^*)<0$
\[0=\xi_j\]
所以约束条件成立
\[y_j(w^*x_j+b^*)\geq 1-\xi_i\]
这和原问题的约束条件是一致的，优化问题等价于
\[\underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i\]