Slanted separating hyperplanes for convex polytopes

Question

EDIT: A previous version of this question was imprecisely formulated—I am grateful to Theo Bendit for providing a counterexample for that version.

Let, for some $n\in\mathbb N$, $X\subseteq\mathbb R^n$ be a convex polytope (the convex hull of a non-empty finite set of points) and $(\overline x_1,\ldots,\overline x_n)\in X$. Define $$Y\equiv\{(y_1,\ldots,y_n)\in\mathbb R^n\,|\,y_i\geq\overline x_i\text{ for $i=1,\ldots,n$}\}.$$ Moreover, suppose that the intersection $X\cap Y$ consists of the one and only one point $\{(\overline x_1,\ldots,\overline x_n)\}$.

These conditions ensure that $X$ and $Y$ can be separated by a hyperplane: there exist some $p_1,\ldots,p_n\in\mathbb R$, not all zero, such that $$p\cdot y\geq p\cdot x\quad\text{for every $x\in X$ and $y\in Y$.}\tag{$\diamondsuit$}$$ Moreover, it is not difficult to check that the $p_i$’s are actually non-negative.

My conjecture is that all of the separating hyperplane coefficients can be taken to be strictly positive: it can be arranged in ($\diamondsuit$) that $p_i>0$ for $i=1,\ldots,n$. The goal is to ensure that the resulting hyperplane is “slanted,” as it were (not parallel to any of the axes).

I am 99% sure this conjecture is true, but the details of the proof have eluded me thus far. Any hints would be appreciated.

Answer 1

Let’s add the remaining one percent to the truth assurance.

Let $\overline x=(\overline x_1,\ldots,\overline x_n)$, $K$ be a convex cone spanned by $X-\overline x$, and $$\Bbb R^n_+=Y-\overline x=Y\equiv\{(y_1,\ldots,y_n)\in\mathbb R^n\,|\,y_i\geq 0 \text{ for $i=1,\ldots,n$}\}.$$

Since $X$ is a convex hull of a finite set, the cone $K$ is spanned by a finite set, so, by Weyl’s Theorem, $K$ is polyhedral and therefore closed (see, for instance, [Paf, Theorem 1.8] and Definition 1.3 of a polyhedral cone), and the intersection $K\cap \Bbb R^n_+=\{0\}$ is trivial. Then by Theorem 7 from §30 of [Cha], there exists a vector $p$ satisfying ($\diamondsuit$) with all positive components.

The proof is the following. Let the dual cone $K^*$ consists of all vectors $p\in\Bbb R^n$ such that $px\le 0$ for all $x\in K$. Suppose to the contrary that the cone $K^*$ contains no vectors with all positive components. Pick $a\in \Bbb R^n$ and $b\in\Bbb R$ such that $a\cdot x\ge b$ for each $x\in \Bbb R^n_+$ and $a\cdot x\le b$ for each $x\in K^*$. Since $0\in \Bbb R^n_+$, $a\cdot 0=0\ge b$. So $a\cdot x\le 0$ for each $x\in K^*$, that is $a$ belongs to a dual cone $K^{**}$ of $K^*$. We have $K=K^{**}$ by Theorem 1 from §30 of [Cha] for a closed $K$ or Lemma 1.12.3 in [Paf] for a finitely generated $K$, so $a\in K\setminus\{0\}$ and there exists $a_i<0$. Let $e^i$ in $\Bbb R^n_+$ be a vector whose $i$-th coordinate is $1$ and other coordinates are $0$. Then $a\cdot \lambda e_i=\lambda a_i<b$ for all $\lambda>0$, which is impossible, a contradiction.

References

[Cha] V.S. Charin, Linear transformations and convex sets, Kyiv: Vyshcha shkola, 1978. (in Russian).

[Paf] Andreas Paffenholz, Polyhedral Geometry and Linear Optimization. Summer Semester 2010.

Answer 2

W.L.O.G assume $\bar{x} = 0$. Define $A := \{x\;|\; \sum_{i} x_i =1 \;,\; x_i \geq 0 \}$. Clearly $A$ is compact , convex , and $ A \cap X = \emptyset $. Therefore there exists an $\varepsilon >0$ such that first $0 \notin A+ \varepsilon B $, and secondly $(A+ \varepsilon B )\cap X = \emptyset$. Let $C$ be the cone generated by $A+ \varepsilon B $, that is $ C =\{t a + \varepsilon tb ~|~ t\geq 0 ~ b \in B\}$. Since $A+\varepsilon B$ is compact and does not contain $0$, you can easily show that $C$ is a closed convex cone. Note that $Y$ is the cone generated by $A.$ Then show that $X \cap Y = \{0\}$ implies $X \cap C =\{0\}$ [to prove this you need use the polyhedrality of $X$].

Then show that any separating hyper plane that separates $X$ and $C$ has positive coordinates. Clearly there is at least one.

Advice: In order to understand the proof perfectly, draw a picture of situation.