# 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?

• I assume the functions $f_i$ are all convex. The union of a set of vectors is just another set of vectors. So indeed the convex hull of the union is the same as the convex hull of that set of vectors (the set which comprises the union). If you mean $\sum_{i \in I_A(x_k)} \alpha_i \partial f_i(x_k)$ to be a summation of sets, and if you consider all possible $\alpha_i$ that are nonnegative and sum to 1, and if you use the fact that $\partial f_i(x_k)$ are already convex sets, then indeed you get the whole convex hull. – Michael Feb 22 '18 at 1:42
• @Michael So I need to interpret the summation as a summation of sets. In this case, can I just pick a random vector out of that summed set, and use that as sort of THE subgradient for an algorithm? – Some_Guy_2018 Feb 26 '18 at 15:01
• @Michael To clarify, suppose that $m=2$ and at some point $x_{k}$ both $f_{1}(x)$ and $f_{2}(x)$ are active. At this point, we have: $\partial f_{1}(x_{k}) = \{ \mathbf{v_{11}}, \mathbf{v_{12}}\}$ and $\partial f_{2}(x_{k}) = \{ \mathbf{v_{21}}, \mathbf{v_{22}}\}$. So the union of the subgradients is $U = \{ \mathbf{v_{11}}, \mathbf{v_{12}}, \mathbf{v_{21}}, \mathbf{v_{22}} \}$ and so the convex hull of the union would be $\partial f (x_{k}) = \alpha_{11} \mathbf{v_{11}} + \alpha_{12} \mathbf{v_{12}} + \alpha_{21} \mathbf{v_{21}} + \alpha_{22} \mathbf{v_{22}}$ where the $\alpha$s sum to 1? – Some_Guy_2018 Feb 26 '18 at 15:11
• Yes. Of course, the set of all subgradients is a convex set and cannot contain only two distinct points (as it would contain all points in between). But your example is in principle correct. By a "sum of sets" I meant like in Minkowski set addition here: en.wikipedia.org/wiki/Minkowski_addition – Michael Feb 26 '18 at 19:37

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