3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ If I am not mistaken you conjectured that : there exists a $p$ with all positive coordinates satisfying $\diamondsuit$ ? $\endgroup$
    – Red shoes
    Jun 21 '19 at 6:43
  • $\begingroup$ @TheoBendit Are you sure? If it is true that if you cut into $X$ upon “tilting” in the positive direction, however slightly, a hyperplane through $\overline x$ with some zero coefficient, then the face in which $\overline x$ is located must be parallel to at least one of the axes and $\overline x$ is in the relative interior of it. This means that you can move slightly towards north, east, or up, etc. This would seem to contradict the singleton intersection condition, no? $\endgroup$
    – triple_sec
    Jun 21 '19 at 6:43
  • $\begingroup$ Yes, I am looking for a separating hyperplane with strictly positive (not merely non-negative) coefficients. $\endgroup$
    – triple_sec
    Jun 21 '19 at 6:45
  • $\begingroup$ @triple_sec No, I'm not. The problem I was thinking of is indeed ameliorated by the singleton intersection condition, hence the deleted comment. $\endgroup$ Jun 21 '19 at 6:45
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Fantastic answer, thank you very much! $\endgroup$
    – triple_sec
    Jun 25 '19 at 21:51
  • $\begingroup$ Is it possible that it should say "Pick $a\in\mathbb{R}^n\setminus\{0\}$" rather than just $a\in\mathbb{R}^n$? -- It's a minor thing, and the separating hyperplane theorem of course assures that such a $a$ exists, just want to be sure I fully understand the proof. $\endgroup$
    – mimuller
    Nov 21 '19 at 14:08
2
$\begingroup$

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.

enter image description here

$\endgroup$
3
  • $\begingroup$ Thank you for your answer, this was helpful. I added a figure to it depicting what’s going on. $B$ denotes the closed unit ball, right? $\endgroup$
    – triple_sec
    Jun 25 '19 at 22:48
  • $\begingroup$ Yes, It is, I forgot to mention. Nice figure! Using what software you draw that figure? @triple_sec $\endgroup$
    – Red shoes
    Jun 25 '19 at 23:00
  • $\begingroup$ I use Grapher, which is a built-in graphing software in macOS operating systems. It’s a hidden gem. I import formulae superimposed on the figure using LaTeXiT. $\endgroup$
    – triple_sec
    Jun 25 '19 at 23:08

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.