0
$\begingroup$

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?

Improve this question
$\endgroup$
1
$\begingroup$

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$).

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ @mtanneauThis was adapted from part 1 of Proposition 1 at page 6 of personal.psu.edu/vvs3/IE597/ie597_lect4.pdf $\endgroup$ – DSPinfinity Feb 26 at 14:47
  • $\begingroup$ 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$. $\endgroup$ – k88074 Feb 26 at 19:27
  • $\begingroup$ @k88074 how can we prove under "finitely many distinct hyperplanes" specification? $\endgroup$ – DSPinfinity Feb 26 at 19:43
  • $\begingroup$ 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. $\endgroup$ – mtanneau Feb 27 at 15:12
  • $\begingroup$ @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 $\endgroup$ – DSPinfinity Mar 2 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.