3
$\begingroup$

Let $V$ be a finite-dimensional real vector space, let $P, Q \subseteq V$ be polytopes with $P \subseteq Q$. (Let a polytope be defined as the convex hull of finitely many points.) I'm interested in the following

Question: How can I identify the set of all affine maps $T: V \rightarrow V$ with $T(P) \subseteq Q$?

More precisely, I want to find a "nice" way to characterize the set of all maps $T: V \rightarrow V$ with the following properties:

  • $T(\alpha v_1 + (1-\alpha) v_2) = \alpha T(v_1) + (1-\alpha) T(v_2) \quad \forall \alpha \in \mathbb{R}, \forall v_1, v_2 \in V$,
  • $v \in P \Rightarrow T(v) \in Q$.

Admittedly, the question of how to find a "nice" way to characterize this set is rather vague. My motivation for this question is that I have given two such polytopes and want to study this set of maps, and it seems to me that this set is generic enough that people might have studied it.

1 Answers 1

1

If you know the extreme points of $P$, namely $\operatorname{xtr}(P)=\{p_i\}_{i\in \mathbb{I}}$,then define

$ \mathfrak{T}\triangleq \{T:V\to V : T(z)=Az+b, Ap_i+b\in Q\} $

But, you can also make use of support functions saying that $TP\subseteq Q$ if and only if $\delta^\star(x\mid TP)\leq\delta^\star(x\mid Q)$, where $\delta^\star(x\mid P)\triangleq\sup_{p\in P}\langle x,p\rangle$.

Define the Minkowski functional of a set $C$ as $\pi(x\mid C)\triangleq\inf\{\lambda>0: x\in\lambda C\}$. If $P$ contains the origin in its interior and it is absorbing (i.e., for all $x\in\mathbb{R}^n$, there is a $\lambda$ so that $\lambda P \ni x$) and if you know the extreme points of $Q$, say $\operatorname{xtr}(Q)=\{q_i\}_{i\in \mathbb{J}}$, then $TP\subseteq Q$ iff $\pi(q_i\mid TP)\geq 1$. You can further work to this direction making use of dual polytopes. For a polytope $X$, its dual is the polytope defined as $X^\star\triangleq \{x^\star: \langle x,x^\star\rangle\leq 1, \forall x\in X\}$. Then you can prove that $\pi(x\mid X)=\inf\{\langle x, x^\star\rangle,x^\star\in X^\star\}$.

If your polytopes have a more favourable structure, like $K\mathcal{B}_\infty$ or $K\mathcal{B}_1$, then you can derive simpler expressions from the above properties.

I have asked here a similar question in which I provide some criteria for polytopes being subsets of other polytopes.