4
$\begingroup$

$\newcommand\ext{\operatorname{ext}}\newcommand\R{\mathbb R}$Let $A$ be a convex polytope in $\R^n$ with nonempty interior. Consider the closed convex cone
$$K_A:=\{(l,t)\in(\R^n)'\times\R\colon\, l(x)\ge t\ \forall x\in A\}.$$

Claim: If $(l,t)$ is on an extreme ray of $K_A$, then the hyperplane $l^{-1}(\{0\})$ is parallel to a facet of the polytope $A$.

Is this claim true?

$\endgroup$

2 Answers 2

1
$\begingroup$

Let $A_0\subset A$ be the set where $\ell$ attains a minimum on $A$. It is a face of some dimension $k<d$. If $k=d-1$, we are done. Assume that $k<d-1$. Without loss of generality, $0\in A_0$ and moreover 0 belongs to a relative interior of $A_0$ (it is easy to check that your question is translation-invariant with respect to $A$). Let $\ell_1=0,\ldots,\ell_m=0$ be equations of all facets which contain $A_0$, let $\ell_i$ on $A$ be non-negative. Consider two cases:

  1. $\ell$ is a non-negative combination of $\ell_1,\ldots,\ell_m$: $\ell=\sum c_i\ell_i$, $c_i\geqslant 0$. If, say, $c_1>0$, then $\ell$ is a half-sum of two functionals $\ell-c_1 \ell_1$, $\ell+c_1\ell_1$ which are non-negative on $A$. This shows that our ray is not extremal.

  2. $\ell$ is not a non-negative combination of $\ell_1,\ldots,\ell_m$. Then by separation there exists $x\in \mathbb{R}^n$ such that $\ell(x)<0$ but $\ell_i(x)\geqslant 0$. For small $\lambda>0$ the point $\lambda x$ belongs to $A$: indeed, $A$ is a finite intersection of half-spaces, for all of them except our $m$ guys $\{\ell_i\geqslant 0\}$ 0 is an interior point. Thus for small $\lambda$ the point $\lambda x$ belongs to these other half-subspaces, and it belongs to $\{\ell_i\geqslant 0\}$ for every positive $\lambda$. But this is a contradiction, since $\ell$ is non-negative on $A$.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer. $\endgroup$ Commented Dec 3, 2023 at 4:59
0
$\begingroup$

The set $K_A$ is essentially a polar of $A$. Indeed, we have $$ A = \{ x \in \mathbb R^n \mid l(x) \ge t \; \forall (l,t) \in K_A\} =: B.$$ The inclusion "$\subset$" is clear and in order to check "$\supset$", let us take $y \not\in A$. Thus, we can separate $y$ and $A$, i.e., there exists $l \in (\mathbb R^n)'$ and $\varepsilon > 0$ with $$ l(y) + \varepsilon \le l(x) \qquad\forall x \in A.$$ Thus, $(l, l(y)+\varepsilon) \in K_A$ and, therefore, $y \not\in B$. Hence, $A = B$.

Now, let $E$ be the extremal rays of $K_A$. Since $K_A$ is the conical convex hull of $E$, we get $$ A = \{x \in \mathbb R^n \mid l(x) \ge t \; \forall (l,t) \in E\}.$$ This description is also minimal, i.e., for each strict subset $F \subsetneq E$, $$ A \ne \{x \in \mathbb R^n \mid l(x) \ge t \; \forall (l,t) \in F\}.$$ This should give us that for each $(l,t) \in E$, $$ A \cap l^{-1}(\{t\})$$ is a face of $A$.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. Can you detail your last sentence? $\endgroup$ Commented Jul 5, 2023 at 15:36
  • $\begingroup$ I am not totally sure, because I do not speak convex geometry fluently. But the set on the last line is nonempty and on the boundary of $A$. Hence, it is a face of $A$. $\endgroup$
    – gerw
    Commented Jul 5, 2023 at 17:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .