2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ should formula be $(w^T x_i + b) _+$ which is hinge loss? $\endgroup$ – Haitao Du Aug 16 '16 at 14:44
  • $\begingroup$ 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. $\endgroup$ – dkoehn Aug 16 '16 at 14:57
3
$\begingroup$

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).

For an intuitive approach to illustrate (not a formal proof):

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.