# How to prove this (corollary of) hyperplane separation theorem?

$$X$$ is a nonempty convex subset of $$\mathbb{R}^n$$ whose element is $$x=\left(x_1,...,x_n\right)$$.

The theorem is as follows.

If for each $$x\in X$$, there is an $$i \in \left\{1,...,n\right\}$$ such that $$x_i>0$$, then there exists $$\left(\lambda_1,...,\lambda_n\right)$$ where $$\lambda_i \geqslant 0$$ for all $$i$$ and $$\sum_{i=1}^n \lambda_i=1$$, such that $$\lambda \cdot x \geqslant 0$$ for all $$x\in X$$ and $$\lambda \cdot x>0$$, for some $$x \in X$$.

I was wondering how to prove it. "$$\geqslant 0$$ for all $$x$$" should be easy. But I got stuck in "$$>0$$ for some $$x$$". I failed to use the proper separation theorem (Theorem 11.3 in Rockafellar (1970)).

Thank you very much!

Let $$Y$$ be the span of $$X$$, $$C=Y\cap (-\infty,0]^n$$. Since $$X$$ and $$C$$ are disjoint convex sets in $$Y$$, there exists a non-zero functional $$\eta\in Y^*$$ which separates (not strictly) $$X$$ and $$C$$: $$\eta$$ is non-positive on $$C$$ and non-negative on $$X$$. Since $$X$$ is of full dimension in $$Y$$, we have $$\eta(x)>0$$ for some $$x\in X$$.

Now note that the coordinate functionals $$x\to x_i$$, $$i=1,\ldots,n$$, and the functional $$\eta$$ on $$Y$$ satisfy the property "if $$x_i$$'s are non-negative, then $$\eta$$ is non-negative". It yields by duality that $$\eta$$ is a non-negative linear combination of $$x_i$$'s (as a functional on $$Y$$, in particular as a function on $$X$$.)

• @WlodAA $Y$ is used to find a point $x\in X$ in which $\eta(x)\ne 0$ Aug 10 at 6:17
• oh, you are correct. Let's say differently: the coordinate functionals $x\to x_i$ and the functional $\eta$ on $Y$ satisfy the property "if $x_i$'s are non-negative, then $\eta$ is non-negative". It yields by duality that $\eta$ belongs to a cone generated by $x_i$'s. Aug 10 at 14:42
• @copper.hat on $Y$ every functional may be represented as a non-negative linear combination of $x_1$ and $x_2$. Aug 12 at 4:55
• any finitely generated cone is closed (it is a finite unit of cones generated by linearly independent subsets: if $g=c_1f_1+\ldots+c_kf_k\,(*)$ with all $c_1,\ldots,c_k$ positive, but $f_i$'s are linearly dependent, then adding this dependence with appropriate coefficient to $(*)$ you get a representation of $g$ with lesser number of f's.) Aug 12 at 14:37
• @Ypbor If $\eta$ vanishes on $X$, then it vanishes on $Y$, while it is a non-zero functional. Then there is $x \in X$ such that $\eta(x)\neq 0$ and then $\eta (x)>0$ since $\eta \geq 0$ on $X$. Aug 13 at 14:30


Suppose that $$\begin{equation*} \forall x\in X\ \exists i\in[n]:=\{1,\dots,n\}\ x_i>0. \tag{1}\label{1} \end{equation*}$$ Then there is some $$\nu\in\R_+^n$$ such that $$\begin{equation*} \nu\cdot X:=\{\nu\cdot x\colon x\in X\}\subseteq\R_+\quad\text{and}\quad \nu\cdot X\ne\{0\}. \tag{2}\label{2} \end{equation*}$$

Proof: Condition \eqref{1} means that $$X\cap\R_-^n=\emptyset$$. So, by Theorem 11.3 in Rockafellar (1970), there is some $$\la^1\in\R^n\setminus\{0\}$$ such that $$\la^1\cdot X\subseteq\R_+$$ and $$\la^1\cdot\R_-^n\subseteq\R_-$$. Also, $$\la^1\cdot\R_-^n\subseteq\R_-$$ means that $$\la^1\in\R_+^n$$. Thus, $$\begin{equation*} \text{\la^1\in\R_+^n\setminus\{0\} and \la^1\cdot X\subseteq\R_+.} \tag{3}\label{3} \end{equation*}$$

So, either \eqref{2} holds with $$\la^1$$ in place of $$\nu$$ or $$\la^1\cdot X=\{0\}$$.
So, without loss of generality (wlog), $$\la^1\cdot X=\{0\}$$. That is, we have $$\begin{equation*} X\subseteq V^1:=\{x\in\R^n\colon\la^1\cdot x=0\}. \end{equation*}$$ The condition $$\la^1\in\R_+^n\setminus\{0\}$$ in \eqref{3} implies that wlog for some $$k^1\in[n]$$ and all $$i\in[n]$$ $$\begin{equation*} \la^1_i>0\text{ if }i\le k^1\quad \text{and}\quad \la^1_i=0\text{ if }i>k^1. \tag{4}\label{4} \end{equation*}$$

Now condition \eqref{1} implies $$X\cap V^1_-=\emptyset$$, where $$V^1_-:=V^1\cap\R_-^n$$. Applying now Theorem 11.3 in Rockafellar (1970) to the Euclidean space $$V^1$$, we see that there is some $$\mu^1\in V^1\setminus\{0\}$$ such that $$\begin{equation*} \mu^1\cdot X\subseteq\R_+ \end{equation*}$$ and $$\mu^1\cdot(V^1\cap\R_-^n)\subseteq\R_-$$. The latter condition means that for all $$x\in\R^n$$ we have $$\begin{equation*} (\la^1\cdot x=0\ \&\ x\in\R_-^n)\implies\mu^1\cdot x\le0 \end{equation*}$$ or, equivalently, $$\begin{equation*} (\la^1\cdot x=0\ \&\ x\in\R_+^n)\implies\mu^1\cdot x\ge0. \tag{5}\label{5} \end{equation*}$$ Substituting the $$i$$th standard basis vector $$e_i$$ for $$x$$ in \eqref{5}, and recalling \eqref{4}, we get $$\mu^1_i=\mu^1\cdot e_i\ge0$$ for $$i>k$$.

