使用cvx工具箱求解svm的原问题及其对偶问题

要使用CVX工具箱求解支持向量机（SVM）的原问题和对偶问题，需分别构建优化模型并求解

---

1. SVM原问题（硬间隔）

优化目标：
$\min_{w,b} \frac{1}{2} \|w\|^2$
约束条件：
$y_i (w^T x_i + b) \geq 1 \quad \forall i$

% 生成线性可分数据（示例）
rng(1);
X = [randn(20,2) + 2; randn(20,2) - 2];  % 两类数据
y = [ones(20,1); -ones(20,1)];           % 标签 [1, -1]

% 使用CVX求解原问题
cvx_begin
    variables w(2) b;        % 优化变量：权重w和偏置b
    minimize(0.5 * sum(w.^2)); % 目标函数
    subject to
        y .* (X * w + b) >= 1; % 线性约束
cvx_end

% 可视化结果
scatter(X(:,1), X(:,2), [], y, 'filled');
hold on;
x1 = min(X(:,1)):0.1:max(X(:,1));
x2 = (-w(1)*x1 - b) / w(2);  % 决策边界 w1*x1 + w2*x2 + b = 0
plot(x1, x2, 'k-', 'LineWidth', 2);
title('SVM Primal Solution');
legend('Class 1', 'Class -1', 'Decision Boundary');

---

2. SVM对偶问题（硬间隔）

优化目标：
$\max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j x_i^T x_j$
约束条件：
$\alpha_i \geq 0 \quad \forall i, \quad \sum_{i=1}^m \alpha_i y_i = 0$

% 计算核矩阵（线性核）
m = size(X,1);
K = X * X';        % 线性核矩阵
H = (y * y') .* K; % 对偶问题中的Hessian矩阵

% 使用CVX求解对偶问题
cvx_begin
    variable alpha(m);       % 优化变量：拉格朗日乘子
    maximize(sum(alpha) - 0.5 * quad_form(alpha, H)); % 目标函数
    subject to
        alpha >= 0;         % 不等式约束
        y' * alpha == 0;    % 等式约束
cvx_end

% 从alpha恢复原始参数w和b
w_dual = (alpha .* y)' * X; % w = Σ(α_i y_i x_i)
idx = find(alpha > 1e-4);   % 找到支持向量（α>0）
b_dual = mean(y(idx) - X(idx,:) * w_dual'); % 计算偏置b

% 可视化对偶问题结果
scatter(X(:,1), X(:,2), [], y, 'filled');
hold on;
x2_dual = (-w_dual(1)*x1 - b_dual) / w_dual(2);
plot(x1, x2_dual, 'r--', 'LineWidth', 2);
title('SVM Dual Solution');
legend('Class 1', 'Class -1', 'Decision Boundary (Dual)');

---

说明

1. 原问题与对偶问题等价性：
   在硬间隔线性可分情况下，两者解应一致（决策边界重合）。若有轻微差异，可能因数值精度或支持向量选择阈值（1e-4）导致。

2. 支持向量识别：
   对偶问题中，非零 $\alpha_i$ 对应支持向量，位于边界 $y_i(w^T x_i + b) = 1$ 上。

3. 软间隔扩展：
   若数据非线性可分，引入松弛变量 $\xi_i$ 和惩罚参数 $C$：

   • 原问题：
     $\min_{w,b,\xi} \frac{1}{2} \|w\|^2 + C \sum_i \xi_i$
     $y_i (w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0$
   • 对偶问题：
     约束改为 $0 \leq \alpha_i \leq C$，其余不变。

4. 非线性SVM：
   使用核技巧时，将对偶问题中的内积 $x_i^T x_j$ 替换为核函数 $K(x_i,x_j)$（如高斯核）。

参考 使用cvx工具箱求解svm的原问题及其对偶问题 youwenfan.com/contentcna/66111.html

---

结果

• 比较 w（原问题）和 w_dual（对偶问题），应接近。
• 决策边界应正确分离两类数据。
• 支持向量位于边界上（对偶问题中 $\alpha_i > 0$ 的点）。