7
$\begingroup$

Is there a simple proof that shows:

  1. Linear transformation of a $\mathcal{H}$-polyhedron (i.e. the intersection of finitely many closed half-spaces) is a $\mathcal{H}$-polyhedron.
  2. Minkowski sum of two $\mathcal{H}$-polyhedrons is a $\mathcal{H}$-polyhedron.

I know a proof of (1.) based on Fourier-Motzkin elimination. and, I know (2.) is a simple consequence of (1.).

Every different approach is appreciated.

$\endgroup$
  • 7
    $\begingroup$ Why would anybody need Fourier-Motzkin elimination to prove (1)? It is immediate from the definition. $\endgroup$ – Misha Jun 28 '14 at 18:32
  • 2
    $\begingroup$ I might be missing something obvious, but I'm not convinced that 1. is immediate from the definition. That the image of a polyhedron in $\mathbb{R}^{n+1}$ under the projection map $\mathbb{R}^{n+1} \to \mathbb{R}^n$ to the first $n$ coordinates is again a polyhedron was apparently not considered too trivial to bother proving in Tame Topology and O-minimal Structures by van den Dries (see pp. 26-27). (The general result follows from this without too much pain.) $\endgroup$ – Todd Trimble Jun 28 '14 at 22:01
  • 2
    $\begingroup$ @Misha Thanks. I was just about to remark as Mahdi did, although you might have an easy workaround to handle the noncompact case (do you?). But I think Mahdi's question is legitimate, since he asks for a simple proof that presumably works from first principles, i.e., from the definition he gives of polyhedron. My own feeling is that the question should be honored. $\endgroup$ – Todd Trimble Jun 28 '14 at 23:37
  • 2
    $\begingroup$ @Misha It would be great to see such an argument fleshed out, just to dispel any worry that there's handwaving involved here. Would you consider writing up your thoughts as an answer? While I feel somewhat confident that Fourier-Motzkin is not to be dismissed lightly, any alternative insights you have would be appreciated. (Are there generalized linear program formulations that translate unbounded problems into bounded ones? Perhaps this paper is relevant: lara.epfl.ch/w/_media/…, especially in sections 4 and 5.) $\endgroup$ – Todd Trimble Jun 29 '14 at 1:26
  • 4
    $\begingroup$ @DeaneYang Yes, convex polyhedra are implied in the post (intersection of finitely many closed half-spaces). The trouble with your argument is that the taking of images does not preserve intersections. $\endgroup$ – Todd Trimble Jun 29 '14 at 2:01
5
$\begingroup$

I'm not familiar with Fourier-Motzkin, so I don't know how different the following argument is from what one usually does, but it's direct and elementary (and constructive, it in principle produces the new constraints from the old ones).

The claim is trivial if $A\in\mathbb R^{n\times n}$ is invertible, and a general $A$ can be written as $A=PB$, with $B$ invertible and $P$ a projection, so we can focus on projections. We can in fact also assume that $P$ is a projection on a codimension $1$ subspace, say $P(y+\alpha e)=y$, for $y\perp e$ and $\alpha\in\mathbb R$. Suppose the polyhedron $Q$ is defined by the constraints $x\cdot n_j\le c_j$. We are then interested in $$ S=P(Q)=\{ y\in\{e\}^{\perp} : y\cdot n_j \le c_j + d_j\alpha \:\textrm{ for some }\alpha\in\mathbb R \textrm{ and }j=1,\ldots, N \} $$ (the same $\alpha$ for all $j$ of course). We can further assume that $d_j=0$ or $\pm 1$. Call a constraint zero, positive, or negative according to the sign of $d_j$. The zero constraints are already of the desired type and can be ignored. The case of only positive (or only negative) constraints is trivial ($S=\{e\}^{\perp}$ in both cases). In the remaining case, I claim that $y\in S$ precisely if $$ y\cdot (n_k^+ + n_j^-) \le c_k^+ + c_j^-\quad\quad\quad (1) $$ for all choices of pairs $(k,j)$ of one positive and one negative condition. Indeed, we can rewrite (1) as $$ y\cdot n_k^+ \le c_k^+ + \min (c_j^--y\cdot n_j^-) , $$ and then observe that the largest $\alpha$ that satisfies all negative constraints for a given $y$ is $\alpha=\min (c_j^--y\cdot n_j^-)$. It is now clear that (1) is equivalent to $y\in S$.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Your Approach is similar to Fourier-Motzkin elimination. $\endgroup$ – Mahdi Jun 29 '14 at 10:07
  • $\begingroup$ For clarification your answer, Please says that $S$ is the projection of the polyhedron and defines theses notations: $n_j$, $c_j$ in your answer. $\endgroup$ – Mahdi Jun 29 '14 at 11:14
  • $\begingroup$ @Mahdi: Yes, $S$ is $P(Q)$, where $Q$ is the original polyhedron, defined by the constraints $x\cdot n_j\le c_j$. I'll edit. $\endgroup$ – Christian Remling Jun 29 '14 at 15:27
  • $\begingroup$ I think that for compatibiliy of the dimensions of $y$ and $n_j$, it is better to write $y\in\{e\}^\perp$ instead of $y\in \mathbb{R}^{n-1}$ in definition of $S$. $\endgroup$ – Mahdi Jun 29 '14 at 20:16
  • $\begingroup$ Are you definition $P(Q)$ in the way you write there of you are trying to prove $P(Q)$ has that form? Moreover, why the same $\alpha$ for all $j$? Thank you! $\endgroup$ – JumpJump Sep 9 '16 at 18:58

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.