Related: Why is this function, related to SVM derivation, non-convex?
I am studying notes which cover the derivation of SVM. The intuition is the geometric margin should be maximized in order to result in more confident predictions. The notes pose the following optimization problem:
\begin{equation*}
\begin{aligned}
& \max_{\gamma,w,b}
& & \gamma \\
& \text{s.t.}
& & y^{(i)}(w^Tx^{(i)} + b) \geq \gamma; i = 1, \ldots, m.\\
&&& \|w\| = 1.
\end{aligned}
\end{equation*}
$\gamma = y((\frac{w}{\|w\|})^Tx + \frac{b}{\|w\|})$
If $\|w\| = 1$ then the geometric margin equals the functional margin. However, it is stated that the constraint $\|w\| = 1$ is non-convex. I cannot intuitively see why this constraint is non-convex.
I tried graphing the function $\|w\| – 1 = 0, w \in \mathbb{R^1}$ and plugging in values to the definition of a convex function. I have not found any combination that would show this function to be non-convex.
Clearly I am lacking a fundamental understanding of this problem. Why is $\|w\| = 1$ a non-convex constraint?
Best Answer
What makes a constraint convex is not the convexity (or otherwise) of the functions involved, but rather the convexity of the set of points that satisfy the constraint.
The set of points satisfying $\|w\|=1$ is the surface of a norm ball. For the Euclidean norm $\|w\|=\langle w, w\rangle^{1/2}$, it is the surface of an $n$-sphere. These points do not form a convex set. To see this, consider the line segment between any point in the set $w$ and its negative $-w$, also on the surface of the ball. The midpoint of this segment is the origin, which of course is not in the set. This contradicts a claim of convexity, which requires that the entire segment lie within the set. (In fact, when $n=1$, the set consists of just two points!)
The set $\|w\|\leq 1$, on the other hand, is the entire norm ball, including the interior. This is a convex set; so it is a convex constraint.
In practice, equality constraints involving nonlinear functions are almost never convex. The exceptions tend to be trivial to reduce to an equivalent set of linear equations.