# SVM - why quadratic programming problem?

In Support Vector Machine, why is it a quadratic programming problem instead of a linear programming problem to obtain the optimal separating hyperplane. I only find, in book references, that the author choose the quadratic, my question is why????

Because the optimal separating hyperplane between classes of data

$$D(\mathbf{x})=\mathbf{w}^T\mathbf{x} + b = c \quad \quad -1 < c < 1,$$

is found by minimizing the objective function

$$\begin{split} Q(\mathbf{w})&=\frac{1}{2} ||\mathbf{w}||^2\\ \mathrm{w.r.t } & \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1,\\ \end{split}$$

which is linear in the inequality contraint but is a quadratic objective function due to the squared term. The square of the Euclidean norm $||\mathbf{w}||$ makes the optimization problem "quadratic programming." The quadratic objective function with inequality constraints results in a function value that is unique, but the solutions are nonunique.

There's also a definition in optimization theory:

Definition: An optimization problem for which the objective function, inequality, and equality constraints are linear is said to be a linear program. However, if the objective function is quadratic while the constraints are all linear, then the optimization problem is called a quadratic program.

In order to find an optimal separating hyperplane, the norm of the weight vector $||\overline{w}||$ should be minimized, subject to constraints $y_i(\overline{w} \cdot \varphi(x_i) + b) ≥ 1 − \xi_i$, $\xi_i \geqslant 0, i=1,\dots, l$ (see here).

While it's technically possible to minimize $\mathcal{l}^1$-norm $||\overline{w}|| = \sum_i^n |w_i|$ (i.e. to solve linear programming problem) instead of $\mathcal{l}^2$ norm (quadratic problem), the $l^1$-approach has a number of disadvantages over the $l^2$:

(a) the solutions for $l^1$-norm minimization problem lack stability,

(b) the solution isn't unique,

(c) it's harder to provide computationally efficient method for $l^1$-minimization, as compared to $l^2$-minimization.

On the other hand, while the solution of $l^1$-minimization problem is more robust to outliers than of the corresponding $l^2$ problem, this doesn't play a great role specifically for SVMs, since there's a very small chance for an outlier to become a support vector.

• Another point of interest: since the L1 norm is not invariant under rotation, this SVM would have the weird property of changing when you rotated your data set; i.e. the separating slab would not rotate along with the data points. – Matthew Drury Jul 22 '17 at 22:15