So, wlog there is some real $$t^1>0$$ such that for $$\begin{equation*} \la^2:=\la^1+t^1\mu^1 \tag{6}\label{6} \end{equation*}$$ and some integer $$k^2\in[k^1,n]$$ we have $$\begin{equation*} \la^2_i>0\text{ if }i\le k^2\quad \text{and}\quad \la^2_i=0\text{ if }i>k^2. \tag{4a}\label{4a} \end{equation*}$$ Also, by \eqref{6}, $$\la^2\cdot X\subseteq\la^1\cdot X+t^1\mu^1\cdot X\subseteq\R_+$$. So, either \eqref{2} holds with $$\la^2$$ in place of $$\nu$$ or $$\la^2\cdot X=\{0\}$$ and hence $$\mu^1\cdot X=\{0\}$$.
So, wlog, $$\la^2\cdot X=\{0\}=\mu^1\cdot X$$. So, $$\begin{equation*} X\subseteq V^2:=\{x\in V^1\colon\la^2\cdot x=0\} =\{x\in V^1\colon\mu^1\cdot x=0\}\subsetneq V^1; \end{equation*}$$ the latter strict inclusion follows because $$\mu^1\in V^1\setminus\{0\}$$.

Continuing thus, in $$n$$ similar steps wlog we will get $$X\subseteq V^n:=\{0\}$$, which contradicts \eqref{1}. $$\quad\Box$$.

• Thanks for answering. I have some questions. (1) How can you guarantee that $\mu^1 \in V^1$? (2) Why is $\left\{x \in \mathbb{R}^n: \lambda^2 \cdot x=0\right\}=\left\{x \in V^1: \mu^1 \cdot x=0\right\}$? Why doesn't $\lambda^1 \cdot x>0$ and $\mu^1 \cdot x<0$ work? (3) Why does $V^n$ eventually shrink to ${0}$? Aug 11 at 9:04
• @Ypbor : (1) Theorem 11.3 in the Rockafellar book is stated for $R^n$, but is clearly applicable to any finite-dimensional Euclidean space. I applied this theorem to the subspace $V_1$ of the Euclidean space $\mathbb R^n$, since $X\subseteq V_1$ and $V^1_-\subseteq V_1$. So, we automatically have $\mu^1\in V^1\setminus\{0\}$. (2) The definition of $V^2$ was incorrect. It is corrected now. (3) The inclusion $V^2\subsetneq V^1$ is strict. Continuing such steps, wlog we will get $V^n\subsetneq V^{n-1}\cdots\subsetneq V^1$. Since the dimension of $V_1$ is $n-1$, the dimension of $V_n$ is $0$. Aug 11 at 17:30
• @losif Pinelis, the hyperplane is in $V^1$, but $\mu^1$, which is the normal vector, is not in $V^1$. Aug 12 at 7:38
• @Ypbor : To understand this point, forget that $V^1$ is a subspace of $\mathbb R^n$ -- look at $V^1$ as a Euclidean space on its own. By Theorem 11.3 in the Rockafellar book applied to $V^1$ (instead of $R^n$), there is (say) a nonzero linear functional $l$ on $V^1$ such that $l(X)\subseteq\mathbb R_+$ and $l(V_-^1)\subseteq\mathbb R_-$. The linear functional $l$ on $V^1$ is given by the formula $l(x)=\mu_1\cdot x$ for some nonzero $\mu^1\in V^1$ and all $x\in V^1$. So, $\mu^1\cdot X\subseteq\mathbb R_+$ and $\mu^1\cdot V_-^1\subseteq\mathbb R_-$. And, of course, $\mu^1\in V^1$. Aug 12 at 13:38
• In my graph, $X=\left\{(x_1, x_2) | x_1+x_2=0, x_1 \in [\frac{1}{2},1]\right\}$, $V^1=\left\{(x_1, x_2)| x_1+x_2=0\right\}$, and $V_{-}^1$ is just the origin. Note that the dimension of $V^1$ is 1, so a hyperplane should be of dimension 0. For example, point $A$ is a hyperplane (with respect to $V^1$) that separates $X$ and $V_{-}^1$. Of course, $A \in V^1$, but what is the $\mu^1$ corresponding to $A$? (Note $\mu^1 \in \mathbb{R}^2$) Aug 13 at 2:23

I thought that I had an answer for both part, but for the moment, I succeed only on the first part, which is an application of the first separation theorem given in https://en.wikipedia.org/wiki/Hyperplane_separation_theorem

By assumption, $$X$$ and $$\mathbb{R}_-^n$$ are two disjoint non-empty convex subsets of $$\mathbb{R}^n$$. There exist some non-null vector $$c$$ such that $$X \subset \{x \in \mathbb{R}^n : c \cdot x \ge 0\}$$ and $$\mathbb{R}_-^n \subset \{x \in \mathbb{R}^n : c \cdot x \le 0\}$$.

The last condition applied to opposite of the vectors of the canonical basis of $$\mathbb{R}^n$$ (containd in $$\mathbb{R}_-^n$$) forces $$c$$ to have non-negative coordinates. Of course, one may divide $$c$$ by the sum of its coordinate (which is strictly positive).