3
$\begingroup$

I was interested in the following:

Given two polyhedra $P_1, P_2$ specified in the form:

$$ P_1 = {x : A_1x \le b_1 } $$ $$ P_2 = {x : A_2x \le b_2 } $$

Whereas $ x \in R^n$ and $b_1, b_2$ are real vectors of same "height" dimension as $P_1$ and $P_2$ respectively.

How does one determine the convex hull $C$ of these two polyhedra. Given in the form

$$ C = {x: Qx \le \tau} $$

Whereas $Q,\tau$ should be the minimum number of inequalities necessary to specify the set.

I had posted this question on OR-Exchange:

https://www.or-exchange.org/questions/12714/how-to-determine-cuts-for-convex-hull

Which recommended fourier-motzkin elimination in conjunction with a simple scheme for including every-point in the hull.

My one qualm is this doubled the number of variables. And running fourier-motzkin would take exponential time to reduce the "excess" variables.

Is there a procedure that that doesn't take exponential time which maintains the same number of variables?

$\endgroup$
  • 2
    $\begingroup$ Why would you be concerned about doubling the number of variables? It wouldn't surprise me to find that standard LP presolvers have theoretically exponential worst-case performance; but if that is the case, it just indicates that exponential complexity ought not be an automatic disqualifier, because they do work well in practice. $\endgroup$ – Michael Grant Aug 28 '15 at 13:49
  • $\begingroup$ The convex hull. In the same number of dimensions, for the two polyhedra has number of (n-1) dimensional facets that is polynomially bounded on the number if (n-1) dimensional facets of the original two polyhedra. To eliminate the doubling of variables back to the original n, results in exponential amount of facets (many of which become redundant), I find it, at least odd that the convex hull, which isn't by itself very complex in MY formulation, needs an EXPTIME worst case algorithm. $\endgroup$ – frogeyedpeas Aug 28 '15 at 13:56
  • $\begingroup$ @MichaelGrant so hence I am curious and hopeful if in this specific application a polynomial time hull generating algorithm exists. Where the hull is given as a system of inequalities $\endgroup$ – frogeyedpeas Aug 28 '15 at 13:58
  • $\begingroup$ Well, the problem is that correct algorithms have to handle not just problems like yours which "isn't by itself very complex" but also ones that are! The exponential-time simplex algorithm for LP, for instance, rarely consumes exponential time in practice, but we know that it will for certain problems. Thus is the conundrum. $\endgroup$ – Michael Grant Aug 28 '15 at 13:59
  • 1
    $\begingroup$ Please know, I voted your question up, I think it's a very interesting one. I just don't think your theoretical objectives will be satisfied. My suspicion however is that a practical implementation will work just fine for you, even if it is not theoretically tractable. $\endgroup$ – Michael Grant Aug 28 '15 at 14:01
2
$\begingroup$

You cannot avoid an exponential blow-up in the number of resulting constraints.

As an example, let us look at cross-polytope $P_3$ in $\mathbb{R}^n$. It is the convex hull of all vertices obtained by all permutations of $(\pm1,0,\dots,0)$. Hence, it has $2n$ vertices and $2^n$ facets (see https://en.wikipedia.org/wiki/Cross-polytope) and its $\mathcal{H}$-representation $Qx \leq \tau$ has at least $2^n$ rows. On the other hand, the two simplices $P_1$ and $P_2$, where $$P_1 = conv\{(0,\dots,0), (1,0,\dots,0), (0,1,0,\dots,0), \dots, (0,\dots,0,1)\}$$ $$P_2 = conv\{(0,\dots,0), (-1,0,\dots,0), (0,-1,0,\dots,0), \dots, (0,\dots,0,-1)\},$$ have $n+1$ vertices and also $n+1$ facets. Hence, their (minimal) $\mathcal{H}$-representations $A_1x \leq b_1$ and $A_2x \leq b_2$ have $n+1$ rows each. It is crucial to note that the convex hull of $P_1$ and $P_2$ is exactly the cross-polytope $P_3$. This shows that in your setting (unless I missed something about the "specific application") it is impossible to have a procedure which does not take exponential time at worst.

$\endgroup$
  • $\begingroup$ Great answer. Of course, the cross-polytope, being just the unit ball of the $\ell_1$ norm, can readily be represented using $O(n)$ inequalities if you are allowed to introduce additional variables. For instance, introducing $y\in\mathbb{R}^n$, we have: $$-y_i \leq x_i \leq y_i, \quad i=1,2,\dots,n,\quad \sum_i y_i \leq 1$$ $\endgroup$ – Michael Grant Aug 29 '15 at 15:40
  • $\begingroup$ Thanks, Michael. BTW: I like the idea of introducing additional variables and solving the problems by means of linear programs afterwards. Often you don't need the actual $\mathcal{H}$-representation. $\endgroup$ – Willem Hagemann Aug 29 '15 at 16:18
  • $\begingroup$ That's right, it all depends on the underlying purpose for building the inequalities! $\endgroup$ – Michael Grant Aug 29 '15 at 16:30
  • $\begingroup$ so this is intriguing... there are explicit cases where raising the dimension of the system, even if representing the same object, results in a more compact $\mathcal{H}$ representation $\endgroup$ – frogeyedpeas Feb 17 '16 at 0:10
2
$\begingroup$

No, I don't think you will find a guaranteed fast algorithm, as the problem appears intractable in general, if I understand the below paper correctly. A quick search led me to, e.g.,

On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes, by Hans Raj Tiwary

$\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.