Please help me solve this problem:
Let $V=R^d$ and $(x_i,y_i)_{1 \leq i \leq n} \in (V \times \{-1,1\})^n$
Let $C=\{(w,b)\in V \times R : 1-y_i(w^tx_i-b)\leq0 , \forall i \in [1,n]\}$
Show that $min_{(w,b) \in C} ||w||^2$ has a solution $(w,b)$
What I tried:
$||w||^2$ is clearly continuous, I proved that C is closed. If C is bounded, then C is compact and the solution exists (In this case, I don't know how to prove that C is bounded). If C is not bounded, I don't know how to conclude either.
First, you need to check that the set $C \neq \emptyset$ otherwise there will be no solution. If $C\neq \emptyset$ then let $x$ be any point in $C$. Now, let the set $B = \{ y \ : \ ||y||^2 \leq ||x||^2 \}$. Since $B$ is compact and $C$ is closed the set $B\cap C$ is compact. Note that $min_{(w,b) \in C} ||w||^2 = min_{(w,b) \in B\cap C} ||w||^2$. Since $||w||^2$ is continuous and $B$ is compact you know that there must exist a solution.
In general, if you are solving $\min_{x\in S} f(x)$ and the level sets $L_{q} =\{x : f(x)\leq q\}$ are compact and $S$ is closed then there will be a solution by following a similar argument as above.