Separating hyperplanes for a convex cone

Let $$W$$ be a fixed matrix. Define $$\operatorname{pos}W \triangleq \{t \mid 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 $$\operatorname{pos}W$$. Then, there exists a hyperplane $$H \triangleq \{x\mid\sigma^Tx =0\}$$ that separates $$p$$ and $$\operatorname{pos}W$$.

How can we prove that the number of possible separating hyperplanes (separating $$p$$ and $$\operatorname{pos}W$$) is finite based on the fact that $$\operatorname{pos}W$$ is finitely generated?

2 Answers

Perhaps the argument is the following. Observe that $$\operatorname{pos}W$$ is a polyhedral cone (every finitely generated cone is polyhedral). That it is finitely generated can be seen from the fact that it is positively spanned by the finite number of columns of $$W$$.

Thus we can write $$\operatorname{pos}W=\{t\mid Wy=t,y\geq 0\}=\{t\mid Dt\leq 0\}$$ for some matrix $$D\in \mathbb{R}^{m\times n}$$, $$n$$ being the dimension of $$t$$. The last expression illustrates that the number of hyperplanes separating $$\operatorname{pos}W$$ is finite ($$m$$).

How can we prove that the number of possible separating hyperplanes (separating $$p$$ and $$\operatorname{pos}W$$) is finite based on the fact that $$\operatorname{pos}W$$ is finitely generated?

In general, it is not. There may be infinitely many separating hyperplanes.

Let $$\sigma_{1}$$, $$\sigma_{2}$$ define two distinct separating hyperplanes. Then it's straightforward to see that, for $$0 \leq \lambda \leq 1$$, $$\lambda \sigma_{1} + (1 - \lambda) \sigma_{2}$$ also defines a separating hyperplane.

• @mtanneauThis was adapted from part 1 of Proposition 1 at page 6 of personal.psu.edu/vvs3/IE597/ie597_lect4.pdf Feb 26, 2021 at 14:47
• Perhaps the statement holds if we specify "finitely many distinct hyperplanes". Two hyperplanes are not distinct if they are multiple of each other, i.e., they have coefficients $\sigma_1$ and $\sigma_2$, with $\sigma_1 = \mu\sigma_2$, for some $\mu>0$. Feb 26, 2021 at 19:27
• @k88074 how can we prove under "finitely many distinct hyperplanes" specification? Feb 26, 2021 at 19:43
• I think what you want is finitely many "extreme" separating hyperplanes. The set of separating hyperplanes form a convex cone; the "extreme" separating hyperplanes would be the extreme rays of that cone. This set should be finite, yes. Feb 27, 2021 at 15:12
• @mtanneau In fact what I want to prove is part 1 of Proposition 1 at page 6 of personal.psu.edu/vvs3/IE597/ie597_lect4.pdf Mar 2, 2021 at 12:15