对于一个二类可分问题，感知机算法可以对这些样本点进行二分类，其解有无穷多个，我们不能找到一个最优的超平面对这些样本点分类。对于所有可行解来说，超平面距离样本点越远，该超平面对当前样本点分类效果应当越好，这也就引出了支持向量机算法，即间隔最大化。支持向量机算法的原始问题可以描述为二次规划问题，对于线性规划以及二次规划问题，还可以使用对偶问题来描述，并且在一定的条件下，原始问题与对偶问题的解是相等的，这为我们解决支持向量机算法提供了新的思路，并且在该算法的物理解释与拓展上有了新的理解，具体的物理解释与拓展到软间隔和非线性分类见下文。
1. 原始问题
假设数据集为\(D=\{(x_1,y_1),(x_2,y_2),...(x_N,y_N)\},\ x_i\in \Bbb R^n,\ y_i\in\{+1,-1\}\)。若这些样本点二类可分，最大间隔问题可以表示为
\[\begin{aligned} &\arg \max_{w,b}\ \arg\min_{x_i\in D}\ &\left|\frac{w}{\Vert w\Vert}\cdot x_i+\frac{b}{\Vert w\Vert}\right|\\ &s.t.\ &y_i(w\cdot x_i+b)\ge0\ \forall x_i\in D \end{aligned}\]对于此问题，超平面的法向量的方向是有意义的，但是其长度是没有意义的，例如在此问题中若\(w,b\)是此问题的解，则\(2w,2b\)也是其解。首先我们想到的是可以把法向量限定在单位向量中，即目标函数中\(\Vert w\Vert\)可以去掉，但是目标函数不是一个凸函数，不能很好地优化，此时可以换一个思路，因为\(w\)的大小是可以变的，因此\(\vert w\cdot x_i+b\vert\)的大小也是可以任意取值的，为了便于计算不妨取其最小值为1，即
\[\begin{aligned} &\vert w\cdot x_i+b\vert\ge1\\ \Rightarrow &\frac{\vert w\cdot x_i+b\vert}{\Vert w\Vert}\ge \frac{1}{\Vert w \Vert} \end{aligned}\]因此该问题可以转化为如下
\[\begin{aligned} &\arg \max_{w,b}\ &\frac{1}{\Vert w \Vert}\\ &s.t.\ &y_i(w\cdot x_i+b)\ge1\ \forall x_i\in D \end{aligned}\]最大化\(\frac{1}{\Vert w\Vert}\)问题等价于最小化\(\frac{1}{2}\Vert w\Vert^2\)，目标函数转化为了二次凸优化函数，整个问题也转换为了二次规划问题，即
\[\begin{aligned} &\arg \min_{w,b}\ &\frac{1}{2}\Vert w\Vert^2\\ &s.t.\ &y_i(w\cdot x_i+b)\ge1\ \forall x_i\in D \end{aligned}\]2. 对偶问题
对于对偶问题，首先需要得到原始问题的拉格朗日函数，对于上述问题，可以得到其拉格朗日函数为\(L(\alpha,w,b)=\frac{1}{2}\Vert w\Vert^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i\)，其中\(\alpha_i\ge0\)，对\(\alpha\)来说，若满足\(y_i(w\cdot x_i+b)\ge1\)条件，\(L(\alpha,w,b)\)的最大值为\(\frac{1}{2}\Vert w\Vert ^2\)，否则，其最大值为\(+\infty\)，因此首先要对\(L(\alpha,w,b)\)求对于\(\alpha\)的极大，再对\(w,b\)求极小来隐性满足约束条件求解原始问题，因为若不满足约束条件，其值为\(+\infty\)，显然不是可行解。整个问题可以表示为\(\arg \min_{w,b}\ \arg \max_\alpha\ L(\alpha,w,b)\)。其对偶问题可以表示为\(\arg \max_\alpha\ \arg \min_{w,b}\ L(\alpha,w,b)\)，首先求解\(\arg \min_{w,b} L(\alpha,w,b)\)，分别对这两个变量求偏导等于0可得
\[\begin{aligned} \nabla_wL(\alpha,w,b)&=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\ \nabla_bL(\alpha,w,b)&=-\sum_{i=1}^N\alpha_iy_i=0 \end{aligned}\]将上述结果带入\(L(\alpha,w,b)\)，可得
\[\begin{aligned} &\arg\max_\alpha\ &-\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.\ &\sum_{i=1}^N\alpha_iy_i=0\\ &&\alpha_i\ge0 \end{aligned}\]至此就将原始问题转化为了二次规划问题，可以使用固定的求解最优解的方式来进行求解。
3.软间隔分类
在实际应用中，上述讨论的二类线性可分情况是一个非常严格的条件，实际情况中很难满足这样的条件，如何在存在误差点的情况下对数据进行分类成为了需要解决的问题。
对于线性不可分的情况，可以引入松弛变量\(\xi\)来使约束条件满足\(y_i(w\cdot x_i+b)+\xi_i\ge1\)，即人为的将处于超平面间隔内的点移动到超平面的边缘外，另一方面通过最小化所有的\(\xi\)相加来使得人为的移动越少，同时应满足\(\xi\ge0\)，使得正确分类的点不会发生移动，即正确分类的点的\(\xi=0\)，最后再引入超参数\(C\)来平衡正确分类与人为移动之间的关系，在这种情况下的原始问题可以表示为
\[\begin{aligned} &\arg\min_{w,b,\xi} \ &\frac{1}{2}\Vert w\Vert ^2+C\sum_{i=1}^N\xi_i&\\ &s.t.\ &y_i(w\cdot x_i+b)+\xi_i\ge1&,\ i=1,2,...,N\\ &&\xi_i\ge0&,\ i=1,2,...,N \end{aligned}\]相似地，表示出其对应的拉格朗日函数\(L(\alpha,\beta,w,b,\xi)=\frac{1}{2}\Vert w\Vert ^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^N\alpha_i(y_i(w\cdot x_i+b)+\xi_i-1)-\sum_{i=1}^N\beta_i\xi_i\)，其中\(\alpha_i\ge0,\beta_i\ge0\)，其对偶问题应该先对\(w,b,\xi\)求极小，再对\(\alpha,\beta\)求极大，即
\[\begin{aligned} &\nabla_wL(\alpha,\beta,w,b,\xi)=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\ &\nabla_bL(\alpha,\beta,w,b,\xi)=\sum_{i=1}^N\alpha_iy_i=0\\ &\nabla_{\xi_i}L(\alpha,\beta,w,b,\xi)=C-\alpha_i-\beta_i=0 \end{aligned}\]将上述结果带入\(L(\alpha,\beta,w,b,\xi)\)可得
\[\begin{aligned} &\arg\max_{\alpha,\beta}\ &-\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.\ &\sum_{i=1}^N\alpha_iy_i=0&\\ &&C-\alpha_i-\beta_i=0&,\ i=1,2,...,N\\ &&\alpha_i\ge0&,\ i=1,2,...,N\\ &&\beta_i\ge0&,\ i=1,2,...,N \end{aligned}\]上式还可以进一步的化简，其中\(\alpha_i=C-\beta_i\)，且\(\beta_i\ge0\)，因此\(\alpha_i\le C\)，从而可以将上式化简为
\[\begin{aligned} &\arg\max_{\alpha,\beta}\ &-\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.\ &\sum_{i=1}^N\alpha_iy_i=0&\\ &&0\le\alpha_i\le C&,\ i=1,2,...,N\\ \end{aligned}\]从对偶问题的描述中可以看出软间隔与硬间隔的目标函数的形式是一样的，不一样的只有对\(\alpha_i\)上界的一个约束。假设已经得到上述对偶问题的最优解，由KKT条件可知其满足如下条件
\[\begin{aligned} &互补松弛条件\ &\alpha_i(y_i(w\cdot x_i+b)+\xi_i-1)=0\\ &&\beta_i\xi_i=0\\ &对偶条件\ &\alpha_i+\beta_i=C\\ &原始条件\ &\alpha_i\ge0\\ &&\beta_i\ge0\\ \end{aligned}\]因此当样本点位于超平面边界外时，\(\xi_i=0,y_i(w\cdot x_i+b)>1\)，则有\(\alpha_i=0\)，当样本点为与边界上时，\(\xi_i=0,y_i(w\cdot x_i+b)=1\)，则\(0<\alpha_i<C\)，当样本点为与边界内时，\(\beta_i=0\)，则\(\alpha_i=C\)。这里的\(\alpha_i\)可以表示第\(i\)个样本点对分割超平面贡献的权重，权重不为0的样本点也被称为支持向量，这也就是此算法被称为支持向量机的原因，理解这个需要从算法的对偶问题出发。、
线性支持向量机的另一种解释可以通过引入hinge loss来进行解释，即最小化\(\sum_{i=1}^N[1-y_i(w\cdot x_i+b)]_++\lambda\Vert w\Vert ^2\)，其中hinge loss函数为
\[[x]_+=\begin {cases} x,\ x\ge0\\ 0,\ x<0 \end{cases}\]可以理解在误分类点损失基础上加入了正则项，同时误分类损失并不是0-1损失，通过样本点距离超平面的距离表示其损失，同时利用常数1来增加样本点距离超平面边界的距离，增加样本点分类的确信度。
4. 非线性分类问题
从上述对偶问题的描述中可以看出，式子中有一个內积项\((x_i\cdot x_j)\)，并且通过前面的推导可得\(w=\sum_{i=1}^N\alpha_iy_ix_i\)，超平面的表达式为\(\sum_{i=1}^N\alpha_iy_i(x_i\cdot x)+b\)，因此可以看出在问题的求解与应用中都不需要确切的指导\(x_i,x_j\)的具体值，只需要知道二者的內积值就可以了，这也就是核函数的概念，即将样本点进行升维，样本在升维后的空间的坐标不需要求出，只需要知道任意两个点在升维空间中的內积就可以达到将样本升维后分类的目的。
