Convex Hull of the Union of Subgradients So for the function:
$$ f(x) = \underset{i=1,\ldots,m}{max}{f_{i}(x)} $$
The set of subdifferentials at a given point $x_{k}$ is given by:
$$ \partial f(x_{k}) = conv\Big( \bigcup\limits_{i\in I_{A}(x_{k})} \partial f_{i}(x_{k})  \Big) $$
Where:
$$ I_{A}(x_{k}) = \{i | f_{i}(x_{k}) = f(x_{k})\} $$
I am not sure how can I actually compute this for given set of functions. Would it simply be:
$$ \partial f(x_{k}) = \sum\limits_{i \in I_{A}(x_{k})} \alpha_{i} \partial f_{i}(x_{k})  $$
Where $ \sum\limits_{i \in I_{A}(x_{k})} \alpha_{i} = 1$? 
Basically, what I don't understand is: How is the convex hull of the union of a set of vectors different than the convex hull of those vectors? 
 A: Note that $\partial f_i$ might be also a set, and not necessarily a singleton. So, the right way to express the convex hull of everything is to write it as the convex hull of the union of all these sets. If the sets happen to be singletons then it reduces to the convex hull of all these points.
A: An example for functions $\mathbb{R}\rightarrow\mathbb{R}$ is: 
$$ f_1(x) = |x|, \quad f_2(x) = 2x $$
Then 
$$ f(x) = \max[|x|, 2x]   = \left\{ \begin{array}{ll}
2x &\mbox{ if $x \geq0$} \\
-x  & \mbox{ if $x<0$} 
\end{array}
\right.$$
Now at $x=0$ both functions are active and the active index set is  $I=\{1, 2\}$,  and 
\begin{align}
\partial f_1 (0) &= \{m \in \mathbb{R} : -1\leq m \leq 1\} \\
\partial f_2(0) &= \{2\} 
\end{align}
Notice that both $\partial f_1(0)$ and $\partial f_2(0)$ are indeed convex sets. 
So the union is: 
$$ U = \{2\} \cup [-1,1] $$
The convex hull of $U$ is the set of all points $z$ that can be written as
$$ z = \sum_{i=1}^k \theta_i z_i $$
for some positive integer $k$, some $z_1, ..., z_k$ in $U$, and some nonnegative values $\theta_1, ..., \theta_k$ that sum to 1.  But the set of all such points is just all real numbers in the closed interval from $-1$ to $2$: 
$$ Conv(U) = [-1, 2] $$

Claim: If $A_1, ..., A_m$ are nonempty convex subsets of $\mathbb{R}^n$ then $Conv(\cup_{i=1}^m A_i)$ can be described as the set of all points $z$ of the form: 
$$ z = \sum_{i=1}^m \theta_i z_i$$
for some nonnegative values $\theta_1, ..., \theta_m$ that sum to 1, and some vectors $z_1, ..., z_m$ such that $z_i \in A_i$ for all $i \in \{1, ..., m\}$. 
Proof: Let $z \in Conv(\cup_{i=1}^m A_i)$.  By definition, there is a positive integer $k$ and (without loss of generality, positive) values $\beta_1, ..., \beta_k$ that sum to 1 such that: 
$$ z = \sum_{j=1}^k \beta_j v_j $$
for some vectors $v_1, ..., v_k \in \cup_{i=1}^m A_i$. However, we can group the $v_j$ vectors into which set $A_i$ they come from, breaking ties (in cases when $v_j$ belongs to more than one $A_i$ set) in favor of the smallest $i$.  For each $i \in \{1, ..., m\}$ define $B_i$ as the set of all indices $j$ such that $v_j \in A_i$, but $v_j \notin A_k$ for any $k <i$.  For simplicity, assume each set $B_i$ is nonempty (this avoids distractions and the general proof without this assumption is similar).  For each $i \in \{1, .., m\}$, define $\theta_i = \sum_{j \in B_i} \beta_j$ and note that $\theta_i>0$ and $\sum_{j \in B_i} \frac{\beta_j}{\theta_i} =1$.  Then
$$ z = \sum_{j=1}^k \beta_j v_j = \sum_{i =1}^m \sum_{j \in B_i} \beta_j v_j = \sum_{i=1}^m\theta_i \underbrace{\left[\sum_{j\in B_i} \frac{\beta_j}{\theta_i}v_j\right]}_{\in Conv(A_i)} $$
But $Conv(A_i) = A_i$ since $A_i$ is convex for each $i$.  For each $i \in \{1, ..., m\}$, define $z_i = \sum_{j \in B_i} \frac{\beta_j}{\theta_i}v_j$.  Then $z_i \in Conv(A_i) = A_i$ for all $i$. Also, $\theta_i$ are nonnegative values that sum to 1, and
$$ z= \sum_{i=1}^m \theta_i z_i $$
The case when some $B_i$ sets are empty can be treated by repeating the above argument over only those indices $i$ for which $B_i$ is not empty, and defining $\theta_i=0$ whenever $B_i=\phi$.
$\Box$
