1
$\begingroup$

Consider a linear system with a map $A: \mathbb{R}^n \rightarrow \mathbb{R}^m$ such that $y = A x$ with $n \geq m$

The input space $x$ is constrained by a zonotope set $\mathcal{X} \subseteq \mathbb{R}^n$ in an $\mathcal{H}$-representation given

$$ \mathcal{X} = \{ \, x \in \mathbb{R}^n\, | \, \, C_{x}^{T} x \leq d_{x} \, \} $$

We need to characterize the output variable $y$ by obtaining a set $\mathcal{Y} \subseteq \mathbb{R}^m$ such that

$$ \mathcal{Y} = \{ \, y \in \mathbb{R}^m \, | \, \, y = A x ,\, x \in \mathcal{X} \,\} $$

WE know that the set $\mathcal{Y}$ is also a Zonotope and could be expressed in $\mathcal{H}$-representation as

$$ \mathcal{Y} = \{ \, y \in \mathbb{R}^m\, | \, \, C_{y}^{T} y \leq d_{y} \, \} $$

Our questions are:

  1. How to mathematically prove that $\mathcal{Y}$ is a Zonotope.
  2. How to compute $\mathcal{Y}$ i.e. obtain $\{C_{y}, d_{y}\}$ given $A$ and $\{C_{x}, d_{x}\}$.
$\endgroup$
2
$\begingroup$

If $\mathcal{X}$ is the Minkowski sum of line segments $l_1,\ldots,l_k$, then $\mathcal{Y}$ is the Minkowski sum of line segments $Al_1,\ldots, Al_k$ (and hence a zonotope). As far as computing $C_y$ and $d_y$, this is a well known procedure for any polytope known as Fourier-Motzkin elimination.

$\endgroup$
3
  • $\begingroup$ Any details or supporting materials will be appreciated. $\endgroup$ Dec 5 '14 at 14:32
  • $\begingroup$ See for example the first part of Theorem 6.1 here math.lsa.umich.edu/~barvinok/polynotes669.pdf $\endgroup$ Dec 6 '14 at 22:04
  • $\begingroup$ The material is really helpful but it has been presented for a simple projection on a subset of the input coordinates which is clearly easy using FM elimination. Are there any general approach to do that? $\endgroup$ Dec 15 '14 at 10:24

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