Mathematical Formulation of SVM Problem:

Given $D=\{(x_i,y_i)\}, y_i\in\{-1,1\}$, $i=1..n$.

Primal (Soft-margin, most general):

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

Hard margin special case $C\to\infty$, $\xi_i=0$.

Dual (Wolfe Dual, kernelizable):

Using Lagrange multipliers $\alpha_i\ge0$, $\mu_i\ge0$:
$L = \frac12||w||^2 +C\sum\xi_i -\sum\alpha_i[y_i(w^T x_i+b)-1+\xi_i] -\sum\mu_i\xi_i$

KKT: $w=\sum\alpha_i y_i x_i$, $\sum\alpha_i y_i=0$, $C-\alpha_i-\mu_i=0$

Dual:
$$\max_{\alpha} \sum_i \alpha_i -\frac12\sum_{i,j}\alpha_i\alpha_j y_i y_j K(x_i,x_j)$$
s.t. $0\le\alpha_i\le C$, $\sum_i \alpha_i y_i =0$

$K(x_i,x_j)=x_i^T x_j$ (linear) or kernel $K=\phi(x_i)^T\phi(x_j)$.

Decision: $f(x)=sign(\sum_{i:\alpha_i>0}\alpha_i y_i K(x_i,x)+b)$, $b$ from support vectors where $0<\alpha_i<C$ via $y_s(\sum\alpha_i y_i K(x_i,x_s)+b)=1$.

Outline of Method for Solving:

1. Choose $C$ (and kernel hyperparameters $\gamma$ via CV).
2. Solve Quadratic Programming dual for $\alpha$ ( convex QP). Use algorithms: SMO (Sequential Minimal Optimization) — iteratively optimizes pair of $\alpha$ analytically, efficient $O(n)$; or interior point, gradient ascent.
3. Identify Support Vectors $\alpha_i>0$ (approx $10^{-5}$). SVs on margin $0<\alpha_i<C$, inside/errors $\alpha_i=C$.
4. Compute $w$ (implicitly via kernel) and $b$ averaging over margin SVs.
5. Classify new $x$ via sign of kernel expansion.

For large data, use LIBSVM / LIBLINEAR, Pegasos (primal SGD).

Properties: Convex, global optimum, sparsity (only SVs matter), max margin minimizes VC bound, good generalization.