6
$\begingroup$

I would like to share some facts about polytopes and how to check whether a polytope is a subset of some other polytope. I will provide some methods and I would like to know whether there exist other relevant criteria. Some definitions:

Half-space: We call a half-space a set of the form $H=\{x\in\mathbb{R}^n;\langle p, x\rangle \leq q\}$.

Polytope A set $C\subseteq\mathbb{R}$ is called a polytope if it is the intersection of a finite number of subspaces.

Compact polytopes can be written as the convex hull of a finite number of points in $\mathbb{R}^n$, $C=\operatorname{conv}\{c_i\}_{i=1}^M$. Any polytope can be written as $C=\{x\in\mathbb{R}^n; Hx\leq K\}$, where $H\in\mathbb{R}^{s\times n}$ and $K\in\mathbb{R}^s$ and $\leq$ stands for the component-wise comparison relation.

Affine mappings of polytopes Let $C\subseteq\mathbb{R}^n$ be a polytope, $A\in\mathbb{R}^{m\times n}$ and $b\in\mathbb{R}^m$. We introduce the following notation: $AC+b=\{z=Ac+b;c\in C\}$.

Ball infinity A special polytope is the closed ball of the infinity norm, $\|x\|_\infty=\max_{i=1,\ldots,n}|x_i|$. It is $\mathcal{B}_\infty=\{z;\|z\|_\infty\leq 1\}$.

Criterion 1. Let $C_1, C_2$ be two polytopes and $C_1$ be compact. Then $C_1\subseteq C_2$ if and only if its extreme points are in $C_2$. (The proof is trivial).

In practice, the use of this criterion implies the enumeration of all extreme points of a polytope and is computationally prohibitive in high-dimensional spaces.

Criterion 2. Let $A,B\in\mathbb{R}^{m\times n}$. It is $A\mathcal{B}_\infty\subseteq B\mathcal{B}_\infty$ if and only if $\|Ax\|_1\leq \|Bx\|_1$ for all $x\in\mathbb{R}^n$ (Recall that $\|x\|_1=\sum_{i=1}^n|x_1|$).

Proof. Let $\delta^\star(x\mid C)$ be the support function of a set $C$, i.e., $\delta^\star(x\mid C)=\sup_{y\in C}\langle x,y\rangle$. Since $A\mathcal{B}_\infty$ and $B\mathcal{B}_\infty$ are both closed and convex sets, it holds that for all $x\in\mathbb{R}^n$ (see: R. T. Rockafellar, "Convex Analysis," Princeton University Press, New Jersey, 1972, ISBN: 0-691-08069-0):

\begin{align} &A\mathcal{B}_\infty\subseteq B\mathcal{B}_\infty\\ &\Leftrightarrow \delta^\star(x\mid A\mathcal{B}_\infty) \leq \delta^\star(x\mid B\mathcal{B}_\infty)\\ &\Leftrightarrow \sup\{\langle x,As \rangle, s\in \mathcal{B}_{\infty}\}\leq \sup\{\langle x,Bp \rangle, p\in \mathcal{B}_{\infty}\}\\ &\Leftrightarrow \sup_{\|s\|_{\infty}\leq 1}\langle A'x,s \rangle\leq \sup_{\|p\|_{\infty}\leq 1}\langle B'x,p \rangle\\ &\Leftrightarrow \| Ax\|_1 \leq \| Bx\|_1, \end{align} which proves the assertion. $\square$

A straightforward generalisation of Criterion 2 is:

Criterion 3. Let $\|\cdot\|$ be a norm in $\mathbb{R}^n$ and let $\|\cdot\|^\star$ be its dual norm (Defined as $\|x^\star\|^\star\triangleq \sup_{\|x\|\leq 1}\langle x,x^\star\rangle$). Let $\mathcal{B}=\{z\in\mathbb{R}^n; \|z\|\leq 1\}$. Then $A\mathcal{B}\subseteq B\mathcal{B}$ if and only if $\|Ax\|^\star \leq \|Bx\|^\star$ for all $x\in\mathbb{R}^n$.

