SVM对偶问题

1、对偶问题数学基础

对偶问题：在线性规划中，每一个线性规划问题(称为原问题)都有一个与之对应的对偶问题。从数学形式上看，如果原问题是求解一个线性目标函数的最大值（或最小值），在满足一系列线性不等式（或等式）约束的条件下，那么对偶问题就是通过原问题的约束条件系数和目标函数系数等信息构建的另一个线性规划问题。这两个问题之间存在着紧密的数学关系。

PS2-1：为防止一些同学没有学过凸优化理论讲解一下什么是凸优化问题。

对于一般地约束优化问题

若目标函数f(x)是凸函数，约束集合是凸集（s.t.后面的两个为约束条件，假设有n个等式约束和m个不等式约束），则称上述优化问题为凸优化问题，特别地， $g_i(x)$ 是凸函数， $h_i(x)$ 是线性函数时，约束集合为凸集，该优化问题为凸优化问题。显然，支持向量机的目标函数是 $\frac{1}{2}\left \| w \right \|^2$ 关于 w 的凸函数，不等式约束 $1-y_i(w^Tx_i+b)$ 也是关于 w 的凸函数，因此支持向量机是一个凸优化问题。

emm补充一些内容，关于凸函数的：

        ①若是f(x)为凸函数，那么-f(x)则是凹函数。这说明了线性函数既是凸函数也是凹函数。

        ②对于二次函数，若是Q矩阵是半正定矩阵，那么其二阶导(海森矩阵)也为半正定矩阵，根据凸性判定的二阶条件，它也是凸的。

        ③最小二乘函数总是可以写成 $AA^T$ ，因此也是凸的

凸集：集合C内的任意取两点，形成的线段均在集合C内，则称集合C为凸集。

扩展到k个点的时候：

凸集的示例：

在支持向量机求解最优分离超平面的问题中，使用拉格朗日对偶性将原始问题转换为对偶问题，通过解对偶问题得到原始问题的解。这里的拉格朗日对偶法对于一般地约束优化问题，并不一定要是凸优化问题。

设上述优化问题的定义域为上面三个函数的交集

可行集首先要满足定义域，同时还得让x满足约束条件，即

显然 𝐷 是 𝐷 的子集，最优值为 $P^*=min{f(\widetilde{x})},\widetilde{x} \in\widetilde{D}$ 。由拉格朗日函数的定义可知上述优化问题的拉格朗日函数为：

其中μ={μ1；μ2；…；μm}，λ={λ1；λ2；…；λn}为拉格朗日乘子向量。

定义上述优化问题的拉格朗日对偶函数𝛤(𝜇，𝜆) ，该对偶函数只是关于拉格朗日乘子的函数，其自变量与 x 无关。𝛤(𝜇，𝜆)为拉格朗日函数𝐿(𝑤,𝑏,𝛼)关于 𝑥 的下确界。即

PS2-2：这里扩充一下下确界和上确界的概念

下确界：inf（infimum或infima）。inf(S)， S 表示一个集合，inf(S)是指集合 S 的下确界，即小于或等于 S 中所有元素的最大值，这个数不一定在集合S中。

上确界：sup（supermum）。sup(S) 是指集合 S 的上确界，即大于或等于 S 的所有元素的最小值，这个数不一定在集合 S 中。

举几个例子：

①𝑖𝑛𝑓{1,2,3,4,5}=1：集合 {1,2,3,4,5} 的下确界是 1，因为 1 是集合中最小的元素。

②𝑖𝑛𝑓{𝑥∈ℝ| 0＜ 𝑥＜10}=0：集合 {𝑥∈ℝ|0＜𝑥＜10} 的下确界是 0，因为 0 是小于集合中所有元素的最大值，但 0 不在集合中。

③ $inf\left \{ (-1)^n+\frac{1}{n+1}|n=1,2,3,... \right \}=0$ ：数列 $(-1)^n+\frac{1}{n+1}$ 的下确界是 0，因为 0 是小于或等于数列所有项的最大值。

④𝑠𝑢𝑝{1,2,3,4}=4：集合 {1,2,3,4} 的上确界是 4，因为 4 是集合中最大的元素。

⑤𝑠𝑢𝑝{𝑥∈ℝ| 0＜𝑥＜10}=10：集合 {𝑥∈ℝ| 0＜𝑥＜10} 的上确界是 10，因为 10 是大于集合中所有元素的最小值，但 10 不在集合中。

⑥𝑠𝑢𝑝{𝑥∈ℝ| 0＜𝑥≤ 10}=10：集合 {𝑥∈ℝ| 0＜𝑥＜10} 的上确界也是 10，因为 10 是集合中最大的元素。

关于上确界和下确界的一些性质：

① $sup\left \{ a+b|a\in A \quad and \quad b\in B \right \}=sup(A)+sup(B)$ ：两个集合 A 和 B 的和的上确界等于它们各自上确界的和。

② $inf\left \{ a+b|a\in A \quad and \quad b\in B \right \}=inf(A)+inf(B)$ ：两个集合 A 和 B 的和的下确界等于它们各自下确界的和。

对偶函数𝛤(𝜇，𝜆)有如下重要的性质：

①无论上述优化问题是否是凸优化问题，其对偶函数𝛤(𝜇，𝜆)恒为凹函数

②当𝜇⪰0时，𝛤(𝜇，𝜆)构成了上述优化问题最优值 $p^*$ 的下界，即𝛤(𝜇，𝜆) ≤ $p^*$

PS2-3：为什么𝛤(𝜇，𝜆)构成了上述优化问题最优值 $p^*$ 的下界？

【证明】：设 $\widetilde{x} \in\widetilde{D}$ 是优化问题的可行点，则满足等式约束条件，即 $g_i(\widetilde{x})\leq 0,h_i(\widetilde{x})=0$ ，因此当 𝜇⪰0时， $\mu _ig_i(\widetilde{x})\leq 0,\lambda _ih_i(\widetilde{x})=0$ 恒成立，所以

进一步可以推出

又因为

这个式子，左边的 𝑥 ∈ 𝐷 ， $\widetilde{x} \in\widetilde{D}$ ，而 $\widetilde{D}$ 是 𝐷 的子集。那 x 求的就是最小值。在全局𝐷上的最小值一定小于等于子集 $\widetilde{D}$ 上任何一个点所取到的值。（这句话可能有点抽象，举个例子珠穆朗玛峰是世界上最高的山峰，那其一定是在中国最高的山峰。）。所以根据上面的式子可知

进一步地

所以，𝛤(𝜇，𝜆)构成了上述优化问题最优值 $p^*$ 的下界。证毕！

定义在满足这个μ ⪰ 0约束条件下求对偶函数最大值的优化问题为拉格朗日对偶问题（简称对偶问题）

设对偶问题的最优值为 $d^*$ ，显然 $d^*\leq p^*$ ，此时称为"弱对偶性"成立，若 $d^* =p^*$ ，则称为"强对偶性"成立。如此一来就找到了求解 $p^*$ 的方法。

说一下对偶问题的性质：

①当主问题满足某些充分条件时，强对偶性成立。常见的充分条件有Slater条件："若主问题是凸优化问题，且可行集 $\widetilde{D}$ 中存在一点能使所有不等式约束的不等号成立，则强对偶性成立"。显然，支持向量机满足Slatert条件。

②无论主问题是否为凸优化问题，对偶问题恒为凸优化问题，因为对偶函数𝛤(𝜇，𝜆)恒为凹函数(加个负号即可转为凸函数)，约束条件μ⪰0恒为凸集

③设 $f(x),g_i(x),h_j(x)$ 一阶偏导连续， $x^*$ ， $(\mu ^*,\lambda ^*)$ 分别为主问题和对偶问题的最优解，若是强对偶成立，则， $x^*$ ， $\mu ^*,\lambda ^*$ 一定满足如下5个条件：

这五个条件也成为KKT条件。KKT条件是局部解的必要条件，也就是说只要该优化问题满足任何一个特定的约束限制条件，局部解就一定会满足以上5个条件。

PS2-4：这里的"∇𝑥"就是对变量x的梯度，其实就是对x求导，其中不等式的约束的乘子必须是大于等于0的，不等式的乘子×其不等式约束=0。

        公式①是"稳定性条件"：在最优解 $x^*$ 处，目标函数的梯度必须与所有约束的梯度的线性组合相等。

        公式②和公式③是"原始可行性"：最优解 $x^*$ 必须满足所有约束条件：

        公式④是"对偶可行性"：不等式约束的拉格朗日乘子必须非负

        公式⑤是"互补松弛条件"：对于每个不等式约束，要么约束是活跃的，要么对应的拉格朗日乘子为零

KKT条件的定义：KKT条件是判断某点是否为约束优化问题极值点的必要条件。对于一个非线性规划问题，如果目标函数和约束条件满足一定的正则性条件，那么在最优解处，KKT条件必须成立。一个典型的优化问题可以表示为：

