0
$\begingroup$

I seek to prove the following, which I guess is true:

Define $A:=\{x \ge 0\} \subset \mathbb{R}^m$ and assume that $U\subset \mathbb{R}^m$ is an affine subspace with $A \cap U=\emptyset$. Show that

$$ \delta:=\inf_{\substack{x\ge 0\\x'\in U}}\lVert x-x'\rVert>0.$$

I can easily handle the cases where $\mbox{dim}(U)=0$ or $1$.

$\endgroup$
1
$\begingroup$

Not sure how to solve this, but I can help you with one more case. If U is a hyperplane then there is some vector y and constant c such that $U=\{ x: x \cdot y =c \}$. Disjointness implies that $y \geq 0, c<0$. This implies the distance is at least $ - c/ \| y \| $.

$\endgroup$
  • $\begingroup$ Thank you for the answer, but I do not see why it should blow up? U could be parallel to one of the faces of A and even if not, I do not see a simple argument. $\endgroup$ – crankk Apr 15 at 14:21
  • $\begingroup$ @crankk you're absolutely right. I edited my answer to solve one more special case. $\endgroup$ – Amichai Lampert Apr 16 at 6:22
  • $\begingroup$ Assume that $dim(U)<m$ and that $U\cap A=\emptyset$. Does it follow that there is a hyperplane $U'$ with $U\subset U'$ and $U'\cap A = \emptyset$? That would solve the problem... $\endgroup$ – crankk Apr 16 at 11:03
  • $\begingroup$ I think I am one step away from the solution: Is it true that, given to disjoint convex closed sets $U$ and $V$ there is a $c\in\mathbb{R}$ and a non zero $v$ such that either $(x,v)\ge c > (y,v)$ or $(y,v) \ge c >(x,v)$ for all $x\in U$ and $y\in V$? $\endgroup$ – crankk Apr 17 at 7:49
  • $\begingroup$ @crankk: I don't think that's true for general convex closed sets. E.g. take $U$ to be the closed convex hull of points of the form $(0,y,0)$ and $(1,y,e^y)$ with $y\leq 0,$ and take $V$ to be the closed convex hull of points of the form $(0,y,-e^y)$ and $(1,y,0)$ with $y\leq 0.$ The only separating hyperplane is $z=0,$ which has points from both. $\endgroup$ – Dap Apr 17 at 19:42
1
$\begingroup$

I'll assume $U$ is non-empty. $U$ is of the form $u+V$ for some point $u$ and some linear subspace $V.$ Consider the projection map $\phi:\mathbb R^m\to \mathbb R^m/V.$ It takes $U$ to a single point which I will denote $[u].$ The distance between $A$ and $U$ is bounded below by (in fact equal to) the distance between $\phi(A)$ and $[u].$ So it remains to show that the distance between $\phi(A)$ and $[u]$ is positive.

Each standard basis vector $e_i$ is taken to a point other than $[u]$ because $e_i\in A$ which is disjoint from $U.$ Since $A$ is a convex cone generated by the rays $e_1,\dots,e_m,$ the set $\phi(A)$ is a convex cone generated by the rays $\phi(e_1),\dots,\phi(e_m).$ A finitely generated convex cone is polyhedral (the "Farkas-Minkowski-Weyl theorem", see for example Schrijver's "Theory of Linear and Integer Porgramming") and therefore closed. The distance between a point $[u]$ and the closed set $\phi(A)$ disjoint from $[u]$ is positive, which is what we needed to prove.

$\endgroup$
  • $\begingroup$ Thank you! I hoped for a more elemtary way, which does not need the "Farkas-Minkowski-Weyl Theorem"... $\endgroup$ – crankk 2 days ago

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.