4
$\begingroup$

Let $P\subseteq \mathbb{R}^n$ be a full dimensional polytope. Let us assume that $P$ has a facet description with the following inequalities: $$ \left<x,u_F\right> \geq -a_F$$ where $u_F\in \mathbb{R}^n$ and $a_F\in \mathbb{R}$ for each facet $F$ of the polytope.

In other words, $P$ is the bounded intersection of the halfspaces $H_{u_F,-a_F}^+$. For each $Q$ face of $P$ we define the cone $$\sigma_Q := \operatorname{Cone}(u_F: F \text{ facet, } F\supseteq Q)$$

What I want is to prove that $$\sigma_Q = \{u\in \mathbb{R}^n : \left<x,u\right> \leq \left<y,u\right> \text{ for all } x\in Q, y\in P\}$$

My thoughts: It is easy to prove one of the inclusions. For the other, I wanted to use (one of the many versions of) Farkas Lemma.

If $u\in \mathbb{R}^n$ satisfies $\left<x,u\right>\leq \left<y,u\right>$ for each $x\in Q$ and $y\in P$, in particular, there exists a face $Q'$ of $P$ such that $Q' = P \cap H_{u,a}$ for certain $a=\left<x,u\right>$ for any $x\in Q$ (this value is independent of $x\in Q$), also $Q\subseteq Q'$ and $P\subseteq H_{u,a}^+$. I tried to use Farkas Lemma II (see Ziegler's book). So, to conclude that $u\in \sigma_Q$, I need to prove that there cannot exist a vector $m\in \mathbb{R}^n$ with the property that: $$\left<m,u_F\right> \geq 0 \text{ for all facets } F\supseteq Q'$$ and simultaneously $$\left<m,u\right> < 0.$$

To get a contradiction I think it suffices to show that one can find a point $x\in P\smallsetminus Q'$ such that $x = q - \lambda m$ for a $q\in Q'$ and $\lambda > 0$.

In that case, $x\in P\smallsetminus Q'$ implies that for some facet $F$ with $F\supseteq Q'$ it has to be: $\left<x,u_F\right> > -a_F$, which yields $\left<q,u_F\right> - \lambda\left<m,u_F\right> > -a_F$. The fact that $q\in Q'$ implies that $\left<q,u_F\right> = -a_F$, from where it follows $\lambda\left<m,u_F\right> < 0$ and $\lambda > 0$ yields $\left<m,u_F\right> < 0$ which is the desired contradiction. I am having trouble to prove the existence of such an $x$.

Of course, a different approach to prove this is also welcome!

$\endgroup$

1 Answer 1

1
$\begingroup$

Let's name $\sigma_1 = \operatorname{cone}(u_F : F \text{ facet}, Q \subset F)$ and $\sigma_2 = \operatorname{cone} (\{y-x : x \in Q, y \in P\})$

As you noticed, $\sigma_1 \subset \sigma_2^{\vee}$ is obvious, so only the second direction is interesting.

Notice that the problem is translation invariant, so choosing appropriate coordinates we can assume that $0 \in \operatorname{relint}(Q)$ the point in the relative interior. Using this assumption we can see that $\sigma_2 = \operatorname{cone}(P)$ where $P$ interpreted as a set of vectors. Indeed, $\operatorname{cone}(P) \subset \sigma_2$ is the implication of $x-0 \in \sigma_2$ and $\sigma_2 \subset \operatorname{cone}(P)$ is the implication of $y \in \operatorname{cone}(P), -x \in \operatorname{cone}(P)$ for any $y \in P, x \in Q$. Notice that $-x \in \operatorname{cone}(P)$ is the consequence of the $0 \in \operatorname{relint}(Q)$.

Using all those reductions the problem now is to check that the obvious inclusion $\sigma_1 \subset \operatorname{cone}(P)^{\vee} $ is in fact equality. Suppose it is not, so there is a functional $\phi \in \operatorname{cone}(P)^{\vee}$ such that it is not in $\sigma_1$. Let $A$ be the matrix in which all $u_F, F \supset Q$ written by columns, $Ax = \phi, x \geq 0$ have no solutions, by Farkas II there is a vector $v$ such that $(v,u_F) \geq 0$ for every facet $F \supset Q$ but $(v,\phi) < 0$ so $v \not \in \operatorname{cone}(P)$.

Let $U = \{x \in \mathbb R^n : (u_F,x) + a_F >0, F \not \supset Q\}$ this is the open set which contains $0$ and I claim that

$$U \cap P = U \cap \{x \in \mathbb R^n : (u_F,x) \geq 0, F \supset Q\}$$ indeed, H-polytope $P$ could be defined by $P=\{x \in \mathbb R^n :(u_F,x) + a_F \geq 0, F \text{ is facet}\}$ part of equations are satisfied by restricting to $U$ and part of them satisfied explicitly. Notice that $a_F = 0$ for $F \supset Q$, because $0 \in F$ in that case.

Returning to the point $v$ such that $(v,u_F) \geq 0, F \supset Q$ and $v \not \in \operatorname{cone}(P)$. Since $U$ is open and contains $0$ there is $t \in \mathbb R_{>0}$ such that $tv \in U$, because $tv$ satisfying all the inequalities $(u_F,tv) = t(u_F,v) \geq 0, F \supset Q$ we have $tv \in U \cap P$ so $tv \in P$, but Farkas II says that $tv \not \in \operatorname{cone}(P)$ (since $v \not \in \operatorname{cone}(P)$) this is the contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.