其中：

现在对于支持向量机的数学知识基本讲解完毕，套用上面的知识：

2、SVM问题实例

主问题：

拉格朗日函数，引入拉格朗日乘子 $a_i\geq 0$ 得到拉格朗日函数

令𝐿(𝑤,𝑏,𝛼)对 w 和 b 的偏导为 0（这里的 w 和 b 就相当于上面 KKT 中说的 x ）可得

将其带入拉格朗日函数里，得：

PS2-5：这里的计算过程是比较简单的，对w和b求偏导的过程不用多说。数学基础有所缺失的朋友可能会对 $w^T$ 和 $\left \| w \right \|$ 的求解有些许疑问。首先根据向量和矩阵的转置性质 $(c\cdot a)^T=c\cdot a^T$ ，其中a是向量，c是标量。故：

而对于

解出 𝛼 以后，求出 w 和 b 即可得到模型：

其对应的KKT条件

若 $a_i=0$ ，则该样本将不会在最终模型的求和中出现，也就不会对 𝑓(𝑥) 有任何影响；

若 $a_i> 0$ ，则必有 $y_if(x_i)=1$ ，所对应的样本点位于最大间隔边界上。

这显示出支持向量机的一个重要性质，即解的稀疏性：训练完成后，大部分的训练样本都不需要保留，最终模型只与支持向量相关。

现在问题就集中到如何解出 𝛼 了，不难发现，这是一个二次规划问题，可以使用通用二次规划算法解决，然而对于训练样本数较大的情况下，使用通用二次规划算法的开销较大。根据问题特性，创造了很多高效的算法，这里以SMO算法作为代表进行介绍。

PS2-6：二次规划问题：是一种特殊类型的优化问题，其目标函数是二次的，而约束条件可以是线性的。二次规划问题的一般形式如下：

其中，Q 是一个对称的正定或半正定矩阵，c 是一个列向量，A 和 $A_e$ 是线性约束的系数矩阵，𝑏 和 $b_e$ 是线性约束的常数项向量， $l$ 和 𝑢 分别是变量的下界和上界向量。

        凸二次规划问题：Q半正定，问题有全局解

        严格凸二次规划问题：Q正定，问题有唯一全局解

        一般二次规划问题：Q不定，问题有稳定点或局部解

【一般而言直接代入对应的求解包就行】

详见：最优化 | 二次规划的基础知识理论https://blog.csdn.net/weixin_42301220/article/details/126267907?ops_request_misc=%257B%2522request%255Fid%2522%253A%25223360fe5648d543f2fb84281edc96aedf%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=3360fe5648d543f2fb84281edc96aedf&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-1-126267907-null-null.142%5ev101%5epc_search_result_base2&utm_term=%E4%BA%8C%E6%AC%A1%E8%A7%84%E5%88%92%E9%97%AE%E9%A2%98&spm=1018.2226.3001.4187

SMO（Sequential Minimal Optimization）节省计算开销，SMO每次选择两个样本 $\alpha _i$ 和 $\alpha _j$ ，并固定其他参数，在参数初始化后，SMO不断执行如下两个步骤直至收敛：

1.选取一对需更新的变量 $\alpha _i$ 和 $\alpha _j$ 。

2.固定 $\alpha _i$ 和 $\alpha _j$ 以外的参数，求解对偶问题获得更新后的 $\alpha _i$ 和 $\alpha _j$

仅考虑 $\alpha _i$ 和 $\alpha _j$ 时，对偶问题的约束 $\sum_{i=0}^{m}\alpha _iy_i=0$ 变为 $\alpha _iy_i+\alpha _jy_j=c,\alpha _i\geq 0,\alpha _j\geq 0,c= \sum_{k\neq i,j}^{}\alpha _ky_k$ (其实就是剩下的加起来）。

用 $\alpha _i$ 表示 $\alpha _j$ ，带入对偶问题

解出来 $\alpha _i$ 以后我就能将解出来的值代入，就可以解出 $\alpha _j$ 。如此一来就可以迭代的进行求解下去，而且这种方法可以很有效的提高效率。

直观来看，KKT条件违背的程度越大，则变量更新后可能导致目标函数数值减幅增大。SMO先选取违背KKT条件程度最大的变量，第二个变量应选择一个使目标函数值减小最快的变量（计算复杂度高），SMO采用了一个启发式：使选取的两个变量所对应的样本之间间隔最大，其一定是收敛的，因为一直找违反KKT条件最大的变量，迟早会找不到的。那就是收敛的地方。