凸优化--对偶问题 for SVM

### 关于支持向量机中的凸二次规划问题 在支持向量机（SVM）中，优化目标函数可以被表述为一个凸二次规划（Convex Quadratic Programming, CQP）问题。该问题的目标是在高维空间中找到最优超平面，使得不同类别的数据点能够被尽可能清晰地区分开来。 #### 凸二次规划问题的形式化描述 对于线性可分的支持向量机而言，原始最优化问题是寻找满足特定约束条件下的最小权重平方和： \[ \min_{w,b} \frac{1}{2}\| w \| ^2 \] 其中 \(w\) 是权值向量而 \(b\) 则表示偏置项。为了处理非严格线性可分的情况以及引入核技巧扩展到更高维度的空间内工作，通常会转换成拉格朗日对偶形式求解[^1]。 此时原问题转化为其对应的对偶问题——即最大化如下表达式的值: \[ L_D=\sum_i^n{\alpha_i}-\frac{1}{2}\sum_i^n\sum_j^n y^{(i)}y^{(j)}K(x^{(i)},x^{(j)})\alpha_i\alpha_j \] 这里 \(α_i≥0\) 表示拉格朗日乘子；\(y^{(i)}∈{-1,+1}\) 代表类别标签；\(K(\cdot,\cdot)\) 定义了两个输入实例之间的相似度测量方式（也称为核函数），它允许模型通过映射至特征空间实现更复杂的决策边界构建。 #### 解决方法：序列最小优化(SMO) 由于直接应用通用的二次规划算法效率低下，因此提出了专门针对此类问题设计的方法—序列最小优化 (Sequential Minimal Optimization, SMO)。此技术的核心思想在于每次只更新一对参数而不是整个变量集，在每一步迭代过程中选择合适的样本来简化计算过程并加速收敛速度。 具体来说，SMO 将大规模 QP 问题分解成了多个小型子问题来进行逐个击破。这些子问题具有解析解可以直接得出而不必依赖数值逼近手段，从而大大提高了整体运算性能。 ```python def smo_algorithm(X, Y, C, tol, max_passes, kernel_func): m, n = X.shape alphas = np.zeros(m) b = 0 passes = 0 while passes < max_passes: num_changed_alphas = 0 for i in range(m): Ei = calc_E(w=calc_w(alphas, X, Y), dataMatrix=X, classLabels=Y, i=i) - Y[i] if ((Y[i]*Ei < -tol and alphas[i] < C) or (Y[i]*Ei > tol and alphas[i] > 0)): j = select_Jrand(i, m) Ej = calc_E(w=calc_w(alphas, X, Y), dataMatrix=X, classLabels=Y, i=j) alpha_Iold = alphas[i].copy() alpha_Jold = alphas[j].copy() L, H = clip_alpha(alphas[i], alphas[j], Y[i], Y[j]) if L==H: continue eta = 2.0 * X[i,:]*X[j,:].T - X[i,:]*X[i,:].T - X[j,:]*X[j,:].T if eta >= 0: continue alphas[j] -= float(Y[j]*(Ei - Ej))/eta alphas[j] = adjust_alpha(alphas[j], L, H) if abs(alphas[j]-alpha_Jold)<0.00001: continue alphas[i] += Y[j]*Y[i]*(alpha_Jold-alphas[j]) b = update_b(b, Ei, Ej, alphas[i], alphas[j], alpha_Iold, alpha_Jold, Y[i], Y[j], X[i,:], X[j,:]) num_changed_alphas += 1 if num_changed_alphas == 0: passes += 1 else: passes = 0 return alphas, b ```