# H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows:

$P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ for $j=1\dots,r$.

Is it possible to derive the H-representation of the convex hull of the union of $P_j$s, i.e., ConvexHull$(\bigcup_j P_j)$, efficiently?

## 1 Answer

If you're okay with additional variables, then the answer is yes. This follows from Balas's extended formulation for the disjunction of polyhedra. It shows that $\operatorname{convex}.\operatorname{hull} ( \cup_j P_j)$ admits an extended formulation of size at most $\sum_{j}(\operatorname{xc}(P_j)+1)$, where $\operatorname{xc}(\cdot)$ denotes extension complexity. (The extension complexity of $P_j$ is at most the number of inequalities defining $P_j$.)

I have not thought about whether this can be done in the original space of variables.

• @ Austin: Now this question arises: If the extended formulation of convex hulls for two sets of polytopes are equivalent, can it be the case that the original convex hulls are also equivalent?
– Star
Aug 5, 2015 at 15:36
• @how many variables do you need? Aug 13, 2019 at 16:58