5
$\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$
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 solution $\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$

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.