0
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you for your reply ! Do you mean $min_{(w,b) \in C} ||w||^2=min_{(w,b) \in B \cap C} ||w||^2$ ? If it's the case, I can't see why $min_{(w,b) \in C} ||w||^2 \geq min_{(w,b) \in B \cap C} ||w||^2$ $\endgroup$
    – array.02
    Commented Apr 2, 2022 at 11:00
  • $\begingroup$ Ops, you are right, that is a typo. The reason they are equal is because the point $x$ we choose was any random point that satisfies the constraint $C$. If there is a better point than $x$ it must have a value less than $||x||^{2}$., the set $B$ is the set of all such points. So the set $B\cap C$ is just the set of points that satisfy the constraints and give a lower value of $||w||^{2}$ than the random point we selected $x$. Also, it isn't possible for a more restricted set ($B\cap C$) to give a lower value than the original set ($C$). $\endgroup$
    – dgadjov
    Commented Apr 2, 2022 at 17:01
  • $\begingroup$ Thank you for your detailed answer !! $\endgroup$
    – array.02
    Commented Apr 2, 2022 at 18:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .