To solve the support vector machine (SVM) primal and dual problems using the CVX toolbox, we need to formulate and optimize the corresponding mathematical models.

1. Primal Problem of SVM (Hard Margin)

Objective Function:

[\min_{w,b} \frac{1}{2} |w|^2 ]Constraints:

[y_i (w^T x_i + b) \geq 1 \quad \forall i ]``` % Generate linearly separable data (example) rng(1); X = [randn(20,2) + 2; randn(20,2) - 2]; % Two classes of data y = [ones(20,1); -ones(20,1)]; % Labels [1, -1]

% Solve the primal problem using CVX cvx_begin variables w(2) b; % Optimization variables: weight vector w and bias b minimize(0.5 * sum(w.^2)); % Objective function subject to y .* (X * w + b) >= 1; % Linear constraints cvx_end

% Visualization of results 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); % Decision boundary: w1x1 + w2*x2 + b = 0 plot(x1, x2, 'k-', 'LineWidth', 2); title('SVM Primal Solution'); legend('Class 1', 'Class -1', 'Decision Boundary');

### **2. Dual Problem of SVM (Hard Margin)**

**Objective Function**:

\[\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 \]**Constraints**:

\[\alpha_i \geq 0 \quad \forall i, \quad \sum_{i=1}^m \alpha_i y_i = 0 \]```
% Compute kernel matrix (linear kernel)
m = size(X,1);
K = X * X';        % Linear kernel matrix
H = (y * y') .* K; % Hessian matrix in dual problem

% Solve the dual problem using CVX
cvx_begin
    variable alpha(m);       % Optimization variable: Lagrange multipliers
    maximize(sum(alpha) - 0.5 * quad_form(alpha, H)); % Objective function
    subject to
        alpha >= 0;         % Inequality constraint
        y' * alpha == 0;    % Equality constraint
cvx_end

% Recover primal parameters w and b from alpha
w_dual = (alpha .* y)' * X; % w = Σ(α_i y_i x_i)
idx = find(alpha > 1e-4);   % Identify support vectors (α > 0)
b_dual = mean(y(idx) - X(idx,:) * w_dual'); % Compute bias term b

% Visualize the dual solution
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)');

Notes

1. Equivalence of Primal and Dual Solutions:
   For linearly separable data with hard margins, both solutions should yield identical decision boundaries. Minor differences may arise due to numerical precision or the threshold used for identifying support vectors (1e-4).

2. Support Vector Identification:
   In the dual formulation, non-zero Lagrange multipliers αᵢ correspond to support vectors that lie on the margin defined by yᵢ(wᵀxᵢ + b) = 1.

3. Soft Margin Extension:
   When dealing with non-linearly separable data, introduce slack variables ξᵢ and a regularization parameter C:

   • Primal Form:[\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 ]
   • Dual Form:
     Constraints change to 0 ≤ αᵢ ≤ C, with other components unchanged.

4. Nonlinear SVM:
   When applying kernel methods, replace inner products xᵢᵀxⱼ with kernel functions K(xᵢ,xⱼ), such as the Gaussian kernel.

Reference: Using CVX Toolbox to Solve Primal and Dual SVM Problems

Results

• The weight vectors w (from primal) and w_dual (from dual) should be nearly equal.
• The decision boundary correctly separates the two classes.
• Support vectors are identified by non-zero values of αᵢ in the dual solution.