5
$\begingroup$

$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!

This was cross-posted at https://math.stackexchange.com/questions/4504475/how-to-prove-this-corollary-of-hyperplane-separation-theorem?noredirect=1#comment9461236_4504475

enter image description here

$\endgroup$
0

3 Answers 3

6
$\begingroup$

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

$\endgroup$
38
  • 2
    $\begingroup$ @WlodAA $Y$ is used to find a point $x\in X$ in which $\eta(x)\ne 0$ $\endgroup$ Aug 10 at 6:17
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 10 at 14:42
  • 1
    $\begingroup$ @copper.hat on $Y$ every functional may be represented as a non-negative linear combination of $x_1$ and $x_2$. $\endgroup$ Aug 12 at 4:55
  • 1
    $\begingroup$ 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.) $\endgroup$ Aug 12 at 14:37
  • 2
    $\begingroup$ @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$. $\endgroup$ Aug 13 at 14:30
2
$\begingroup$

$\newcommand{\R}{\mathbb R}\newcommand{\la}{\lambda}$Let $\R_-:=(-\infty,0]$ and $\R_+:=[0,\infty)$. The desired statement is equivalent to the following:

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

$\endgroup$
6
  • $\begingroup$ 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}$? $\endgroup$
    – Ypbor
    Aug 11 at 9:04
  • $\begingroup$ @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$. $\endgroup$ Aug 11 at 17:30
  • $\begingroup$ @losif Pinelis, the hyperplane is in $V^1$, but $\mu^1$, which is the normal vector, is not in $V^1$. $\endgroup$
    – Ypbor
    Aug 12 at 7:38
  • $\begingroup$ @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$. $\endgroup$ Aug 12 at 13:38
  • $\begingroup$ 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$) $\endgroup$
    – Ypbor
    Aug 13 at 2:23
1
$\begingroup$

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

$\endgroup$

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.