We may use Criterion 3 with $\|\cdot\|=\|\cdot\|_1$ (and $\|\cdot\|^\star=\|\cdot\|_\infty$). Also, if $C$ is a nonempty balanced absorbing compact polytope containing the origin in its interior, then its Minkowski functional $p_C(x)=\inf_{\lambda>0} \{x\in\lambda C\}$ is a norm and again Criterion 3 applies. In this case, if $\|x\|\triangleq p_C(x)$, then for $x^\star\in\mathbb{R}^n$:

$$ \|x^\star\|^\star = \sup_{x}\{ \langle x, x^\star\rangle, p_C(x)\leq 1\} $$

But, the set $\{x: p_C(x)\leq 1\}$ in this case is the topological closure of $C$, i.e., $C$ since it is assumed to be closed. Hence $\|x^\star\|^\star=\delta^\star(x^\star\mid C)$.

In order to state the next result we introduce the notation $A^{[k]}$ to denote the first $k$ rows of a matrix $A\in\mathbb{R}^{m\times n}$, with $1\leq k\leq m$.

Criterion 4. Let $H_P, H_Q \in \mathbb{R}^{m\times n}$ have full row rank and define $P=\{x\in\mathbb{R}^n: H_P x \leq K_P\}$ and $Q=\{x\in\mathbb{R}^n: H_Q x\leq K_Q\}$. The following are equivalent:

  1. $P\subseteq Q$
  2. One of the following holds true:
    • There is a matrix $M$, lower triangular and with positive diagonal elements so that $H_P=MH_Q$ and $K_P=MK_Q$
    • There is an $l$, with $1\leq l\leq m$ and a matrix $M\in\mathbb{R}^{l\times l}$ so that $H_P^{[l]} = MH_Q^{[l]}$ and $q_P^{[l]}<Mq_Q^{[l]}$

Proof. See Lemma 4.5.1. in: L. Q. Thuan, "Piecewise Affine Dynamical Systems: Well-posedness, controllability and stabilizability," PhD. Thesis, University of Groningen, 2013 $\square$

Are there other relevant results?

$\endgroup$
1
  • $\begingroup$ Regarding criterion 4, having both H matrices full row rank renders both polytopes unbounded. It would be interesting to explore similar results for the bounded polytopes. I have a question you may be interested in looking at and providing an answer: mathoverflow.net/q/385579/32660 $\endgroup$
    – Hans
    Mar 4, 2021 at 19:25

1 Answer 1

3
$\begingroup$

Though I have not checked the given criteria above, I would like to add the following criterion:

Let $P_1=\{\mathbf{x}\mid A\mathbf{x} \leq \mathbf{a}\}$ and $P_2=\{\mathbf{x}\mid B\mathbf{x}\leq \mathbf{b}\}$ be two polyhedra. Further, let $\mathbf{b}_i^T$ denote the $i$th row of the matrix $B$ and $b_i$ denote the $i$th component of the vector $\mathbf{b}$. If for each row $\mathbf{b}_i^T$ of $B$ it holds that the linear program

$\quad$ maximize $\mathbf{b}_i^T\mathbf{x}$ subject to $A\mathbf{x}\leq\mathbf{a}$ $\quad$(*)

has an optimal value $\lambda_i$ with $\lambda_i \leq b_i$, then $P_1\subseteq P_2$.

Note: $\lambda_i$ is the value of the support function $\delta^*(\mathbf{b}_i,P_1)$. Hence, it is enough to check the values of the support function of $P_1$ over the finitely many vectors $\mathbf{b}_i$ determined by the representation matrix $B$ of $P_2$.

$\endgroup$
4
  • 1
    $\begingroup$ See also: math.stackexchange.com/questions/856850/… $\endgroup$ Apr 10, 2015 at 6:25
  • $\begingroup$ In $\lambda_i \leq b_i$, what is $b_i$? $\endgroup$ Aug 11, 2020 at 8:17
  • $\begingroup$ $\lambda_i$ is the optimal value of the linear program (I edited the answer accordingly). $b_i$ is the $i$th component of the vector $\mathbf b$. That is, in other words, the extend $\lambda_i$ of $P_1$ is in every explicitly given direction of $P_2$ (these are given by the vectors $\mathbf b_i$) less or equal than the 'extend' of $P_2$. $\endgroup$ Aug 11, 2020 at 10:11
  • $\begingroup$ Great, thanks Willem! $\endgroup$ Aug 11, 2020 at 12:54

You must log in to answer this question.

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