《SMO算法 公式推导》拉格朗日乘子上界和下界
本文是将文章《SMO算法 公式推导》中的问题单独拿出来做一个详细的解析，便于初学者更好的理解。
在 SMO（Sequential Minimal Optimization） 算法中，优化两个拉格朗日乘子 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 时，受到了多种约束条件的限制。为了确保优化后的 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 保持在合法的范围内，算法会计算 上界（Upper Bound） 和 下界（Lower Bound），并在这个区间内调整 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 的值。
这些界限确保了两个拉格朗日乘子的值既满足优化的线性约束，又保持在 [ 0 , C ] [0, C] [0,C] 的范围内（其中 C C C 是 SVM 的惩罚参数）。下面详细解释 上界 和 下界 的含义及其推导过程。
1. SMO 中的约束条件
在 SVM 的对偶问题中，拉格朗日乘子 α i \alpha_i αi 需要满足以下约束条件：
- 线性约束： α 1 y 1 + α 2 y 2 = k \alpha_1 y_1 + \alpha_2 y_2 = k α1y1+α2y2=k（其中 k k k 是常数，由其他不变的乘子和标签决定）。
- 边界约束： 0 ≤ α 1 ≤ C 0 \leq \alpha_1 \leq C 0≤α1≤C 和 0 ≤ α 2 ≤ C 0 \leq \alpha_2 \leq C 0≤α2≤C。
这些约束确保了我们优化得到的 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 保持在合法的范围内。为了满足这些约束条件，SMO 会为 α 2 \alpha_2 α2 计算出一个 上界 和 下界，并在此范围内对 α 2 \alpha_2 α2 进行优化调整。
2. 上界和下界的推导
根据 y 1 y_1 y1 和 y 2 y_2 y2 的符号（即它们是相同的还是不同的标签），上界和下界的计算方式有所不同。下面分别解释这两种情况。
(1) 当 y 1 = y 2 y_1 = y_2 y1=y2 时
如果 y 1 y_1 y1 和 y 2 y_2 y2 的符号相同（即 y 1 = y 2 y_1 = y_2 y1=y2），我们知道约束条件为：
α 1 + α 2 = k \alpha_1 + \alpha_2 = k α1+α2=k
为了保证 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 的取值保持在 [0, C] 范围内，SMO 会计算 α 2 \alpha_2 α2 的上下界。
-
上界 H H H：由于 α 1 ≤ C \alpha_1 \leq C α1≤C，那么 α 2 \alpha_2 α2 的最大值 H H H 是：
H = min ( C , k ) H = \min(C, k) H=min(C,k)这里， k = α 1 + α 2 k = \alpha_1 + \alpha_2 k=α1+α2，所以 α 2 \alpha_2 α2 的最大值不能超过 k k k 或 C C C，二者取其较小者。
-
下界 L L L：由于 α 1 ≥ 0 \alpha_1 \geq 0 α1≥0，那么 α 2 \alpha_2 α2 的最小值 L L L 是：
L = max ( 0 , k − C ) L = \max(0, k - C) L=max(0,k−C)这里， k k k 是常数， α 2 \alpha_2 α2 的最小值不能小于 0 或 k − C k - C k−C，二者取其较大者。
(2) 当 y 1 ≠ y 2 y_1 \neq y_2 y1=y2 时
如果 y 1 y_1 y1 和 y 2 y_2 y2 的符号不同（即 y 1 = 1 y_1 = 1 y1=1， y 2 = − 1 y_2 = -1 y2=−1 或反过来），我们知道约束条件为：
α 1 − α 2 = k \alpha_1 - \alpha_2 = k α1−α2=k
在这种情况下， α 2 \alpha_2 α2 的上界和下界如下：
-
上界 H H H：由于 α 1 ≤ C \alpha_1 \leq C α1≤C，那么 α 2 \alpha_2 α2 的最大值 H H H 是：
H = min ( C , C − k ) H = \min(C, C - k) H=min(C,C−k)这里， k = α 1 − α 2 k = \alpha_1 - \alpha_2 k=α1−α2，所以 α 2 \alpha_2 α2 的最大值不能超过 C − k C - k C−k。
-
下界 L L L：由于 α 1 ≥ 0 \alpha_1 \geq 0 α1≥0，那么 α 2 \alpha_2 α2 的最小值 L L L 是：
L = max ( 0 , − k ) L = \max(0, -k) L=max(0,−k)这里， α 2 \alpha_2 α2 的最小值不能小于 0 或 − k -k −k，二者取其较大者。
3. 上界和下界的作用
上界和下界的主要作用是 限制 α 2 \alpha_2 α2 的调整范围。由于 SVM 的拉格朗日乘子 α \alpha α 必须满足一系列边界和线性约束条件，SMO 算法通过计算上下界来确保 α 2 \alpha_2 α2 的更新不会超出合法范围。
- 上界 H H H 限制了 α 2 \alpha_2 α2 不能超过最大允许值。
- 下界 L L L 限制了 α 2 \alpha_2 α2 不能低于最小允许值。
通过这样定义的上下界，SMO 保证了优化过程中的每一步都能得到合法的解，并且使得两个拉格朗日乘子 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 的更新符合所有约束条件。
4. 举例说明
假设 C = 1 C = 1 C=1，即拉格朗日乘子 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 的最大值为 1。假设我们有 y 1 = 1 y_1 = 1 y1=1， y 2 = − 1 y_2 = -1 y2=−1，且约束条件是 α 1 − α 2 = 0.5 \alpha_1 - \alpha_2 = 0.5 α1−α2=0.5。在这种情况下：
- 上界 H = min ( C , C − k ) = min ( 1 , 1 − 0.5 ) = 0.5 H = \min(C, C - k) = \min(1, 1 - 0.5) = 0.5 H=min(C,C−k)=min(1,1−0.5)=0.5
- 下界 L = max ( 0 , − k ) = max ( 0 , − 0.5 ) = 0 L = \max(0, -k) = \max(0, -0.5) = 0 L=max(0,−k)=max(0,−0.5)=0
因此， α 2 \alpha_2 α2 的合法取值范围是 [0, 0.5]，即它必须在这个范围内进行优化。
总结
在 SMO 算法中，上界（ H H H）和 下界（ L L L）定义了两个拉格朗日乘子 α 1 \alpha_1 α1 和 α 2 \alpha_2 α2 之间的取值范围，确保它们在优化过程中既满足 SVM 的线性约束条件，又保持在合法的边界 [ 0 , C ] [0, C] [0,C] 之内。