normalization constraint in support vector machine

Question

A support vector machine initially poses the following optimization problem:

$$max_{\gamma, w, b} \gamma \\ s.t\ \\ y^{(i)}(w^Tx^{(i)} + b) \ge \gamma,\ \ i=1,\dots,m \\ ||w|| = 1$$

I understand the constraints and what we are trying to maximize. What I don't understand is why $||w||=1$ constraint is a non-convex one. $||w||=1$ means that we are trying to solve parameters that lie on the surface of unit circle/sphere/etc.

1. I'm not familiar with convexity and convex optimization but I thought spheres were convex. Is nonconvexity referring to the constraint itself - that there is no one solution to $||w||=1$ on a unit circle/sphere because every point on a unit circle/sphere is an optimal solution?

2. Later in the SVM derivation, it transforms the optimization above into
   $$max_{\gamma, w, b} {\hat{\gamma} \over ||w||} \\ s.t. \ \ y^{(i)}(w^Tx^{(i)} + b) \ge \hat{\gamma},\ \ i=1,\dots,m$$ and then to $$min_{\gamma, w, b} {1 \over 2} ||w||^2 \\ s.t. \ \ y^{(i)}(w^Tx^{(i)} + b) \ge 1,\ \ i=1,\dots,m$$ because maximizing ${\hat{\gamma} \over ||w||}$ = 1/||w|| is the same thing as minimizing $||w||^2$. How are they the same thing?

Answer 1

For 1.

Spheres ($||w||_2^2 \leq r^2$) are convex sets, spherical surfaces ($||w||_2^2 = r^2$) are not. Take the definition of a convex set (ch2 of Boyd's book), then take $w_1=[1,0,\dots,0]$ and $w_2=[-1,0,\dots,0]$, they both belong to the surface of the unit sphere of radius 1 but the midpoint of the segment between them, $w=0.5w_1 + (1-0.5)w_2 = [0,\dots,0]$, does not belong to the set.

For 2. See Daneel Olivaw's answer.

Answer 2

For (1), the concern is that the program $\max_{w,b}\frac{1}{\|w\|}$ is not convex: a convex program is one in which you minimize a convex function over a convex set. See @Luca Citi 's answer for more details.

For (2), $\frac{1}{\|w\|}$ is simply the inverse of $\|w\|$, hence if you minimize the former you are actually maximizing the latter:

$$ \begin{align} \forall w, \frac{1}{\|w^*\|} &\leq \frac{1}{\|w\|} \\[12pt] \Leftrightarrow \|w^*\| &\geq \|w\| \end{align} $$

Moreover:

$$ \begin{align} \forall w, \|w^*\| &\geq \|w\| \\[12pt] \Leftrightarrow \|w^*\|^2 &\geq \|w\|^2 \\[8pt] \Leftrightarrow \frac{1}{2}\|w^*\|^2 &\geq \frac{1}{2}\|w\|^2 \end{align} $$

Hence, for all $w$:

$$ \frac{1}{\|w^*\|} \leq \frac{1}{\|w\|} \Leftrightarrow \frac{1}{2}\|w^*\|^2 \geq \frac{1}{2}\|w\|^2 $$