Linear Maximum-Margin Classifier (Hard SVM):

Primal: $\min_{w,b} \frac12||w||^2$ s.t. $y_i(w^T x_i + b) \ge 1$, $y_i\in\{-1,1\}$

Margin $=2/||w||$, support vectors satisfy equality. Only linear separable case, no slack.

Modifications for Non-linear and Non-separable:

1. Allow misclassification (Soft Margin): Introduce slack $\xi_i \ge 0$:
   $y_i(w^T x_i+b) \ge 1-\xi_i$. $\xi_i>0$ violates margin, $\xi_i>1$ misclassifies. Add penalty $C\sum\xi_i$.

2. Make Non-linear via Feature Map $\phi(x)$ and Kernel: Map $x\to\phi(x)$ to higher dimension where linear separation possible. Replace $w^T x$ with $w^T\phi(x)$. Kernel trick: $K(x_i,x_j)=\phi(x_i)^T\phi(x_j)$ avoids explicit high-dim computation (Polynomial, RBF).

Derivation — Primal for Soft-Margin Non-linear SVM:

Minimize over $w,b,\xi$:
$$\min_{w,b,\xi} \frac12||w||^2 + C\sum_{i=1}^n \xi_i$$
s.t. $y_i(w^T\phi(x_i)+b) \ge 1-\xi_i$, $\xi_i \ge 0$, $i=1..n$

• First term maximizes margin ($1/||w||$).
• Second penalizes violations; $C$ trades margin width vs training error (small $C$ wider margin more violations, large $C$ hard margin approx).
• $\xi_i = \max(0, 1-y_i(w^T\phi(x_i)+b))$ = hinge loss.

If separable, optimum $\xi_i=0$ recovers hard margin. Non-linear version retains same form with $\phi$. Dual leads to $w=\sum\alpha_i y_i\phi(x_i)$ and kernelized decision $f(x)=\sum\alpha_i y_i K(x_i,x)+\!b$.

Without slack & kernel, linear separable only; with them, general-purpose classifier.