Separating hyperplanes of a convex cone

151 Views Asked by At

Let $W$ be a fixed matrix. Define

$posW \triangleq \{t |Wy =t , y≥ 0\}$,

It is called the positive hull of $W$. It represents the set of right-hand sides that can be obtained by a non-negative combination of the columns of $W$ . The positive hull is easily seen to be a convex cone.

Let $p$ be a point not in the set $posW$. Then, there exist a hyperplane
$H \triangleq \{x |\sigma^Tx =0\}$ that separates $p$ and $posW$.

How can we prove that the number of possible separating hyperplanes (separating $p$ and $posW$) is finite based on the fact that $posW$ is finitely generated?

2

There are 2 best solutions below

3
On

The result is wrong in general. I.e. for $W=0$, $\text{pos }W= \{0\}$. And if $p \neq 0$, there is an infinite number of hyperplanes separating $p$ and $\text{pos } W$.

7
On

Take $W=I$, then the positive hull is $Q=\{x | x \ge 0 \}$. Take $p= (-1,...,-1)$ and note that the hyperplanes generated by $H_q = \{ x | q^Tx = 0 \}$, for any non zero $q \in Q$ (which is also the dual cone of $Q$) all separate $p$ from $Q$. There are infinitely many of these.