3
$\begingroup$

Suppose I have two polytopes in $\mathbb{R}^n$ given in H-representation as

$P_1: \{x | H_1 x\leq b_1 \}$

$P_2: \{x | H_2 x\leq b_2 \}$

My question is, if it is possible to efficiently (i.e., avoid going to the V-representation) compute the halfspace representation of the convex hull of their union, i.e., find $H_3$, $b_3$ such that

$\mathrm{convh}\{P_1 \cup P_2\} = \{x | H_3x\leq b_3\}$.

Note that if $P_1$, $P_2$ are given in V-representation, I can efficiently determine the V-representation of the convex hull of their union without ever needing to compute the halfspace representation. However, so far I was not able to find a "dual" procedure utilizing only the H-representation.

If it is relevant for a possible solution, the polytopes $P_1$ and $P_2$ are generated by applying a linear mapping to some other polytope $P_0=\{x|H_0x \leq b_0\}$, i.e., in my special case I have that

$P_1=A_1 P_0 = \{x|H_0A_1^{-1}x\leq b_0\}$

$P_2 = A_2 P_0 = \{x|H_0A_2^{-1}x\leq b_0\}$

where $A_1$, $A_2$ are $n\times n$ nonsingular matrices.

$\endgroup$
2
  • $\begingroup$ I have two comments: Firstly, the "dual" of the convex hull of two polyhedra in $\mathcal{H}$-representation is roughly the intersection of two polyhedra in $\mathcal{V}$-representation. $\endgroup$ Commented Jan 4, 2016 at 13:17
  • $\begingroup$ Secondly, if you don't insist on having a minimal (in the number of variables) $\mathcal{H}$-representation, then you could introduce additional variables. E.g. the convex hull of $P_1$ and $P_2$ can be written (with a few exceptions) as $\{\mathbf{x}\mid \exists \mathbf{y},\lambda\ H_1\mathbf{x} + H_1\mathbf{y} + \mathbf{b}_1\lambda \leq \mathbf{b}_1 \land -H_2\mathbf{y} - \mathbf{b}_2\lambda \leq \mathbf{0}\}$. Bold letters are vectors. The formula above holds for polytopes having at least an interior point. $\endgroup$ Commented Jan 4, 2016 at 13:18

1 Answer 1

0
$\begingroup$

I do not think that what I wanted to achieve is possible.

However, I have eliminated the need for such a procedure by restructuring my computations. (More specifically, instead of propagating the mappings $A_1$, $A_2$ forwards from $P_0$, I now iterate the inverse mappings $A_1^{-1}$, $A_2^{-1}$ backwards starting from a "desired" target set until I end up in some feasible $P_0$. As a side effect, this eliminates the need for matrix inversion).

$\endgroup$

You must log in to answer this question.

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