# How to show that SVM is convex problem?

It's well-known fact that support-vector machines (SVM) is convex problem

$$\min_w \frac{1}{2} \left \| w \right \|^2 \quad \text{subject to} \quad (w x_i +b) y_i \geq 1$$

I don't understand how given the LP formulation of SVM I can conclude that it's indeed a convex problem.

• Maybe by showing the Lagrangian is convex ? Commented Jan 31, 2015 at 9:17
• This is not an LP (="linear programming"). Commented Jan 31, 2015 at 13:19

The proof is rather elementary: let $x_1, x_2 \in \mathbb{R}^n$ and let $t \in [0,1]$. We want to show that for any norm $f:\mathbb{R}^n \to \mathbb{R}$, $f$ is convex meaning that $f(tx_1+(1−t)x_2) \leq tf(x_1)+(1−t)f(x_2)$.
Since $f$ is a norm, by triangle inequality $f(tx_1+(1−t)x_2) ≤ f(tx_1)+f((1−t)x_2)$. By positive homogeneity of $f$, the right-hand side of the previous inequality is $f(tx_1)+f((1−t)x_2) = tf(x_1)+(1−t)f(x_2)$, so $f$ is convex.
The SVM problem is not an LP if the norm (used in the objective function) is the Euclidean norm, which SVM problem usually assumes. When using the Euclidian norm, the SVM objective function (besided being convex) is quadratic because the Euclidian norm is equivalent to an inner product of $w$ with itself.
Finally, the usual definition o a convex problem is optimize a convex function over a convex set. Showing that the latter happens is much easier because in the SVM problem only the vector $w$ and the scalar $b$ are the unknowns; the vectors $x_i$ and the scalars $y_i \in \{-1, 1\}$ are the given input data for the SVM problem. So the SVM constraints are actually linear in the unknowns. Now any linear constraint defines a convex set and a set of simultaneous linear constraints defines the intersection of convex sets, so it is also a convex set.