Categories

Calendar

November 2010
M T W T F S S
« Oct   Dec »
1234567
891011121314
15161718192021
22232425262728
2930  

支持向量机:Duality

本文是“支持向量机系列”的番外篇(1),参见本系列的其他文章。

在之前关于 support vector 的推导中,我们提到了 dual ,这里再来补充一点相关的知识。这套理论不仅适用于 SVM 的优化问题,而是对于所有带约束的优化问题都适用的,是优化理论中的一个重要部分。简单来说,对于任意一个带约束的优化都可以写成这样的形式:

\[
\begin{aligned}
\min&f_0(x) \\
s.t. &f_i(x)\leq 0, \quad i=1,\ldots,m\\
&h_i(x)=0, \quad i=1,\ldots,p
\end{aligned}
\]

形式统一能够简化推导过程中不必要的复杂性。其他的形式都可以归约到这样的标准形式,例如一个 $\max f(x)$ 可以转化为 $\min -f(x)$ 等。假如 $f_0,f_1,\ldots,f_m$ 全都是凸函数,并且 $h_1,\ldots,h_p$ 全都是仿射函数(就是形如 $Ax+b$ 的形式),那么这个问题就叫做凸优化(Convex Optimization)问题。凸优化问题有许多优良的性质,例如它的极值是唯一的。不过,这里我们并没有假定需要处理的优化问题是一个凸优化问题。