1
$\begingroup$

I was referring SVM section of Andrew Ng's course notes for Stanford CS229 Machine Learning course. On page 16, he says:

SVM optimization problem can be given as follows: $$\begin{align} \max_{\gamma,w,b}\gamma \\ s.t. & \quad y^{(i)}(w^Tx+b) \geq\gamma, \quad i=1,...,n \\ & \quad \Vert w \Vert =1. \\ \end{align} $$ But the "$\Vert w \Vert$" constraint is a nasty (non-convex) one, ...

I am unable to understand why the constraint $\Vert w \Vert$ is non-convex.

PS: I understand the basic definition of convex "function" and I have not delved any deep in optimization theory.

$\endgroup$

1 Answer 1

2
$\begingroup$

First, you can notice that the points which are satisfying the constraint are the surface of a norm-ball. Hence they don't form a convex set.

Also, consider ∥x∥=1 and ∥-x∥=1. You can easily observe that (1/2)(x+(−x)) has 0 norm. So, it is not closed under convex combination.

$\endgroup$
1
  • $\begingroup$ am really not able to get it. I tried understanding what "$p$-norm ball" from here: 1, 2. But what do you mean by "norm ball" (without $p$)? Can you explain "every sentence" a bit in more detail? I guess I lack the background concepts to understand. For example, I didn't get why "points satisfying the constraint are the surface of a norm-ball". $\endgroup$
    – Rnj
    Sep 23, 2021 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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