# How to show non-convexity of the geometrical motivated SVM Optimization Problem

Geometrically the SVM tries to classify each data point rightly, while maximize the margin $\gamma$. In the linear seperable case this can be formulated as \begin{align} \max_{\gamma,b \in \mathbb{R}, w \in \mathbb{R}^d} \gamma \ \ \textit{s.t.} \ \ \gamma - y_i \dfrac{w^T x_i + b}{||w||} &\leq 0 \ \ \forall i = 1,\dots,n \label{eq:hardsvm} \end{align} Is there a simple and mathematical exact way to show that the unequality constraint of this problem is not convex?

• should formula be $(w^T x_i + b) _+$ which is hinge loss? – Haitao Du Aug 16 '16 at 14:44
• I reformulated the problem, because it there was a mistake in the previous one. This is the binary classification case where $y \in [-1,1]$, which means that $y_i(w^Tx_i + b)$ should be the same as your suggestion. – dkoehn Aug 16 '16 at 14:57

Formally, if we multiply the constraint through by $||w||$ we have $\gamma ||w|| - y_i(w^Tx + b) \leq 0$. The second term is linear. The first term $\gamma||w||$ is obviously not convex (to see this, note that the second derivative in terms of $\gamma$ is 0, but $\frac{d^2}{d\gamma dw} \gamma||w|| = \frac{w}{||w||}$ which obviously isn't 0) - from there, the Hessian isn't positive semi-definite).
Note that since $b$ doesn't appear in the objective we can rescale it freely, e.g. define $b' = \frac{b}{||w||}$. Similarly for $w$, we define $w' = \frac{w}{||w||}$, and note that $||w'|| = 1$ (note that while $w'$ is not well defined at $w=0$, $\lim_{w \rightarrow 0} ||\frac{w}{||w||}|| = 1$). Then our problem becomes:
$$\max_{\gamma, b' \in \mathcal{R}, w' \in \mathcal{R}^d} \gamma\\ s.t. \gamma - (y_i {w'}^Tx + b') \leq 0\\ ||w'|| = 1$$
Note that $||w'||=1$ defines the shell of a sphere, which is non-convex. I think that this is a fairly intuitive way to illustrate it.