1
$\begingroup$

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} $$

  • 0
    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.2012-04-25
  • 0
    @TenaliRaman, I think he knows that. He is asking for a strategy to show these facts.2012-04-25
  • 0
    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.2012-04-25
  • 0
    Above $\theta_1 + \theta_2 + \theta_3 = 1$, as required by convex combinations.2012-04-25

1 Answers 1