# Convex hull of sets defined by (in)equalities

If you define the convex hull of a set $X$ as the set of all convex combinations of elements of $X$, it becomes difficult to decide if a given element $w$ belongs or not to $conv(X)$ (You have to discover whether $w$ can be written as a convex combination of elements of X or not). But if you have a characterization of $conv(X)$ as a system of (in)equalities, it becomes easier.

Consider the sets:

$$A=\{(x,y,z)\in\mathbb{R}^3; y\geq1, z\geq1, y+z=3, x=3\} ,$$ $$B=\{(x,y,z)\in\mathbb{R}^3; x\geq1, y\geq1, x+y=3, z=3\},$$ $$C=\{(x,y,z)\in\mathbb{R}^3; x\geq1, z\geq1, x+z=3, y=3\}.$$

These three sets are segments. Show that the convex hull $\operatorname{conv}(A\cup B\cup C)$ is equal the set:

$$\begin{cases} x\geq1,y\geq 1,z\geq 1; \\ x+y\geq3, y+z\geq3, x+z\geq3;\\ x+y+z=6 \end{cases}$$

-
How do you show two sets are equal? Take element from one set and show it belongs to the other set as well, then take an element from the other set and show it belongs to the first one. – TenaliRaman Apr 25 '12 at 16:24
@TenaliRaman, I think he knows that. He is asking for a strategy to show these facts. – matgaio Apr 25 '12 at 20:01
Consider three points $(x_1, y_1, z_1) \in A, (x_2, y_2, z_2) \in B, (x_3, y_3, z_3) \in C$ and consider the point $(\theta_1x_1 + \theta_2x_2 + \theta_3x_3, \theta_1y_1 + \theta_2y_2 + \theta_3y_3, \theta_1z_1 + \theta_2z_2 + \theta_3z_3)$. This point is in hull. Now, we know $x_1,x_2,x_3 \geq 1$, therefore, $\theta_1x_1 + \theta_2x_2 + \theta_3x_3 \geq 1$ satisfying the first inequality. Similarly, one can show $\theta_1y_1 + \theta_2y_2 + \theta_3y_3 \geq 1$. In the similar vein, one has to go ahead and show all the inequalities are satisfied. That completes one direction, then vice versa. – TenaliRaman Apr 25 '12 at 20:33
Above $\theta_1 + \theta_2 + \theta_3 = 1$, as required by convex combinations. – TenaliRaman Apr 25 '12 at 20:34

Here's a boring way. Let $S$ denote the second set. It should be obvious that $A,B,C$ and $S$ are convex.

First notice that the extreme points of $A$ are $(3,1,2)$ and $(3,2,1)$, and that we can express $A = \mathbb{co} \{ (3,1,2), (3,2,1) \}$. It is easy to check that the extreme points are in $S$, hence $A \subset S$. Similarly, the extreme points of $B$ and $C$ are the other combinations of $1,2,3$, and these can also be checked to be in $S$, hence $A \cup B \cup C \subset S$, hence by convexity $\mathbb{co} (A \cup B \cup C) \subset S$.

For the other inclusion, it helps if you sketch the set $S$, and see that it is an irregular convex hexagon in the $x+y+z=6$ plane. The extreme points will be seen to be all combinations of 1,2,3 as discussed above. I think it is easy to visualize by using the $x+y+z=6$ constraint to replace, for example, the constraint $x+y \geq 3$ by $z \leq 3$. Then $S$ can be seen to be the intersection of the plane $x+y+z=6$ and the constraints $x,y,z \in [1,3]$.

To complete the proof, one needs to verify that $S$ is the convex hull of the '$1,2,3$ combination points'. Let $(x,y,z) \in S$.

First suppose that $x=2$, then it is easy to verify that with $\lambda=\frac{y-1}{2} \geq 0$, then $(x,y,z) = \lambda (2,3,1)+(1-\lambda) (2,1,3)$.

Now suppose $x<2$. If you sketch $S$, it will be clear that $(x,y,z)$ lies in the convex hull of the points $p_1=(2,1,3)$, $p_2=(2,1,3)$, $p_3=(1,3,2)$ and $p_4=(1,2,3)$. It remains to find the coordinates.

A rather tedious calculation shows that with $\mu_1 = (x-1) \frac{(x+y-3)}{x}$, $\mu_2 = (x-1) (1-\frac{(x+y-3)}{x})$, $\mu_3 = (2-x) \frac{(x+y-3)}{x}$, $\mu_4 = (2-x) (1-\frac{(x+y-3)}{x})$, we have $(x,y,z) = \sum_{i=1}^4 \mu_i p_i$, with $\mu_i \geq 0$ and $\sum_{i=1}^4 \mu_i =1$. Hence $(x,y,z) \in \mathbb{co} \{ p_i \}_{i=1}^4$.

A similarly boring calculation shows a similar result for $x>2$. Hence $S$ is the convex hull of the '$1,2,3$ combination points'.

-