1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ There is a typo in your question, the 2nd statement of your optimisation program should be a maximization problem. $\endgroup$ – Daneel Olivaw Mar 25 '17 at 15:40
1
$\begingroup$

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.

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

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 $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The constraint $||w||=1$ is also not convex. See my (partial) answer. $\endgroup$ – Luca Citi Mar 25 '17 at 15:59
  • $\begingroup$ Yes I have seen, I will reformulate my answer to avoid ambiguity. $\endgroup$ – Daneel Olivaw Mar 25 '17 at 16:01

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.