subdifferential rule proof

Question

How to prove that the subdifferential of $f(x) = \max_{i=1,\dots, n} f_i(x)$ satisfies \begin{align} \partial f(x) = \operatorname{conv}\left( \bigcup \partial f_i(x) \right) \end{align}

How am I suppose to utilize the property of convex hull here?

Answer 1

Ah, you'll need the Danskin-Bertsekas theorem for subdifferentials for this one. Viz,

Theorem (Danskin-Bertseka's Theorem for subdifferentials). Let $Y$ be a topological vector space and $C$ be a nonempty compact subset of $\mathbb R^n$. Let $\phi: \mathbb R^n \times Y \rightarrow (-\infty, +\infty]$ be a function such that for every $x \in C$, the mapping $\Phi(x, \cdot) : Y \rightarrow (-\infty, +\infty]$ is a closed proper convex function. Consider the function $f: Y \rightarrow (-\infty, +\infty]$ defined by $f(y) := \underset{x \in C}{\text{sup }}\Phi(x, y).$ If $f$ is proper, then it is a closed and convex. Furthermore, if $\operatorname{dom}(f)^\circ \ne \emptyset$ and $\Phi$ is continuous on $\mathbb R^n \times \operatorname{dom}(f)^\circ$, then for every $y \in \operatorname{dom}(f)^\circ$, we have $$ \partial f(y) = \text{conv}\{\partial_y \Phi(x, y) \mid x \in C_y\}, $$ where $C_y := C \cap \operatorname{opt}(\Phi(\cdot,y)) := \{x \in C \mid \Phi(x, y) = f(y)\}$.

Using the above theorem, one can easily establish the following lemma (which also solves your problem).

Lemma (subdifferential of pointwise max of $n$ functions). Let $f_1,\ldots,f_n: Y \rightarrow (-\infty, +\infty]$ be convex functions. Then for every $y \in \cap_{i=1}^n \operatorname{dom}(f_i)$ such that each $f_i$ is continuous at $y$, one has the identity $$ \partial \max(f_1,\ldots,f_n)(y) = \operatorname{conv}(\cup_{i=1}^n \partial f_i(y)). $$

Proof. Let $f := \max(f_1,\ldots,f_n)$. Define $\Phi:\mathbb R^n \times Y \rightarrow (-\infty, +\infty]$ by $\Phi(x,y):=\sum_{i=1}^n x_i f_i(y)$ and note that $f(y) = \sup_{x \in \Delta_n}\Phi(x, y)$ for every $y \in Y$. Also note that $\partial_y \Phi(x, y) = \sum_{i=1}^nx_i\partial f_i(y)$ (Minkowski sum of sets). Now invoke the above theorem. $\Box$