4
$\begingroup$

Let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a (bounded) polyhedron for $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, $n,m > 0$.

Moreover, let $M \colon \mathbb{R}^n \to \mathbb{R}^p$ be a linear map for $p \leq n$.

I'm interested in computing a $\mathcal{H}$-representation of $M \cdot P = \{Cx \mid x \in P\}.$ Are there any known algorithms, besides the "Quantifier elimination for linear arithmetic" as pointed out in 1?

$\endgroup$
1
3
$\begingroup$

Yes, by the Motzkin Double Description Method you compute the $V$-representation of $P,$ hence the $V$-representation of $M P,$ then, by the double description method (again) the $H$-representation of $M P.$

$\endgroup$
0

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.